OSDN Git Service

PR rtl-optimization/44374
[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, 2007,
3    2008, 2009, 2010 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 /*
26 OVERVIEW:
27
28 The files in this collection (df*.c,df.h) provide a general framework
29 for solving dataflow problems.  The global dataflow is performed using
30 a good implementation of iterative dataflow analysis.
31
32 The file df-problems.c provides problem instance for the most common
33 dataflow problems: reaching defs, upward exposed uses, live variables,
34 uninitialized variables, def-use chains, and use-def chains.  However,
35 the interface allows other dataflow problems to be defined as well.
36
37 Dataflow analysis is available in most of the rtl backend (the parts
38 between pass_df_initialize and pass_df_finish).  It is quite likely
39 that these boundaries will be expanded in the future.  The only
40 requirement is that there be a correct control flow graph.
41
42 There are three variations of the live variable problem that are
43 available whenever dataflow is available.  The LR problem finds the
44 areas that can reach a use of a variable, the UR problems finds the
45 areas that can be reached from a definition of a variable.  The LIVE
46 problem finds the intersection of these two areas.
47
48 There are several optional problems.  These can be enabled when they
49 are needed and disabled when they are not needed.
50
51 Dataflow problems are generally solved in three layers.  The bottom
52 layer is called scanning where a data structure is built for each rtl
53 insn that describes the set of defs and uses of that insn.  Scanning
54 is generally kept up to date, i.e. as the insns changes, the scanned
55 version of that insn changes also.  There are various mechanisms for
56 making this happen and are described in the INCREMENTAL SCANNING
57 section.
58
59 In the middle layer, basic blocks are scanned to produce transfer
60 functions which describe the effects of that block on the global
61 dataflow solution.  The transfer functions are only rebuilt if the
62 some instruction within the block has changed.
63
64 The top layer is the dataflow solution itself.  The dataflow solution
65 is computed by using an efficient iterative solver and the transfer
66 functions.  The dataflow solution must be recomputed whenever the
67 control changes or if one of the transfer function changes.
68
69
70 USAGE:
71
72 Here is an example of using the dataflow routines.
73
74       df_[chain,live,note,rd]_add_problem (flags);
75
76       df_set_blocks (blocks);
77
78       df_analyze ();
79
80       df_dump (stderr);
81
82       df_finish_pass (false);
83
84 DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an
85 instance to struct df_problem, to the set of problems solved in this
86 instance of df.  All calls to add a problem for a given instance of df
87 must occur before the first call to DF_ANALYZE.
88
89 Problems can be dependent on other problems.  For instance, solving
90 def-use or use-def chains is dependent on solving reaching
91 definitions. As long as these dependencies are listed in the problem
92 definition, the order of adding the problems is not material.
93 Otherwise, the problems will be solved in the order of calls to
94 df_add_problem.  Note that it is not necessary to have a problem.  In
95 that case, df will just be used to do the scanning.
96
97
98
99 DF_SET_BLOCKS is an optional call used to define a region of the
100 function on which the analysis will be performed.  The normal case is
101 to analyze the entire function and no call to df_set_blocks is made.
102 DF_SET_BLOCKS only effects the blocks that are effected when computing
103 the transfer functions and final solution.  The insn level information
104 is always kept up to date.
105
106 When a subset is given, the analysis behaves as if the function only
107 contains those blocks and any edges that occur directly between the
108 blocks in the set.  Care should be taken to call df_set_blocks right
109 before the call to analyze in order to eliminate the possibility that
110 optimizations that reorder blocks invalidate the bitvector.
111
112 DF_ANALYZE causes all of the defined problems to be (re)solved.  When
113 DF_ANALYZE is completes, the IN and OUT sets for each basic block
114 contain the computer information.  The DF_*_BB_INFO macros can be used
115 to access these bitvectors.  All deferred rescannings are down before
116 the transfer functions are recomputed.
117
118 DF_DUMP can then be called to dump the information produce to some
119 file.  This calls DF_DUMP_START, to print the information that is not
120 basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM
121 for each block to print the basic specific information.  These parts
122 can all be called separately as part of a larger dump function.
123
124
125 DF_FINISH_PASS causes df_remove_problem to be called on all of the
126 optional problems.  It also causes any insns whose scanning has been
127 deferred to be rescanned as well as clears all of the changeable flags.
128 Setting the pass manager TODO_df_finish flag causes this function to
129 be run.  However, the pass manager will call df_finish_pass AFTER the
130 pass dumping has been done, so if you want to see the results of the
131 optional problems in the pass dumps, use the TODO flag rather than
132 calling the function yourself.
133
134 INCREMENTAL SCANNING
135
136 There are four ways of doing the incremental scanning:
137
138 1) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,
139    df_bb_delete, df_insn_change_bb have been added to most of
140    the low level service functions that maintain the cfg and change
141    rtl.  Calling and of these routines many cause some number of insns
142    to be rescanned.
143
144    For most modern rtl passes, this is certainly the easiest way to
145    manage rescanning the insns.  This technique also has the advantage
146    that the scanning information is always correct and can be relied
147    upon even after changes have been made to the instructions.  This
148    technique is contra indicated in several cases:
149
150    a) If def-use chains OR use-def chains (but not both) are built,
151       using this is SIMPLY WRONG.  The problem is that when a ref is
152       deleted that is the target of an edge, there is not enough
153       information to efficiently find the source of the edge and
154       delete the edge.  This leaves a dangling reference that may
155       cause problems.
156
157    b) If def-use chains AND use-def chains are built, this may
158       produce unexpected results.  The problem is that the incremental
159       scanning of an insn does not know how to repair the chains that
160       point into an insn when the insn changes.  So the incremental
161       scanning just deletes the chains that enter and exit the insn
162       being changed.  The dangling reference issue in (a) is not a
163       problem here, but if the pass is depending on the chains being
164       maintained after insns have been modified, this technique will
165       not do the correct thing.
166
167    c) If the pass modifies insns several times, this incremental
168       updating may be expensive.
169
170    d) If the pass modifies all of the insns, as does register
171       allocation, it is simply better to rescan the entire function.
172
173 2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
174    df_insn_delete do not immediately change the insn but instead make
175    a note that the insn needs to be rescanned.  The next call to
176    df_analyze, df_finish_pass, or df_process_deferred_rescans will
177    cause all of the pending rescans to be processed.
178
179    This is the technique of choice if either 1a, 1b, or 1c are issues
180    in the pass.  In the case of 1a or 1b, a call to df_finish_pass
181    (either manually or via TODO_df_finish) should be made before the
182    next call to df_analyze or df_process_deferred_rescans.
183
184    This mode is also used by a few passes that still rely on note_uses,
185    note_stores and for_each_rtx instead of using the DF data.  This
186    can be said to fall under case 1c.
187
188    To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
189    (This mode can be cleared by calling df_clear_flags
190    (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
191    be rescanned.
192
193 3) Total rescanning - In this mode the rescanning is disabled.
194    Only when insns are deleted is the df information associated with
195    it also deleted.  At the end of the pass, a call must be made to
196    df_insn_rescan_all.  This method is used by the register allocator
197    since it generally changes each insn multiple times (once for each ref)
198    and does not need to make use of the updated scanning information.
199
200 4) Do it yourself - In this mechanism, the pass updates the insns
201    itself using the low level df primitives.  Currently no pass does
202    this, but it has the advantage that it is quite efficient given
203    that the pass generally has exact knowledge of what it is changing.
204
205 DATA STRUCTURES
206
207 Scanning produces a `struct df_ref' data structure (ref) is allocated
208 for every register reference (def or use) and this records the insn
209 and bb the ref is found within.  The refs are linked together in
210 chains of uses and defs for each insn and for each register.  Each ref
211 also has a chain field that links all the use refs for a def or all
212 the def refs for a use.  This is used to create use-def or def-use
213 chains.
214
215 Different optimizations have different needs.  Ultimately, only
216 register allocation and schedulers should be using the bitmaps
217 produced for the live register and uninitialized register problems.
218 The rest of the backend should be upgraded to using and maintaining
219 the linked information such as def use or use def chains.
220
221
222 PHILOSOPHY:
223
224 While incremental bitmaps are not worthwhile to maintain, incremental
225 chains may be perfectly reasonable.  The fastest way to build chains
226 from scratch or after significant modifications is to build reaching
227 definitions (RD) and build the chains from this.
228
229 However, general algorithms for maintaining use-def or def-use chains
230 are not practical.  The amount of work to recompute the chain any
231 chain after an arbitrary change is large.  However, with a modest
232 amount of work it is generally possible to have the application that
233 uses the chains keep them up to date.  The high level knowledge of
234 what is really happening is essential to crafting efficient
235 incremental algorithms.
236
237 As for the bit vector problems, there is no interface to give a set of
238 blocks over with to resolve the iteration.  In general, restarting a
239 dataflow iteration is difficult and expensive.  Again, the best way to
240 keep the dataflow information up to data (if this is really what is
241 needed) it to formulate a problem specific solution.
242
243 There are fine grained calls for creating and deleting references from
244 instructions in df-scan.c.  However, these are not currently connected
245 to the engine that resolves the dataflow equations.
246
247
248 DATA STRUCTURES:
249
250 The basic object is a DF_REF (reference) and this may either be a
251 DEF (definition) or a USE of a register.
252
253 These are linked into a variety of lists; namely reg-def, reg-use,
254 insn-def, insn-use, def-use, and use-def lists.  For example, the
255 reg-def lists contain all the locations that define a given register
256 while the insn-use lists contain all the locations that use a
257 register.
258
259 Note that the reg-def and reg-use chains are generally short for
260 pseudos and long for the hard registers.
261
262 ACCESSING INSNS:
263
264 1) The df insn information is kept in an array of DF_INSN_INFO objects.
265    The array is indexed by insn uid, and every DF_REF points to the
266    DF_INSN_INFO object of the insn that contains the reference.
267
268 2) Each insn has three sets of refs, which are linked into one of three
269    lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS,
270    DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list
271    (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or
272    DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the
273    DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
274    The latter list are the list of references in REG_EQUAL or REG_EQUIV
275    notes.  These macros produce a ref (or NULL), the rest of the list
276    can be obtained by traversal of the NEXT_REF field (accessed by the
277    DF_REF_NEXT_REF macro.)  There is no significance to the ordering of
278    the uses or refs in an instruction.
279
280 3) Each insn has a logical uid field (LUID) which is stored in the
281    DF_INSN_INFO object for the insn.  The LUID field is accessed by
282    the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros.
283    When properly set, the LUID is an integer that numbers each insn in
284    the basic block, in order from the start of the block.
285    The numbers are only correct after a call to df_analyze.  They will
286    rot after insns are added deleted or moved round.
287
288 ACCESSING REFS:
289
290 There are 4 ways to obtain access to refs:
291
292 1) References are divided into two categories, REAL and ARTIFICIAL.
293
294    REAL refs are associated with instructions.
295
296    ARTIFICIAL refs are associated with basic blocks.  The heads of
297    these lists can be accessed by calling df_get_artificial_defs or
298    df_get_artificial_uses for the particular basic block.
299
300    Artificial defs and uses occur both at the beginning and ends of blocks.
301
302      For blocks that area at the destination of eh edges, the
303      artificial uses and defs occur at the beginning.  The defs relate
304      to the registers specified in EH_RETURN_DATA_REGNO and the uses
305      relate to the registers specified in ED_USES.  Logically these
306      defs and uses should really occur along the eh edge, but there is
307      no convenient way to do this.  Artificial edges that occur at the
308      beginning of the block have the DF_REF_AT_TOP flag set.
309
310      Artificial uses occur at the end of all blocks.  These arise from
311      the hard registers that are always live, such as the stack
312      register and are put there to keep the code from forgetting about
313      them.
314
315      Artificial defs occur at the end of the entry block.  These arise
316      from registers that are live at entry to the function.
317
318 2) There are three types of refs: defs, uses and eq_uses.  (Eq_uses are
319    uses that appear inside a REG_EQUAL or REG_EQUIV note.)
320
321    All of the eq_uses, uses and defs associated with each pseudo or
322    hard register may be linked in a bidirectional chain.  These are
323    called reg-use or reg_def chains.  If the changeable flag
324    DF_EQ_NOTES is set when the chains are built, the eq_uses will be
325    treated like uses.  If it is not set they are ignored.
326
327    The first use, eq_use or def for a register can be obtained using
328    the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN
329    macros.  Subsequent uses for the same regno can be obtained by
330    following the next_reg field of the ref.  The number of elements in
331    each of the chains can be found by using the DF_REG_USE_COUNT,
332    DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.
333
334    In previous versions of this code, these chains were ordered.  It
335    has not been practical to continue this practice.
336
337 3) If def-use or use-def chains are built, these can be traversed to
338    get to other refs.  If the flag DF_EQ_NOTES has been set, the chains
339    include the eq_uses.  Otherwise these are ignored when building the
340    chains.
341
342 4) An array of all of the uses (and an array of all of the defs) can
343    be built.  These arrays are indexed by the value in the id
344    structure.  These arrays are only lazily kept up to date, and that
345    process can be expensive.  To have these arrays built, call
346    df_reorganize_defs or df_reorganize_uses.  If the flag DF_EQ_NOTES
347    has been set the array will contain the eq_uses.  Otherwise these
348    are ignored when building the array and assigning the ids.  Note
349    that the values in the id field of a ref may change across calls to
350    df_analyze or df_reorganize_defs or df_reorganize_uses.
351
352    If the only use of this array is to find all of the refs, it is
353    better to traverse all of the registers and then traverse all of
354    reg-use or reg-def chains.
355
356 NOTES:
357
358 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
359 both a use and a def.  These are both marked read/write to show that they
360 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
361 will generate a use of reg 42 followed by a def of reg 42 (both marked
362 read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
363 generates a use of reg 41 then a def of reg 41 (both marked read/write),
364 even though reg 41 is decremented before it is used for the memory
365 address in this second example.
366
367 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
368 for which the number of word_mode units covered by the outer mode is
369 smaller than that covered by the inner mode, invokes a read-modify-write
370 operation.  We generate both a use and a def and again mark them
371 read/write.
372
373 Paradoxical subreg writes do not leave a trace of the old content, so they
374 are write-only operations.
375 */
376
377
378 #include "config.h"
379 #include "system.h"
380 #include "coretypes.h"
381 #include "tm.h"
382 #include "rtl.h"
383 #include "tm_p.h"
384 #include "insn-config.h"
385 #include "recog.h"
386 #include "function.h"
387 #include "regs.h"
388 #include "output.h"
389 #include "alloc-pool.h"
390 #include "flags.h"
391 #include "hard-reg-set.h"
392 #include "basic-block.h"
393 #include "sbitmap.h"
394 #include "bitmap.h"
395 #include "timevar.h"
396 #include "df.h"
397 #include "tree-pass.h"
398 #include "params.h"
399
400 static void *df_get_bb_info (struct dataflow *, unsigned int);
401 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
402 static void df_clear_bb_info (struct dataflow *, unsigned int);
403 #ifdef DF_DEBUG_CFG
404 static void df_set_clean_cfg (void);
405 #endif
406
407 /* An obstack for bitmap not related to specific dataflow problems.
408    This obstack should e.g. be used for bitmaps with a short life time
409    such as temporary bitmaps.  */
410
411 bitmap_obstack df_bitmap_obstack;
412
413
414 /*----------------------------------------------------------------------------
415   Functions to create, destroy and manipulate an instance of df.
416 ----------------------------------------------------------------------------*/
417
418 struct df_d *df;
419
420 /* Add PROBLEM (and any dependent problems) to the DF instance.  */
421
422 void
423 df_add_problem (struct df_problem *problem)
424 {
425   struct dataflow *dflow;
426   int i;
427
428   /* First try to add the dependent problem. */
429   if (problem->dependent_problem)
430     df_add_problem (problem->dependent_problem);
431
432   /* Check to see if this problem has already been defined.  If it
433      has, just return that instance, if not, add it to the end of the
434      vector.  */
435   dflow = df->problems_by_index[problem->id];
436   if (dflow)
437     return;
438
439   /* Make a new one and add it to the end.  */
440   dflow = XCNEW (struct dataflow);
441   dflow->problem = problem;
442   dflow->computed = false;
443   dflow->solutions_dirty = true;
444   df->problems_by_index[dflow->problem->id] = dflow;
445
446   /* Keep the defined problems ordered by index.  This solves the
447      problem that RI will use the information from UREC if UREC has
448      been defined, or from LIVE if LIVE is defined and otherwise LR.
449      However for this to work, the computation of RI must be pushed
450      after which ever of those problems is defined, but we do not
451      require any of those except for LR to have actually been
452      defined.  */
453   df->num_problems_defined++;
454   for (i = df->num_problems_defined - 2; i >= 0; i--)
455     {
456       if (problem->id < df->problems_in_order[i]->problem->id)
457         df->problems_in_order[i+1] = df->problems_in_order[i];
458       else
459         {
460           df->problems_in_order[i+1] = dflow;
461           return;
462         }
463     }
464   df->problems_in_order[0] = dflow;
465 }
466
467
468 /* Set the MASK flags in the DFLOW problem.  The old flags are
469    returned.  If a flag is not allowed to be changed this will fail if
470    checking is enabled.  */
471 int
472 df_set_flags (int changeable_flags)
473 {
474   int old_flags = df->changeable_flags;
475   df->changeable_flags |= changeable_flags;
476   return old_flags;
477 }
478
479
480 /* Clear the MASK flags in the DFLOW problem.  The old flags are
481    returned.  If a flag is not allowed to be changed this will fail if
482    checking is enabled.  */
483 int
484 df_clear_flags (int changeable_flags)
485 {
486   int old_flags = df->changeable_flags;
487   df->changeable_flags &= ~changeable_flags;
488   return old_flags;
489 }
490
491
492 /* Set the blocks that are to be considered for analysis.  If this is
493    not called or is called with null, the entire function in
494    analyzed.  */
495
496 void
497 df_set_blocks (bitmap blocks)
498 {
499   if (blocks)
500     {
501       if (dump_file)
502         bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
503       if (df->blocks_to_analyze)
504         {
505           /* This block is called to change the focus from one subset
506              to another.  */
507           int p;
508           bitmap_head diff;
509           bitmap_initialize (&diff, &df_bitmap_obstack);
510           bitmap_and_compl (&diff, df->blocks_to_analyze, blocks);
511           for (p = 0; p < df->num_problems_defined; p++)
512             {
513               struct dataflow *dflow = df->problems_in_order[p];
514               if (dflow->optional_p && dflow->problem->reset_fun)
515                 dflow->problem->reset_fun (df->blocks_to_analyze);
516               else if (dflow->problem->free_blocks_on_set_blocks)
517                 {
518                   bitmap_iterator bi;
519                   unsigned int bb_index;
520
521                   EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
522                     {
523                       basic_block bb = BASIC_BLOCK (bb_index);
524                       if (bb)
525                         {
526                           void *bb_info = df_get_bb_info (dflow, bb_index);
527                           dflow->problem->free_bb_fun (bb, bb_info);
528                           df_clear_bb_info (dflow, bb_index);
529                         }
530                     }
531                 }
532             }
533
534            bitmap_clear (&diff);
535         }
536       else
537         {
538           /* This block of code is executed to change the focus from
539              the entire function to a subset.  */
540           bitmap_head blocks_to_reset;
541           bool initialized = false;
542           int p;
543           for (p = 0; p < df->num_problems_defined; p++)
544             {
545               struct dataflow *dflow = df->problems_in_order[p];
546               if (dflow->optional_p && dflow->problem->reset_fun)
547                 {
548                   if (!initialized)
549                     {
550                       basic_block bb;
551                       bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack);
552                       FOR_ALL_BB(bb)
553                         {
554                           bitmap_set_bit (&blocks_to_reset, bb->index);
555                         }
556                     }
557                   dflow->problem->reset_fun (&blocks_to_reset);
558                 }
559             }
560           if (initialized)
561             bitmap_clear (&blocks_to_reset);
562
563           df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
564         }
565       bitmap_copy (df->blocks_to_analyze, blocks);
566       df->analyze_subset = true;
567     }
568   else
569     {
570       /* This block is executed to reset the focus to the entire
571          function.  */
572       if (dump_file)
573         fprintf (dump_file, "clearing blocks_to_analyze\n");
574       if (df->blocks_to_analyze)
575         {
576           BITMAP_FREE (df->blocks_to_analyze);
577           df->blocks_to_analyze = NULL;
578         }
579       df->analyze_subset = false;
580     }
581
582   /* Setting the blocks causes the refs to be unorganized since only
583      the refs in the blocks are seen.  */
584   df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
585   df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
586   df_mark_solutions_dirty ();
587 }
588
589
590 /* Delete a DFLOW problem (and any problems that depend on this
591    problem).  */
592
593 void
594 df_remove_problem (struct dataflow *dflow)
595 {
596   struct df_problem *problem;
597   int i;
598
599   if (!dflow)
600     return;
601
602   problem = dflow->problem;
603   gcc_assert (problem->remove_problem_fun);
604
605   /* Delete any problems that depended on this problem first.  */
606   for (i = 0; i < df->num_problems_defined; i++)
607     if (df->problems_in_order[i]->problem->dependent_problem == problem)
608       df_remove_problem (df->problems_in_order[i]);
609
610   /* Now remove this problem.  */
611   for (i = 0; i < df->num_problems_defined; i++)
612     if (df->problems_in_order[i] == dflow)
613       {
614         int j;
615         for (j = i + 1; j < df->num_problems_defined; j++)
616           df->problems_in_order[j-1] = df->problems_in_order[j];
617         df->problems_in_order[j-1] = NULL;
618         df->num_problems_defined--;
619         break;
620       }
621
622   (problem->remove_problem_fun) ();
623   df->problems_by_index[problem->id] = NULL;
624 }
625
626
627 /* Remove all of the problems that are not permanent.  Scanning, LR
628    and (at -O2 or higher) LIVE are permanent, the rest are removable.
629    Also clear all of the changeable_flags.  */
630
631 void
632 df_finish_pass (bool verify ATTRIBUTE_UNUSED)
633 {
634   int i;
635   int removed = 0;
636
637 #ifdef ENABLE_DF_CHECKING
638   int saved_flags;
639 #endif
640
641   if (!df)
642     return;
643
644   df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
645   df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
646
647 #ifdef ENABLE_DF_CHECKING
648   saved_flags = df->changeable_flags;
649 #endif
650
651   for (i = 0; i < df->num_problems_defined; i++)
652     {
653       struct dataflow *dflow = df->problems_in_order[i];
654       struct df_problem *problem = dflow->problem;
655
656       if (dflow->optional_p)
657         {
658           gcc_assert (problem->remove_problem_fun);
659           (problem->remove_problem_fun) ();
660           df->problems_in_order[i] = NULL;
661           df->problems_by_index[problem->id] = NULL;
662           removed++;
663         }
664     }
665   df->num_problems_defined -= removed;
666
667   /* Clear all of the flags.  */
668   df->changeable_flags = 0;
669   df_process_deferred_rescans ();
670
671   /* Set the focus back to the whole function.  */
672   if (df->blocks_to_analyze)
673     {
674       BITMAP_FREE (df->blocks_to_analyze);
675       df->blocks_to_analyze = NULL;
676       df_mark_solutions_dirty ();
677       df->analyze_subset = false;
678     }
679
680 #ifdef ENABLE_DF_CHECKING
681   /* Verification will fail in DF_NO_INSN_RESCAN.  */
682   if (!(saved_flags & DF_NO_INSN_RESCAN))
683     {
684       df_lr_verify_transfer_functions ();
685       if (df_live)
686         df_live_verify_transfer_functions ();
687     }
688
689 #ifdef DF_DEBUG_CFG
690   df_set_clean_cfg ();
691 #endif
692 #endif
693
694 #ifdef ENABLE_CHECKING
695   if (verify)
696     df->changeable_flags |= DF_VERIFY_SCHEDULED;
697 #endif
698 }
699
700
701 /* Set up the dataflow instance for the entire back end.  */
702
703 static unsigned int
704 rest_of_handle_df_initialize (void)
705 {
706   gcc_assert (!df);
707   df = XCNEW (struct df_d);
708   df->changeable_flags = 0;
709
710   bitmap_obstack_initialize (&df_bitmap_obstack);
711
712   /* Set this to a conservative value.  Stack_ptr_mod will compute it
713      correctly later.  */
714   current_function_sp_is_unchanging = 0;
715
716   df_scan_add_problem ();
717   df_scan_alloc (NULL);
718
719   /* These three problems are permanent.  */
720   df_lr_add_problem ();
721   if (optimize > 1)
722     df_live_add_problem ();
723
724   df->postorder = XNEWVEC (int, last_basic_block);
725   df->postorder_inverted = XNEWVEC (int, last_basic_block);
726   df->n_blocks = post_order_compute (df->postorder, true, true);
727   df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
728   gcc_assert (df->n_blocks == df->n_blocks_inverted);
729
730   df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
731   memset (df->hard_regs_live_count, 0,
732           sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
733
734   df_hard_reg_init ();
735   /* After reload, some ports add certain bits to regs_ever_live so
736      this cannot be reset.  */
737   df_compute_regs_ever_live (true);
738   df_scan_blocks ();
739   df_compute_regs_ever_live (false);
740   return 0;
741 }
742
743
744 static bool
745 gate_opt (void)
746 {
747   return optimize > 0;
748 }
749
750
751 struct rtl_opt_pass pass_df_initialize_opt =
752 {
753  {
754   RTL_PASS,
755   "dfinit",                             /* name */
756   gate_opt,                             /* gate */
757   rest_of_handle_df_initialize,         /* execute */
758   NULL,                                 /* sub */
759   NULL,                                 /* next */
760   0,                                    /* static_pass_number */
761   TV_NONE,                              /* tv_id */
762   0,                                    /* properties_required */
763   0,                                    /* properties_provided */
764   0,                                    /* properties_destroyed */
765   0,                                    /* todo_flags_start */
766   0                                     /* todo_flags_finish */
767  }
768 };
769
770
771 static bool
772 gate_no_opt (void)
773 {
774   return optimize == 0;
775 }
776
777
778 struct rtl_opt_pass pass_df_initialize_no_opt =
779 {
780  {
781   RTL_PASS,
782   "no-opt dfinit",                      /* name */
783   gate_no_opt,                          /* gate */
784   rest_of_handle_df_initialize,         /* execute */
785   NULL,                                 /* sub */
786   NULL,                                 /* next */
787   0,                                    /* static_pass_number */
788   TV_NONE,                              /* tv_id */
789   0,                                    /* properties_required */
790   0,                                    /* properties_provided */
791   0,                                    /* properties_destroyed */
792   0,                                    /* todo_flags_start */
793   0                                     /* todo_flags_finish */
794  }
795 };
796
797
798 /* Free all the dataflow info and the DF structure.  This should be
799    called from the df_finish macro which also NULLs the parm.  */
800
801 static unsigned int
802 rest_of_handle_df_finish (void)
803 {
804   int i;
805
806   gcc_assert (df);
807
808   for (i = 0; i < df->num_problems_defined; i++)
809     {
810       struct dataflow *dflow = df->problems_in_order[i];
811       dflow->problem->free_fun ();
812     }
813
814   if (df->postorder)
815     free (df->postorder);
816   if (df->postorder_inverted)
817     free (df->postorder_inverted);
818   free (df->hard_regs_live_count);
819   free (df);
820   df = NULL;
821
822   bitmap_obstack_release (&df_bitmap_obstack);
823   return 0;
824 }
825
826
827 struct rtl_opt_pass pass_df_finish =
828 {
829  {
830   RTL_PASS,
831   "dfinish",                            /* name */
832   NULL,                                 /* gate */
833   rest_of_handle_df_finish,             /* execute */
834   NULL,                                 /* sub */
835   NULL,                                 /* next */
836   0,                                    /* static_pass_number */
837   TV_NONE,                              /* tv_id */
838   0,                                    /* properties_required */
839   0,                                    /* properties_provided */
840   0,                                    /* properties_destroyed */
841   0,                                    /* todo_flags_start */
842   0                                     /* todo_flags_finish */
843  }
844 };
845
846
847
848
849 \f
850 /*----------------------------------------------------------------------------
851    The general data flow analysis engine.
852 ----------------------------------------------------------------------------*/
853
854 /* Return time BB when it was visited for last time.  */
855 #define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
856
857 /* Helper function for df_worklist_dataflow.
858    Propagate the dataflow forward.
859    Given a BB_INDEX, do the dataflow propagation
860    and set bits on for successors in PENDING
861    if the out set of the dataflow has changed.
862
863    AGE specify time when BB was visited last time.
864    AGE of 0 means we are visiting for first time and need to
865    compute transfer function to initialize datastructures.
866    Otherwise we re-do transfer function only if something change
867    while computing confluence functions.
868    We need to compute confluence only of basic block that are younger
869    then last visit of the BB.
870
871    Return true if BB info has changed.  This is always the case
872    in the first visit.  */
873
874 static bool
875 df_worklist_propagate_forward (struct dataflow *dataflow,
876                                unsigned bb_index,
877                                unsigned *bbindex_to_postorder,
878                                bitmap pending,
879                                sbitmap considered,
880                                ptrdiff_t age)
881 {
882   edge e;
883   edge_iterator ei;
884   basic_block bb = BASIC_BLOCK (bb_index);
885   bool changed = !age;
886
887   /*  Calculate <conf_op> of incoming edges.  */
888   if (EDGE_COUNT (bb->preds) > 0)
889     FOR_EACH_EDGE (e, ei, bb->preds)
890       {
891         if (age <= BB_LAST_CHANGE_AGE (e->src)
892             && TEST_BIT (considered, e->src->index))
893           changed |= dataflow->problem->con_fun_n (e);
894       }
895   else if (dataflow->problem->con_fun_0)
896     dataflow->problem->con_fun_0 (bb);
897
898   if (changed
899       && dataflow->problem->trans_fun (bb_index))
900     {
901       /* The out set of this block has changed.
902          Propagate to the outgoing blocks.  */
903       FOR_EACH_EDGE (e, ei, bb->succs)
904         {
905           unsigned ob_index = e->dest->index;
906
907           if (TEST_BIT (considered, ob_index))
908             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
909         }
910       return true;
911     }
912   return false;
913 }
914
915
916 /* Helper function for df_worklist_dataflow.
917    Propagate the dataflow backward.  */
918
919 static bool
920 df_worklist_propagate_backward (struct dataflow *dataflow,
921                                 unsigned bb_index,
922                                 unsigned *bbindex_to_postorder,
923                                 bitmap pending,
924                                 sbitmap considered,
925                                 ptrdiff_t age)
926 {
927   edge e;
928   edge_iterator ei;
929   basic_block bb = BASIC_BLOCK (bb_index);
930   bool changed = !age;
931
932   /*  Calculate <conf_op> of incoming edges.  */
933   if (EDGE_COUNT (bb->succs) > 0)
934     FOR_EACH_EDGE (e, ei, bb->succs)
935       {
936         if (age <= BB_LAST_CHANGE_AGE (e->dest)
937             && TEST_BIT (considered, e->dest->index))
938           changed |= dataflow->problem->con_fun_n (e);
939       }
940   else if (dataflow->problem->con_fun_0)
941     dataflow->problem->con_fun_0 (bb);
942
943   if (changed
944       && dataflow->problem->trans_fun (bb_index))
945     {
946       /* The out set of this block has changed.
947          Propagate to the outgoing blocks.  */
948       FOR_EACH_EDGE (e, ei, bb->preds)
949         {
950           unsigned ob_index = e->src->index;
951
952           if (TEST_BIT (considered, ob_index))
953             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
954         }
955       return true;
956     }
957   return false;
958 }
959
960 /* Main dataflow solver loop.
961
962    DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
963    need to visit.
964    BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
965    BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder possition.
966    PENDING will be freed.
967
968    The worklists are bitmaps indexed by postorder positions.  
969
970    The function implements standard algorithm for dataflow solving with two
971    worklists (we are processing WORKLIST and storing new BBs to visit in
972    PENDING).
973
974    As an optimization we maintain ages when BB was changed (stored in bb->aux)
975    and when it was last visited (stored in last_visit_age).  This avoids need
976    to re-do confluence function for edges to basic blocks whose source
977    did not change since destination was visited last time.  */
978
979 static void
980 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
981                                   bitmap pending,
982                                   sbitmap considered,
983                                   int *blocks_in_postorder,
984                                   unsigned *bbindex_to_postorder,
985                                   int n_blocks)
986 {
987   enum df_flow_dir dir = dataflow->problem->dir;
988   int dcount = 0;
989   bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
990   int age = 0;
991   bool changed;
992   VEC(int, heap) *last_visit_age = NULL;
993   int prev_age;
994   basic_block bb;
995   int i;
996
997   VEC_safe_grow_cleared (int, heap, last_visit_age, n_blocks);
998
999   /* Double-queueing. Worklist is for the current iteration,
1000      and pending is for the next. */
1001   while (!bitmap_empty_p (pending))
1002     {
1003       bitmap_iterator bi;
1004       unsigned int index;
1005
1006       /* Swap pending and worklist. */
1007       bitmap temp = worklist;
1008       worklist = pending;
1009       pending = temp;
1010
1011       EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
1012         {
1013           unsigned bb_index;
1014           dcount++;
1015
1016           bitmap_clear_bit (pending, index);
1017           bb_index = blocks_in_postorder[index];
1018           bb = BASIC_BLOCK (bb_index);
1019           prev_age = VEC_index (int, last_visit_age, index);
1020           if (dir == DF_FORWARD)
1021             changed = df_worklist_propagate_forward (dataflow, bb_index,
1022                                                      bbindex_to_postorder,
1023                                                      pending, considered,
1024                                                      prev_age);
1025           else
1026             changed = df_worklist_propagate_backward (dataflow, bb_index,
1027                                                       bbindex_to_postorder,
1028                                                       pending, considered,
1029                                                       prev_age);
1030           VEC_replace (int, last_visit_age, index, ++age);
1031           if (changed)
1032             bb->aux = (void *)(ptrdiff_t)age;
1033         }
1034       bitmap_clear (worklist);
1035     }
1036   for (i = 0; i < n_blocks; i++)
1037     BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL;
1038
1039   BITMAP_FREE (worklist);
1040   BITMAP_FREE (pending);
1041   VEC_free (int, heap, last_visit_age);
1042
1043   /* Dump statistics. */
1044   if (dump_file)
1045     fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
1046              "n_basic_blocks %d n_edges %d"
1047              " count %d (%5.2g)\n",
1048              n_basic_blocks, n_edges,
1049              dcount, dcount / (float)n_basic_blocks);
1050 }
1051
1052 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
1053    with "n"-th bit representing the n-th block in the reverse-postorder order.
1054    The solver is a double-queue algorithm similar to the "double stack" solver
1055    from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1056    The only significant difference is that the worklist in this implementation
1057    is always sorted in RPO of the CFG visiting direction.  */
1058
1059 void
1060 df_worklist_dataflow (struct dataflow *dataflow,
1061                       bitmap blocks_to_consider,
1062                       int *blocks_in_postorder,
1063                       int n_blocks)
1064 {
1065   bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1066   sbitmap considered = sbitmap_alloc (last_basic_block);
1067   bitmap_iterator bi;
1068   unsigned int *bbindex_to_postorder;
1069   int i;
1070   unsigned int index;
1071   enum df_flow_dir dir = dataflow->problem->dir;
1072
1073   gcc_assert (dir != DF_NONE);
1074
1075   /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  */
1076   bbindex_to_postorder =
1077     (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
1078
1079   /* Initialize the array to an out-of-bound value.  */
1080   for (i = 0; i < last_basic_block; i++)
1081     bbindex_to_postorder[i] = last_basic_block;
1082
1083   /* Initialize the considered map.  */
1084   sbitmap_zero (considered);
1085   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1086     {
1087       SET_BIT (considered, index);
1088     }
1089
1090   /* Initialize the mapping of block index to postorder.  */
1091   for (i = 0; i < n_blocks; i++)
1092     {
1093       bbindex_to_postorder[blocks_in_postorder[i]] = i;
1094       /* Add all blocks to the worklist.  */
1095       bitmap_set_bit (pending, i);
1096     }
1097
1098   /* Initialize the problem. */
1099   if (dataflow->problem->init_fun)
1100     dataflow->problem->init_fun (blocks_to_consider);
1101
1102   /* Solve it.  */
1103   df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1104                                     blocks_in_postorder,
1105                                     bbindex_to_postorder,
1106                                     n_blocks);
1107   sbitmap_free (considered);
1108   free (bbindex_to_postorder);
1109 }
1110
1111
1112 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1113    the order of the remaining entries.  Returns the length of the resulting
1114    list.  */
1115
1116 static unsigned
1117 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1118 {
1119   unsigned act, last;
1120
1121   for (act = 0, last = 0; act < len; act++)
1122     if (bitmap_bit_p (blocks, list[act]))
1123       list[last++] = list[act];
1124
1125   return last;
1126 }
1127
1128
1129 /* Execute dataflow analysis on a single dataflow problem.
1130
1131    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1132    examined or will be computed.  For calls from DF_ANALYZE, this is
1133    the set of blocks that has been passed to DF_SET_BLOCKS.
1134 */
1135
1136 void
1137 df_analyze_problem (struct dataflow *dflow,
1138                     bitmap blocks_to_consider,
1139                     int *postorder, int n_blocks)
1140 {
1141   timevar_push (dflow->problem->tv_id);
1142
1143   /* (Re)Allocate the datastructures necessary to solve the problem.  */
1144   if (dflow->problem->alloc_fun)
1145     dflow->problem->alloc_fun (blocks_to_consider);
1146
1147 #ifdef ENABLE_DF_CHECKING
1148   if (dflow->problem->verify_start_fun)
1149     dflow->problem->verify_start_fun ();
1150 #endif
1151
1152   /* Set up the problem and compute the local information.  */
1153   if (dflow->problem->local_compute_fun)
1154     dflow->problem->local_compute_fun (blocks_to_consider);
1155
1156   /* Solve the equations.  */
1157   if (dflow->problem->dataflow_fun)
1158     dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1159                                   postorder, n_blocks);
1160
1161   /* Massage the solution.  */
1162   if (dflow->problem->finalize_fun)
1163     dflow->problem->finalize_fun (blocks_to_consider);
1164
1165 #ifdef ENABLE_DF_CHECKING
1166   if (dflow->problem->verify_end_fun)
1167     dflow->problem->verify_end_fun ();
1168 #endif
1169
1170   timevar_pop (dflow->problem->tv_id);
1171
1172   dflow->computed = true;
1173 }
1174
1175
1176 /* Analyze dataflow info for the basic blocks specified by the bitmap
1177    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
1178
1179 void
1180 df_analyze (void)
1181 {
1182   bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1183   bool everything;
1184   int i;
1185
1186   if (df->postorder)
1187     free (df->postorder);
1188   if (df->postorder_inverted)
1189     free (df->postorder_inverted);
1190   df->postorder = XNEWVEC (int, last_basic_block);
1191   df->postorder_inverted = XNEWVEC (int, last_basic_block);
1192   df->n_blocks = post_order_compute (df->postorder, true, true);
1193   df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1194
1195   /* These should be the same.  */
1196   gcc_assert (df->n_blocks == df->n_blocks_inverted);
1197
1198   /* We need to do this before the df_verify_all because this is
1199      not kept incrementally up to date.  */
1200   df_compute_regs_ever_live (false);
1201   df_process_deferred_rescans ();
1202
1203   if (dump_file)
1204     fprintf (dump_file, "df_analyze called\n");
1205
1206 #ifndef ENABLE_DF_CHECKING
1207   if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1208 #endif
1209     df_verify ();
1210
1211   for (i = 0; i < df->n_blocks; i++)
1212     bitmap_set_bit (current_all_blocks, df->postorder[i]);
1213
1214 #ifdef ENABLE_CHECKING
1215   /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1216      the ENTRY block.  */
1217   for (i = 0; i < df->n_blocks_inverted; i++)
1218     gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1219 #endif
1220
1221   /* Make sure that we have pruned any unreachable blocks from these
1222      sets.  */
1223   if (df->analyze_subset)
1224     {
1225       everything = false;
1226       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1227       df->n_blocks = df_prune_to_subcfg (df->postorder,
1228                                          df->n_blocks, df->blocks_to_analyze);
1229       df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1230                                                   df->n_blocks_inverted,
1231                                                   df->blocks_to_analyze);
1232       BITMAP_FREE (current_all_blocks);
1233     }
1234   else
1235     {
1236       everything = true;
1237       df->blocks_to_analyze = current_all_blocks;
1238       current_all_blocks = NULL;
1239     }
1240
1241   /* Skip over the DF_SCAN problem. */
1242   for (i = 1; i < df->num_problems_defined; i++)
1243     {
1244       struct dataflow *dflow = df->problems_in_order[i];
1245       if (dflow->solutions_dirty)
1246         {
1247           if (dflow->problem->dir == DF_FORWARD)
1248             df_analyze_problem (dflow,
1249                                 df->blocks_to_analyze,
1250                                 df->postorder_inverted,
1251                                 df->n_blocks_inverted);
1252           else
1253             df_analyze_problem (dflow,
1254                                 df->blocks_to_analyze,
1255                                 df->postorder,
1256                                 df->n_blocks);
1257         }
1258     }
1259
1260   if (everything)
1261     {
1262       BITMAP_FREE (df->blocks_to_analyze);
1263       df->blocks_to_analyze = NULL;
1264     }
1265
1266 #ifdef DF_DEBUG_CFG
1267   df_set_clean_cfg ();
1268 #endif
1269 }
1270
1271
1272 /* Return the number of basic blocks from the last call to df_analyze.  */
1273
1274 int
1275 df_get_n_blocks (enum df_flow_dir dir)
1276 {
1277   gcc_assert (dir != DF_NONE);
1278
1279   if (dir == DF_FORWARD)
1280     {
1281       gcc_assert (df->postorder_inverted);
1282       return df->n_blocks_inverted;
1283     }
1284
1285   gcc_assert (df->postorder);
1286   return df->n_blocks;
1287 }
1288
1289
1290 /* Return a pointer to the array of basic blocks in the reverse postorder.
1291    Depending on the direction of the dataflow problem,
1292    it returns either the usual reverse postorder array
1293    or the reverse postorder of inverted traversal. */
1294 int *
1295 df_get_postorder (enum df_flow_dir dir)
1296 {
1297   gcc_assert (dir != DF_NONE);
1298
1299   if (dir == DF_FORWARD)
1300     {
1301       gcc_assert (df->postorder_inverted);
1302       return df->postorder_inverted;
1303     }
1304   gcc_assert (df->postorder);
1305   return df->postorder;
1306 }
1307
1308 static struct df_problem user_problem;
1309 static struct dataflow user_dflow;
1310
1311 /* Interface for calling iterative dataflow with user defined
1312    confluence and transfer functions.  All that is necessary is to
1313    supply DIR, a direction, CONF_FUN_0, a confluence function for
1314    blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1315    confluence function, TRANS_FUN, the basic block transfer function,
1316    and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1317    postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1318
1319 void
1320 df_simple_dataflow (enum df_flow_dir dir,
1321                     df_init_function init_fun,
1322                     df_confluence_function_0 con_fun_0,
1323                     df_confluence_function_n con_fun_n,
1324                     df_transfer_function trans_fun,
1325                     bitmap blocks, int * postorder, int n_blocks)
1326 {
1327   memset (&user_problem, 0, sizeof (struct df_problem));
1328   user_problem.dir = dir;
1329   user_problem.init_fun = init_fun;
1330   user_problem.con_fun_0 = con_fun_0;
1331   user_problem.con_fun_n = con_fun_n;
1332   user_problem.trans_fun = trans_fun;
1333   user_dflow.problem = &user_problem;
1334   df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1335 }
1336
1337
1338 \f
1339 /*----------------------------------------------------------------------------
1340    Functions to support limited incremental change.
1341 ----------------------------------------------------------------------------*/
1342
1343
1344 /* Get basic block info.  */
1345
1346 static void *
1347 df_get_bb_info (struct dataflow *dflow, unsigned int index)
1348 {
1349   if (dflow->block_info == NULL)
1350     return NULL;
1351   if (index >= dflow->block_info_size)
1352     return NULL;
1353   return (void *)((char *)dflow->block_info
1354                   + index * dflow->problem->block_info_elt_size);
1355 }
1356
1357
1358 /* Set basic block info.  */
1359
1360 static void
1361 df_set_bb_info (struct dataflow *dflow, unsigned int index,
1362                 void *bb_info)
1363 {
1364   gcc_assert (dflow->block_info);
1365   memcpy ((char *)dflow->block_info
1366           + index * dflow->problem->block_info_elt_size,
1367           bb_info, dflow->problem->block_info_elt_size);
1368 }
1369
1370
1371 /* Clear basic block info.  */
1372
1373 static void
1374 df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1375 {
1376   gcc_assert (dflow->block_info);
1377   gcc_assert (dflow->block_info_size > index);
1378   memset ((char *)dflow->block_info
1379           + index * dflow->problem->block_info_elt_size,
1380           0, dflow->problem->block_info_elt_size);
1381 }
1382
1383
1384 /* Mark the solutions as being out of date.  */
1385
1386 void
1387 df_mark_solutions_dirty (void)
1388 {
1389   if (df)
1390     {
1391       int p;
1392       for (p = 1; p < df->num_problems_defined; p++)
1393         df->problems_in_order[p]->solutions_dirty = true;
1394     }
1395 }
1396
1397
1398 /* Return true if BB needs it's transfer functions recomputed.  */
1399
1400 bool
1401 df_get_bb_dirty (basic_block bb)
1402 {
1403   if (df && df_live)
1404     return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
1405   else
1406     return false;
1407 }
1408
1409
1410 /* Mark BB as needing it's transfer functions as being out of
1411    date.  */
1412
1413 void
1414 df_set_bb_dirty (basic_block bb)
1415 {
1416   bb->flags |= BB_MODIFIED;
1417   if (df)
1418     {
1419       int p;
1420       for (p = 1; p < df->num_problems_defined; p++)
1421         {
1422           struct dataflow *dflow = df->problems_in_order[p];
1423           if (dflow->out_of_date_transfer_functions)
1424             bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1425         }
1426       df_mark_solutions_dirty ();
1427     }
1428 }
1429
1430
1431 /* Mark BB as needing it's transfer functions as being out of
1432    date, except for LR problem.  Used when analyzing DEBUG_INSNs,
1433    as LR problem can trigger DCE, and DEBUG_INSNs shouldn't ever
1434    shorten or enlarge lifetime of regs.  */
1435
1436 void
1437 df_set_bb_dirty_nonlr (basic_block bb)
1438 {
1439   if (df)
1440     {
1441       int p;
1442       for (p = 1; p < df->num_problems_defined; p++)
1443         {
1444           struct dataflow *dflow = df->problems_in_order[p];
1445           if (dflow == df_lr)
1446             continue;
1447           if (dflow->out_of_date_transfer_functions)
1448             bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1449           dflow->solutions_dirty = true;
1450         }
1451     }
1452 }
1453
1454 /* Grow the bb_info array.  */
1455
1456 void
1457 df_grow_bb_info (struct dataflow *dflow)
1458 {
1459   unsigned int new_size = last_basic_block + 1;
1460   if (dflow->block_info_size < new_size)
1461     {
1462       new_size += new_size / 4;
1463       dflow->block_info
1464          = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1465                                new_size
1466                                * dflow->problem->block_info_elt_size);
1467       memset ((char *)dflow->block_info
1468               + dflow->block_info_size
1469               * dflow->problem->block_info_elt_size,
1470               0,
1471               (new_size - dflow->block_info_size)
1472               * dflow->problem->block_info_elt_size);
1473       dflow->block_info_size = new_size;
1474     }
1475 }
1476
1477
1478 /* Clear the dirty bits.  This is called from places that delete
1479    blocks.  */
1480 static void
1481 df_clear_bb_dirty (basic_block bb)
1482 {
1483   int p;
1484   for (p = 1; p < df->num_problems_defined; p++)
1485     {
1486       struct dataflow *dflow = df->problems_in_order[p];
1487       if (dflow->out_of_date_transfer_functions)
1488         bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1489     }
1490 }
1491
1492 /* Called from the rtl_compact_blocks to reorganize the problems basic
1493    block info.  */
1494
1495 void
1496 df_compact_blocks (void)
1497 {
1498   int i, p;
1499   basic_block bb;
1500   void *problem_temps;
1501   bitmap_head tmp;
1502
1503   bitmap_initialize (&tmp, &df_bitmap_obstack);
1504   for (p = 0; p < df->num_problems_defined; p++)
1505     {
1506       struct dataflow *dflow = df->problems_in_order[p];
1507
1508       /* Need to reorganize the out_of_date_transfer_functions for the
1509          dflow problem.  */
1510       if (dflow->out_of_date_transfer_functions)
1511         {
1512           bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
1513           bitmap_clear (dflow->out_of_date_transfer_functions);
1514           if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1515             bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1516           if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1517             bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1518
1519           i = NUM_FIXED_BLOCKS;
1520           FOR_EACH_BB (bb)
1521             {
1522               if (bitmap_bit_p (&tmp, bb->index))
1523                 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1524               i++;
1525             }
1526         }
1527
1528       /* Now shuffle the block info for the problem.  */
1529       if (dflow->problem->free_bb_fun)
1530         {
1531           int size = last_basic_block * dflow->problem->block_info_elt_size;
1532           problem_temps = XNEWVAR (char, size);
1533           df_grow_bb_info (dflow);
1534           memcpy (problem_temps, dflow->block_info, size);
1535
1536           /* Copy the bb info from the problem tmps to the proper
1537              place in the block_info vector.  Null out the copied
1538              item.  The entry and exit blocks never move.  */
1539           i = NUM_FIXED_BLOCKS;
1540           FOR_EACH_BB (bb)
1541             {
1542               df_set_bb_info (dflow, i,
1543                               (char *)problem_temps
1544                               + bb->index * dflow->problem->block_info_elt_size);
1545               i++;
1546             }
1547           memset ((char *)dflow->block_info
1548                   + i * dflow->problem->block_info_elt_size, 0,
1549                   (last_basic_block - i)
1550                   * dflow->problem->block_info_elt_size);
1551           free (problem_temps);
1552         }
1553     }
1554
1555   /* Shuffle the bits in the basic_block indexed arrays.  */
1556
1557   if (df->blocks_to_analyze)
1558     {
1559       if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1560         bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1561       if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1562         bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1563       bitmap_copy (&tmp, df->blocks_to_analyze);
1564       bitmap_clear (df->blocks_to_analyze);
1565       i = NUM_FIXED_BLOCKS;
1566       FOR_EACH_BB (bb)
1567         {
1568           if (bitmap_bit_p (&tmp, bb->index))
1569             bitmap_set_bit (df->blocks_to_analyze, i);
1570           i++;
1571         }
1572     }
1573
1574   bitmap_clear (&tmp);
1575
1576   i = NUM_FIXED_BLOCKS;
1577   FOR_EACH_BB (bb)
1578     {
1579       SET_BASIC_BLOCK (i, bb);
1580       bb->index = i;
1581       i++;
1582     }
1583
1584   gcc_assert (i == n_basic_blocks);
1585
1586   for (; i < last_basic_block; i++)
1587     SET_BASIC_BLOCK (i, NULL);
1588
1589 #ifdef DF_DEBUG_CFG
1590   if (!df_lr->solutions_dirty)
1591     df_set_clean_cfg ();
1592 #endif
1593 }
1594
1595
1596 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
1597    block.  There is no excuse for people to do this kind of thing.  */
1598
1599 void
1600 df_bb_replace (int old_index, basic_block new_block)
1601 {
1602   int new_block_index = new_block->index;
1603   int p;
1604
1605   if (dump_file)
1606     fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1607
1608   gcc_assert (df);
1609   gcc_assert (BASIC_BLOCK (old_index) == NULL);
1610
1611   for (p = 0; p < df->num_problems_defined; p++)
1612     {
1613       struct dataflow *dflow = df->problems_in_order[p];
1614       if (dflow->block_info)
1615         {
1616           df_grow_bb_info (dflow);
1617           df_set_bb_info (dflow, old_index,
1618                           df_get_bb_info (dflow, new_block_index));
1619         }
1620     }
1621
1622   df_clear_bb_dirty (new_block);
1623   SET_BASIC_BLOCK (old_index, new_block);
1624   new_block->index = old_index;
1625   df_set_bb_dirty (BASIC_BLOCK (old_index));
1626   SET_BASIC_BLOCK (new_block_index, NULL);
1627 }
1628
1629
1630 /* Free all of the per basic block dataflow from all of the problems.
1631    This is typically called before a basic block is deleted and the
1632    problem will be reanalyzed.  */
1633
1634 void
1635 df_bb_delete (int bb_index)
1636 {
1637   basic_block bb = BASIC_BLOCK (bb_index);
1638   int i;
1639
1640   if (!df)
1641     return;
1642
1643   for (i = 0; i < df->num_problems_defined; i++)
1644     {
1645       struct dataflow *dflow = df->problems_in_order[i];
1646       if (dflow->problem->free_bb_fun)
1647         {
1648           void *bb_info = df_get_bb_info (dflow, bb_index);
1649           if (bb_info)
1650             {
1651               dflow->problem->free_bb_fun (bb, bb_info);
1652               df_clear_bb_info (dflow, bb_index);
1653             }
1654         }
1655     }
1656   df_clear_bb_dirty (bb);
1657   df_mark_solutions_dirty ();
1658 }
1659
1660
1661 /* Verify that there is a place for everything and everything is in
1662    its place.  This is too expensive to run after every pass in the
1663    mainline.  However this is an excellent debugging tool if the
1664    dataflow information is not being updated properly.  You can just
1665    sprinkle calls in until you find the place that is changing an
1666    underlying structure without calling the proper updating
1667    routine.  */
1668
1669 void
1670 df_verify (void)
1671 {
1672   df_scan_verify ();
1673 #ifdef ENABLE_DF_CHECKING
1674   df_lr_verify_transfer_functions ();
1675   if (df_live)
1676     df_live_verify_transfer_functions ();
1677 #endif
1678 }
1679
1680 #ifdef DF_DEBUG_CFG
1681
1682 /* Compute an array of ints that describes the cfg.  This can be used
1683    to discover places where the cfg is modified by the appropriate
1684    calls have not been made to the keep df informed.  The internals of
1685    this are unexciting, the key is that two instances of this can be
1686    compared to see if any changes have been made to the cfg.  */
1687
1688 static int *
1689 df_compute_cfg_image (void)
1690 {
1691   basic_block bb;
1692   int size = 2 + (2 * n_basic_blocks);
1693   int i;
1694   int * map;
1695
1696   FOR_ALL_BB (bb)
1697     {
1698       size += EDGE_COUNT (bb->succs);
1699     }
1700
1701   map = XNEWVEC (int, size);
1702   map[0] = size;
1703   i = 1;
1704   FOR_ALL_BB (bb)
1705     {
1706       edge_iterator ei;
1707       edge e;
1708
1709       map[i++] = bb->index;
1710       FOR_EACH_EDGE (e, ei, bb->succs)
1711         map[i++] = e->dest->index;
1712       map[i++] = -1;
1713     }
1714   map[i] = -1;
1715   return map;
1716 }
1717
1718 static int *saved_cfg = NULL;
1719
1720
1721 /* This function compares the saved version of the cfg with the
1722    current cfg and aborts if the two are identical.  The function
1723    silently returns if the cfg has been marked as dirty or the two are
1724    the same.  */
1725
1726 void
1727 df_check_cfg_clean (void)
1728 {
1729   int *new_map;
1730
1731   if (!df)
1732     return;
1733
1734   if (df_lr->solutions_dirty)
1735     return;
1736
1737   if (saved_cfg == NULL)
1738     return;
1739
1740   new_map = df_compute_cfg_image ();
1741   gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1742   free (new_map);
1743 }
1744
1745
1746 /* This function builds a cfg fingerprint and squirrels it away in
1747    saved_cfg.  */
1748
1749 static void
1750 df_set_clean_cfg (void)
1751 {
1752   if (saved_cfg)
1753     free (saved_cfg);
1754   saved_cfg = df_compute_cfg_image ();
1755 }
1756
1757 #endif /* DF_DEBUG_CFG  */
1758 /*----------------------------------------------------------------------------
1759    PUBLIC INTERFACES TO QUERY INFORMATION.
1760 ----------------------------------------------------------------------------*/
1761
1762
1763 /* Return first def of REGNO within BB.  */
1764
1765 df_ref
1766 df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1767 {
1768   rtx insn;
1769   df_ref *def_rec;
1770   unsigned int uid;
1771
1772   FOR_BB_INSNS (bb, insn)
1773     {
1774       if (!INSN_P (insn))
1775         continue;
1776
1777       uid = INSN_UID (insn);
1778       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1779         {
1780           df_ref def = *def_rec;
1781           if (DF_REF_REGNO (def) == regno)
1782             return def;
1783         }
1784     }
1785   return NULL;
1786 }
1787
1788
1789 /* Return last def of REGNO within BB.  */
1790
1791 df_ref
1792 df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1793 {
1794   rtx insn;
1795   df_ref *def_rec;
1796   unsigned int uid;
1797
1798   FOR_BB_INSNS_REVERSE (bb, insn)
1799     {
1800       if (!INSN_P (insn))
1801         continue;
1802
1803       uid = INSN_UID (insn);
1804       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1805         {
1806           df_ref def = *def_rec;
1807           if (DF_REF_REGNO (def) == regno)
1808             return def;
1809         }
1810     }
1811
1812   return NULL;
1813 }
1814
1815 /* Finds the reference corresponding to the definition of REG in INSN.
1816    DF is the dataflow object.  */
1817
1818 df_ref
1819 df_find_def (rtx insn, rtx reg)
1820 {
1821   unsigned int uid;
1822   df_ref *def_rec;
1823
1824   if (GET_CODE (reg) == SUBREG)
1825     reg = SUBREG_REG (reg);
1826   gcc_assert (REG_P (reg));
1827
1828   uid = INSN_UID (insn);
1829   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1830     {
1831       df_ref def = *def_rec;
1832       if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1833         return def;
1834     }
1835
1836   return NULL;
1837 }
1838
1839
1840 /* Return true if REG is defined in INSN, zero otherwise.  */
1841
1842 bool
1843 df_reg_defined (rtx insn, rtx reg)
1844 {
1845   return df_find_def (insn, reg) != NULL;
1846 }
1847
1848
1849 /* Finds the reference corresponding to the use of REG in INSN.
1850    DF is the dataflow object.  */
1851
1852 df_ref
1853 df_find_use (rtx insn, rtx reg)
1854 {
1855   unsigned int uid;
1856   df_ref *use_rec;
1857
1858   if (GET_CODE (reg) == SUBREG)
1859     reg = SUBREG_REG (reg);
1860   gcc_assert (REG_P (reg));
1861
1862   uid = INSN_UID (insn);
1863   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1864     {
1865       df_ref use = *use_rec;
1866       if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1867         return use;
1868     }
1869   if (df->changeable_flags & DF_EQ_NOTES)
1870     for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1871       {
1872         df_ref use = *use_rec;
1873         if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1874           return use;
1875       }
1876   return NULL;
1877 }
1878
1879
1880 /* Return true if REG is referenced in INSN, zero otherwise.  */
1881
1882 bool
1883 df_reg_used (rtx insn, rtx reg)
1884 {
1885   return df_find_use (insn, reg) != NULL;
1886 }
1887
1888 \f
1889 /*----------------------------------------------------------------------------
1890    Debugging and printing functions.
1891 ----------------------------------------------------------------------------*/
1892
1893
1894 /* Write information about registers and basic blocks into FILE.
1895    This is part of making a debugging dump.  */
1896
1897 void
1898 df_print_regset (FILE *file, bitmap r)
1899 {
1900   unsigned int i;
1901   bitmap_iterator bi;
1902
1903   if (r == NULL)
1904     fputs (" (nil)", file);
1905   else
1906     {
1907       EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1908         {
1909           fprintf (file, " %d", i);
1910           if (i < FIRST_PSEUDO_REGISTER)
1911             fprintf (file, " [%s]", reg_names[i]);
1912         }
1913     }
1914   fprintf (file, "\n");
1915 }
1916
1917
1918 /* Write information about registers and basic blocks into FILE.  The
1919    bitmap is in the form used by df_byte_lr.  This is part of making a
1920    debugging dump.  */
1921
1922 void
1923 df_print_word_regset (FILE *file, bitmap r)
1924 {
1925   unsigned int max_reg = max_reg_num ();
1926
1927   if (r == NULL)
1928     fputs (" (nil)", file);
1929   else
1930     {
1931       unsigned int i;
1932       for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
1933         {
1934           bool found = (bitmap_bit_p (r, 2 * i)
1935                         || bitmap_bit_p (r, 2 * i + 1));
1936           if (found)
1937             {
1938               int word;
1939               const char * sep = "";
1940               fprintf (file, " %d", i);
1941               fprintf (file, "(");
1942               for (word = 0; word < 2; word++)
1943                 if (bitmap_bit_p (r, 2 * i + word))
1944                   {
1945                     fprintf (file, "%s%d", sep, word);
1946                     sep = ", ";
1947                   }
1948               fprintf (file, ")");
1949             }
1950         }
1951     }
1952   fprintf (file, "\n");
1953 }
1954
1955
1956 /* Dump dataflow info.  */
1957
1958 void
1959 df_dump (FILE *file)
1960 {
1961   basic_block bb;
1962   df_dump_start (file);
1963
1964   FOR_ALL_BB (bb)
1965     {
1966       df_print_bb_index (bb, file);
1967       df_dump_top (bb, file);
1968       df_dump_bottom (bb, file);
1969     }
1970
1971   fprintf (file, "\n");
1972 }
1973
1974
1975 /* Dump dataflow info for df->blocks_to_analyze.  */
1976
1977 void
1978 df_dump_region (FILE *file)
1979 {
1980   if (df->blocks_to_analyze)
1981     {
1982       bitmap_iterator bi;
1983       unsigned int bb_index;
1984
1985       fprintf (file, "\n\nstarting region dump\n");
1986       df_dump_start (file);
1987
1988       EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1989         {
1990           basic_block bb = BASIC_BLOCK (bb_index);
1991
1992           df_print_bb_index (bb, file);
1993           df_dump_top (bb, file);
1994           df_dump_bottom (bb, file);
1995         }
1996       fprintf (file, "\n");
1997     }
1998   else
1999     df_dump (file);
2000 }
2001
2002
2003 /* Dump the introductory information for each problem defined.  */
2004
2005 void
2006 df_dump_start (FILE *file)
2007 {
2008   int i;
2009
2010   if (!df || !file)
2011     return;
2012
2013   fprintf (file, "\n\n%s\n", current_function_name ());
2014   fprintf (file, "\nDataflow summary:\n");
2015   if (df->blocks_to_analyze)
2016     fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
2017              DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
2018
2019   for (i = 0; i < df->num_problems_defined; i++)
2020     {
2021       struct dataflow *dflow = df->problems_in_order[i];
2022       if (dflow->computed)
2023         {
2024           df_dump_problem_function fun = dflow->problem->dump_start_fun;
2025           if (fun)
2026             fun(file);
2027         }
2028     }
2029 }
2030
2031
2032 /* Dump the top of the block information for BB.  */
2033
2034 void
2035 df_dump_top (basic_block bb, FILE *file)
2036 {
2037   int i;
2038
2039   if (!df || !file)
2040     return;
2041
2042   for (i = 0; i < df->num_problems_defined; i++)
2043     {
2044       struct dataflow *dflow = df->problems_in_order[i];
2045       if (dflow->computed)
2046         {
2047           df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
2048           if (bbfun)
2049             bbfun (bb, file);
2050         }
2051     }
2052 }
2053
2054
2055 /* Dump the bottom of the block information for BB.  */
2056
2057 void
2058 df_dump_bottom (basic_block bb, FILE *file)
2059 {
2060   int i;
2061
2062   if (!df || !file)
2063     return;
2064
2065   for (i = 0; i < df->num_problems_defined; i++)
2066     {
2067       struct dataflow *dflow = df->problems_in_order[i];
2068       if (dflow->computed)
2069         {
2070           df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
2071           if (bbfun)
2072             bbfun (bb, file);
2073         }
2074     }
2075 }
2076
2077
2078 void
2079 df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
2080 {
2081   fprintf (file, "{ ");
2082   while (*ref_rec)
2083     {
2084       df_ref ref = *ref_rec;
2085       fprintf (file, "%c%d(%d)",
2086                DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2087                DF_REF_ID (ref),
2088                DF_REF_REGNO (ref));
2089       if (follow_chain)
2090         df_chain_dump (DF_REF_CHAIN (ref), file);
2091       ref_rec++;
2092     }
2093   fprintf (file, "}");
2094 }
2095
2096
2097 /* Dump either a ref-def or reg-use chain.  */
2098
2099 void
2100 df_regs_chain_dump (df_ref ref,  FILE *file)
2101 {
2102   fprintf (file, "{ ");
2103   while (ref)
2104     {
2105       fprintf (file, "%c%d(%d) ",
2106                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2107                DF_REF_ID (ref),
2108                DF_REF_REGNO (ref));
2109       ref = DF_REF_NEXT_REG (ref);
2110     }
2111   fprintf (file, "}");
2112 }
2113
2114
2115 static void
2116 df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
2117 {
2118   while (*mws)
2119     {
2120       fprintf (file, "mw %c r[%d..%d]\n",
2121                (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
2122                (*mws)->start_regno, (*mws)->end_regno);
2123       mws++;
2124     }
2125 }
2126
2127
2128 static void
2129 df_insn_uid_debug (unsigned int uid,
2130                    bool follow_chain, FILE *file)
2131 {
2132   fprintf (file, "insn %d luid %d",
2133            uid, DF_INSN_UID_LUID (uid));
2134
2135   if (DF_INSN_UID_DEFS (uid))
2136     {
2137       fprintf (file, " defs ");
2138       df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2139     }
2140
2141   if (DF_INSN_UID_USES (uid))
2142     {
2143       fprintf (file, " uses ");
2144       df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2145     }
2146
2147   if (DF_INSN_UID_EQ_USES (uid))
2148     {
2149       fprintf (file, " eq uses ");
2150       df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2151     }
2152
2153   if (DF_INSN_UID_MWS (uid))
2154     {
2155       fprintf (file, " mws ");
2156       df_mws_dump (DF_INSN_UID_MWS (uid), file);
2157     }
2158   fprintf (file, "\n");
2159 }
2160
2161
2162 DEBUG_FUNCTION void
2163 df_insn_debug (rtx insn, bool follow_chain, FILE *file)
2164 {
2165   df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2166 }
2167
2168 DEBUG_FUNCTION void
2169 df_insn_debug_regno (rtx insn, FILE *file)
2170 {
2171   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2172
2173   fprintf (file, "insn %d bb %d luid %d defs ",
2174            INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2175            DF_INSN_INFO_LUID (insn_info));
2176   df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2177
2178   fprintf (file, " uses ");
2179   df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2180
2181   fprintf (file, " eq_uses ");
2182   df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2183   fprintf (file, "\n");
2184 }
2185
2186 DEBUG_FUNCTION void
2187 df_regno_debug (unsigned int regno, FILE *file)
2188 {
2189   fprintf (file, "reg %d defs ", regno);
2190   df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2191   fprintf (file, " uses ");
2192   df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2193   fprintf (file, " eq_uses ");
2194   df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2195   fprintf (file, "\n");
2196 }
2197
2198
2199 DEBUG_FUNCTION void
2200 df_ref_debug (df_ref ref, FILE *file)
2201 {
2202   fprintf (file, "%c%d ",
2203            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2204            DF_REF_ID (ref));
2205   fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ",
2206            DF_REF_REGNO (ref),
2207            DF_REF_BBNO (ref),
2208            DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2209            DF_REF_FLAGS (ref),
2210            DF_REF_TYPE (ref));
2211   if (DF_REF_LOC (ref))
2212     {
2213       if (flag_dump_noaddr)
2214         fprintf (file, "loc #(#) chain ");
2215       else
2216         fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2217                  (void *)*DF_REF_LOC (ref));
2218     }
2219   else
2220     fprintf (file, "chain ");
2221   df_chain_dump (DF_REF_CHAIN (ref), file);
2222   fprintf (file, "\n");
2223 }
2224 \f
2225 /* Functions for debugging from GDB.  */
2226
2227 DEBUG_FUNCTION void
2228 debug_df_insn (rtx insn)
2229 {
2230   df_insn_debug (insn, true, stderr);
2231   debug_rtx (insn);
2232 }
2233
2234
2235 DEBUG_FUNCTION void
2236 debug_df_reg (rtx reg)
2237 {
2238   df_regno_debug (REGNO (reg), stderr);
2239 }
2240
2241
2242 DEBUG_FUNCTION void
2243 debug_df_regno (unsigned int regno)
2244 {
2245   df_regno_debug (regno, stderr);
2246 }
2247
2248
2249 DEBUG_FUNCTION void
2250 debug_df_ref (df_ref ref)
2251 {
2252   df_ref_debug (ref, stderr);
2253 }
2254
2255
2256 DEBUG_FUNCTION void
2257 debug_df_defno (unsigned int defno)
2258 {
2259   df_ref_debug (DF_DEFS_GET (defno), stderr);
2260 }
2261
2262
2263 DEBUG_FUNCTION void
2264 debug_df_useno (unsigned int defno)
2265 {
2266   df_ref_debug (DF_USES_GET (defno), stderr);
2267 }
2268
2269
2270 DEBUG_FUNCTION void
2271 debug_df_chain (struct df_link *link)
2272 {
2273   df_chain_dump (link, stderr);
2274   fputc ('\n', stderr);
2275 }