OSDN Git Service

c42b20f2ce70a2c6df942962b9daad18200b6f7a
[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 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 #ifdef DF_DEBUG_CFG
403 static void df_set_clean_cfg (void);
404 #endif
405
406 /* An obstack for bitmap not related to specific dataflow problems.
407    This obstack should e.g. be used for bitmaps with a short life time
408    such as temporary bitmaps.  */
409
410 bitmap_obstack df_bitmap_obstack;
411
412
413 /*----------------------------------------------------------------------------
414   Functions to create, destroy and manipulate an instance of df.
415 ----------------------------------------------------------------------------*/
416
417 struct df *df;
418
419 /* Add PROBLEM (and any dependent problems) to the DF instance.  */
420
421 void
422 df_add_problem (struct df_problem *problem)
423 {
424   struct dataflow *dflow;
425   int i;
426
427   /* First try to add the dependent problem. */
428   if (problem->dependent_problem)
429     df_add_problem (problem->dependent_problem);
430
431   /* Check to see if this problem has already been defined.  If it
432      has, just return that instance, if not, add it to the end of the
433      vector.  */
434   dflow = df->problems_by_index[problem->id];
435   if (dflow)
436     return;
437
438   /* Make a new one and add it to the end.  */
439   dflow = XCNEW (struct dataflow);
440   dflow->problem = problem;
441   dflow->computed = false;
442   dflow->solutions_dirty = true;
443   df->problems_by_index[dflow->problem->id] = dflow;
444
445   /* Keep the defined problems ordered by index.  This solves the
446      problem that RI will use the information from UREC if UREC has
447      been defined, or from LIVE if LIVE is defined and otherwise LR.
448      However for this to work, the computation of RI must be pushed
449      after which ever of those problems is defined, but we do not
450      require any of those except for LR to have actually been
451      defined.  */ 
452   df->num_problems_defined++;
453   for (i = df->num_problems_defined - 2; i >= 0; i--)
454     {
455       if (problem->id < df->problems_in_order[i]->problem->id)
456         df->problems_in_order[i+1] = df->problems_in_order[i];
457       else
458         {
459           df->problems_in_order[i+1] = dflow;
460           return;
461         }
462     }
463   df->problems_in_order[0] = dflow;
464 }
465
466
467 /* Set the MASK flags in the DFLOW problem.  The old flags are
468    returned.  If a flag is not allowed to be changed this will fail if
469    checking is enabled.  */
470 int
471 df_set_flags (int changeable_flags)
472 {
473   int old_flags = df->changeable_flags;
474   df->changeable_flags |= changeable_flags;
475   return old_flags;
476 }
477
478
479 /* Clear the MASK flags in the DFLOW problem.  The old flags are
480    returned.  If a flag is not allowed to be changed this will fail if
481    checking is enabled.  */
482 int
483 df_clear_flags (int changeable_flags)
484 {
485   int old_flags = df->changeable_flags;
486   df->changeable_flags &= ~changeable_flags;
487   return old_flags;
488 }
489
490
491 /* Set the blocks that are to be considered for analysis.  If this is
492    not called or is called with null, the entire function in
493    analyzed.  */
494
495 void 
496 df_set_blocks (bitmap blocks)
497 {
498   if (blocks)
499     {
500       if (dump_file)
501         bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
502       if (df->blocks_to_analyze)
503         {
504           /* This block is called to change the focus from one subset
505              to another.  */
506           int p;
507           bitmap diff = BITMAP_ALLOC (&df_bitmap_obstack);
508           bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
509           for (p = 0; p < df->num_problems_defined; p++)
510             {
511               struct dataflow *dflow = df->problems_in_order[p];
512               if (dflow->optional_p && dflow->problem->reset_fun)
513                 dflow->problem->reset_fun (df->blocks_to_analyze);
514               else if (dflow->problem->free_blocks_on_set_blocks)
515                 {
516                   bitmap_iterator bi;
517                   unsigned int bb_index;
518                   
519                   EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
520                     {
521                       basic_block bb = BASIC_BLOCK (bb_index);
522                       if (bb)
523                         {
524                           void *bb_info = df_get_bb_info (dflow, bb_index);
525                           if (bb_info)
526                             {
527                               dflow->problem->free_bb_fun (bb, bb_info);
528                               df_set_bb_info (dflow, bb_index, NULL);
529                             }
530                         }
531                     }
532                 }
533             }
534
535           BITMAP_FREE (diff);
536         }
537       else
538         {
539           /* This block of code is executed to change the focus from
540              the entire function to a subset.  */
541           bitmap blocks_to_reset = NULL;
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 (!blocks_to_reset)
549                     {
550                       basic_block bb;
551                       blocks_to_reset =
552                         BITMAP_ALLOC (&df_bitmap_obstack);
553                       FOR_ALL_BB(bb)
554                         {
555                           bitmap_set_bit (blocks_to_reset, bb->index); 
556                         }
557                     }
558                   dflow->problem->reset_fun (blocks_to_reset);
559                 }
560             }
561           if (blocks_to_reset)
562             BITMAP_FREE (blocks_to_reset);
563
564           df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
565         }
566       bitmap_copy (df->blocks_to_analyze, blocks);
567       df->analyze_subset = true;
568     }
569   else
570     {
571       /* This block is executed to reset the focus to the entire
572          function.  */
573       if (dump_file)
574         fprintf (dump_file, "clearing blocks_to_analyze\n");
575       if (df->blocks_to_analyze)
576         {
577           BITMAP_FREE (df->blocks_to_analyze);
578           df->blocks_to_analyze = NULL;
579         }
580       df->analyze_subset = false;
581     }
582
583   /* Setting the blocks causes the refs to be unorganized since only
584      the refs in the blocks are seen.  */
585   df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
586   df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
587   df_mark_solutions_dirty ();
588 }
589
590
591 /* Delete a DFLOW problem (and any problems that depend on this
592    problem).  */
593
594 void
595 df_remove_problem (struct dataflow *dflow)
596 {
597   struct df_problem *problem;
598   int i;
599
600   if (!dflow)
601     return;
602
603   problem = dflow->problem;
604   gcc_assert (problem->remove_problem_fun);
605
606   /* Delete any problems that depended on this problem first.  */
607   for (i = 0; i < df->num_problems_defined; i++)
608     if (df->problems_in_order[i]->problem->dependent_problem == problem)
609       df_remove_problem (df->problems_in_order[i]);
610
611   /* Now remove this problem.  */
612   for (i = 0; i < df->num_problems_defined; i++)
613     if (df->problems_in_order[i] == dflow)
614       {
615         int j;
616         for (j = i + 1; j < df->num_problems_defined; j++)
617           df->problems_in_order[j-1] = df->problems_in_order[j];
618         df->problems_in_order[j-1] = NULL;
619         df->num_problems_defined--;
620         break;
621       }
622
623   (problem->remove_problem_fun) ();
624   df->problems_by_index[problem->id] = NULL;
625 }
626
627
628 /* Remove all of the problems that are not permanent.  Scanning, LR
629    and (at -O2 or higher) LIVE are permanent, the rest are removable.
630    Also clear all of the changeable_flags.  */
631
632 void
633 df_finish_pass (bool verify ATTRIBUTE_UNUSED)
634 {
635   int i;
636   int removed = 0;
637
638 #ifdef ENABLE_DF_CHECKING
639   enum df_changeable_flags saved_flags;
640 #endif
641
642   if (!df)
643     return;
644
645   df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
646   df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
647
648 #ifdef ENABLE_DF_CHECKING
649   saved_flags = df->changeable_flags;
650 #endif
651
652   for (i = 0; i < df->num_problems_defined; i++)
653     {
654       struct dataflow *dflow = df->problems_in_order[i];
655       struct df_problem *problem = dflow->problem;
656
657       if (dflow->optional_p)
658         {
659           gcc_assert (problem->remove_problem_fun);
660           (problem->remove_problem_fun) ();
661           df->problems_in_order[i] = NULL;
662           df->problems_by_index[problem->id] = NULL;
663           removed++;
664         }
665     }
666   df->num_problems_defined -= removed;
667
668   /* Clear all of the flags.  */
669   df->changeable_flags = 0;
670   df_process_deferred_rescans ();
671
672   /* Set the focus back to the whole function.  */
673   if (df->blocks_to_analyze)
674     {
675       BITMAP_FREE (df->blocks_to_analyze);
676       df->blocks_to_analyze = NULL;
677       df_mark_solutions_dirty ();
678       df->analyze_subset = false;
679     }
680
681 #ifdef ENABLE_DF_CHECKING
682   /* Verification will fail in DF_NO_INSN_RESCAN.  */
683   if (!(saved_flags & DF_NO_INSN_RESCAN))
684     {
685       df_lr_verify_transfer_functions ();
686       if (df_live)
687         df_live_verify_transfer_functions ();
688     }
689
690 #ifdef DF_DEBUG_CFG
691   df_set_clean_cfg ();
692 #endif
693 #endif
694
695 #ifdef ENABLE_CHECKING
696   if (verify)
697     df->changeable_flags |= DF_VERIFY_SCHEDULED;
698 #endif
699 }
700
701
702 /* Set up the dataflow instance for the entire back end.  */
703
704 static unsigned int
705 rest_of_handle_df_initialize (void)
706 {
707   gcc_assert (!df);
708   df = XCNEW (struct df);
709   df->changeable_flags = 0;
710
711   bitmap_obstack_initialize (&df_bitmap_obstack);
712
713   /* Set this to a conservative value.  Stack_ptr_mod will compute it
714      correctly later.  */
715   current_function_sp_is_unchanging = 0;
716
717   df_scan_add_problem ();
718   df_scan_alloc (NULL);
719
720   /* These three problems are permanent.  */
721   df_lr_add_problem ();
722   if (optimize > 1)
723     df_live_add_problem ();
724
725   df->postorder = XNEWVEC (int, last_basic_block);
726   df->postorder_inverted = XNEWVEC (int, last_basic_block);
727   df->n_blocks = post_order_compute (df->postorder, true, true);
728   df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
729   gcc_assert (df->n_blocks == df->n_blocks_inverted);
730
731   df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
732   memset (df->hard_regs_live_count, 0, 
733           sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
734
735   df_hard_reg_init ();
736   /* After reload, some ports add certain bits to regs_ever_live so
737      this cannot be reset.  */
738   df_compute_regs_ever_live (true);
739   df_scan_blocks ();
740   df_compute_regs_ever_live (false);
741   return 0;
742 }
743
744
745 static bool
746 gate_opt (void)
747 {
748   return optimize > 0;
749 }
750
751
752 struct rtl_opt_pass pass_df_initialize_opt =
753 {
754  {
755   RTL_PASS,
756   "dfinit",                             /* name */
757   gate_opt,                             /* gate */
758   rest_of_handle_df_initialize,         /* execute */
759   NULL,                                 /* sub */
760   NULL,                                 /* next */
761   0,                                    /* static_pass_number */
762   TV_NONE,                              /* tv_id */
763   0,                                    /* properties_required */
764   0,                                    /* properties_provided */
765   0,                                    /* properties_destroyed */
766   0,                                    /* todo_flags_start */
767   0                                     /* todo_flags_finish */
768  }
769 };
770
771
772 static bool
773 gate_no_opt (void)
774 {
775   return optimize == 0;
776 }
777
778
779 struct rtl_opt_pass pass_df_initialize_no_opt =
780 {
781  {
782   RTL_PASS,
783   "dfinit",                             /* name */
784   gate_no_opt,                          /* gate */
785   rest_of_handle_df_initialize,         /* execute */
786   NULL,                                 /* sub */
787   NULL,                                 /* next */
788   0,                                    /* static_pass_number */
789   TV_NONE,                              /* tv_id */
790   0,                                    /* properties_required */
791   0,                                    /* properties_provided */
792   0,                                    /* properties_destroyed */
793   0,                                    /* todo_flags_start */
794   0                                     /* todo_flags_finish */
795  }
796 };
797
798
799 /* Free all the dataflow info and the DF structure.  This should be
800    called from the df_finish macro which also NULLs the parm.  */
801
802 static unsigned int
803 rest_of_handle_df_finish (void)
804 {
805   int i;
806
807   gcc_assert (df);
808
809   for (i = 0; i < df->num_problems_defined; i++)
810     {
811       struct dataflow *dflow = df->problems_in_order[i];
812       dflow->problem->free_fun (); 
813     }
814
815   if (df->postorder)
816     free (df->postorder);
817   if (df->postorder_inverted)
818     free (df->postorder_inverted);
819   free (df->hard_regs_live_count);
820   free (df);
821   df = NULL;
822
823   bitmap_obstack_release (&df_bitmap_obstack);
824   return 0;
825 }
826
827
828 struct rtl_opt_pass pass_df_finish =
829 {
830  {
831   RTL_PASS,
832   "dfinish",                            /* name */
833   NULL,                                 /* gate */
834   rest_of_handle_df_finish,             /* execute */
835   NULL,                                 /* sub */
836   NULL,                                 /* next */
837   0,                                    /* static_pass_number */
838   TV_NONE,                              /* tv_id */
839   0,                                    /* properties_required */
840   0,                                    /* properties_provided */
841   0,                                    /* properties_destroyed */
842   0,                                    /* todo_flags_start */
843   0                                     /* todo_flags_finish */
844  }
845 };
846
847
848
849
850 \f
851 /*----------------------------------------------------------------------------
852    The general data flow analysis engine.
853 ----------------------------------------------------------------------------*/
854
855
856 /* Helper function for df_worklist_dataflow.
857    Propagate the dataflow forward. 
858    Given a BB_INDEX, do the dataflow propagation
859    and set bits on for successors in PENDING
860    if the out set of the dataflow has changed. */
861
862 static void
863 df_worklist_propagate_forward (struct dataflow *dataflow,
864                                unsigned bb_index,
865                                unsigned *bbindex_to_postorder,
866                                bitmap pending,
867                                sbitmap considered)
868 {
869   edge e;
870   edge_iterator ei;
871   basic_block bb = BASIC_BLOCK (bb_index);
872
873   /*  Calculate <conf_op> of incoming edges.  */
874   if (EDGE_COUNT (bb->preds) > 0)
875     FOR_EACH_EDGE (e, ei, bb->preds)
876       {                                                         
877         if (TEST_BIT (considered, e->src->index))               
878           dataflow->problem->con_fun_n (e);
879       }                                                         
880   else if (dataflow->problem->con_fun_0)
881     dataflow->problem->con_fun_0 (bb);
882
883   if (dataflow->problem->trans_fun (bb_index))
884     {
885       /* The out set of this block has changed. 
886          Propagate to the outgoing blocks.  */
887       FOR_EACH_EDGE (e, ei, bb->succs)
888         {
889           unsigned ob_index = e->dest->index;
890
891           if (TEST_BIT (considered, ob_index))
892             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
893         }
894     }
895 }
896
897
898 /* Helper function for df_worklist_dataflow.
899    Propagate the dataflow backward.  */
900
901 static void
902 df_worklist_propagate_backward (struct dataflow *dataflow,
903                                 unsigned bb_index,
904                                 unsigned *bbindex_to_postorder,
905                                 bitmap pending,
906                                 sbitmap considered)
907 {
908   edge e;
909   edge_iterator ei;
910   basic_block bb = BASIC_BLOCK (bb_index);
911
912   /*  Calculate <conf_op> of incoming edges.  */
913   if (EDGE_COUNT (bb->succs) > 0)
914     FOR_EACH_EDGE (e, ei, bb->succs)
915       {                                                         
916         if (TEST_BIT (considered, e->dest->index))              
917           dataflow->problem->con_fun_n (e);
918       }                                                         
919   else if (dataflow->problem->con_fun_0)
920     dataflow->problem->con_fun_0 (bb);
921
922   if (dataflow->problem->trans_fun (bb_index))
923     {
924       /* The out set of this block has changed. 
925          Propagate to the outgoing blocks.  */
926       FOR_EACH_EDGE (e, ei, bb->preds)
927         {
928           unsigned ob_index = e->src->index;
929
930           if (TEST_BIT (considered, ob_index))
931             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
932         }
933     }
934 }
935
936
937
938 /* This will free "pending". */
939
940 static void 
941 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
942                                   bitmap pending,
943                                   sbitmap considered,
944                                   int *blocks_in_postorder,
945                                   unsigned *bbindex_to_postorder)
946 {
947   enum df_flow_dir dir = dataflow->problem->dir;
948   int dcount = 0;
949   bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
950
951   /* Double-queueing. Worklist is for the current iteration,
952      and pending is for the next. */
953   while (!bitmap_empty_p (pending))
954     {
955       /* Swap pending and worklist. */
956       bitmap temp = worklist;
957       worklist = pending;
958       pending = temp;
959
960       do
961         {
962           int index;
963           unsigned bb_index;
964           dcount++;
965
966           index = bitmap_first_set_bit (worklist);
967           bitmap_clear_bit (worklist, index);
968
969           bb_index = blocks_in_postorder[index];
970
971           if (dir == DF_FORWARD)
972             df_worklist_propagate_forward (dataflow, bb_index,
973                                            bbindex_to_postorder,
974                                            pending, considered);
975           else 
976             df_worklist_propagate_backward (dataflow, bb_index,
977                                             bbindex_to_postorder,
978                                             pending, considered);
979         }
980       while (!bitmap_empty_p (worklist));
981     }
982
983   BITMAP_FREE (worklist);
984   BITMAP_FREE (pending);
985
986   /* Dump statistics. */
987   if (dump_file)
988     fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
989              "n_basic_blocks %d n_edges %d"
990              " count %d (%5.2g)\n",
991              n_basic_blocks, n_edges,
992              dcount, dcount / (float)n_basic_blocks);
993 }
994
995 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
996    with "n"-th bit representing the n-th block in the reverse-postorder order. 
997    The solver is a double-queue algorithm similar to the "double stack" solver
998    from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
999    The only significant difference is that the worklist in this implementation
1000    is always sorted in RPO of the CFG visiting direction.  */
1001
1002 void 
1003 df_worklist_dataflow (struct dataflow *dataflow,
1004                       bitmap blocks_to_consider,
1005                       int *blocks_in_postorder,
1006                       int n_blocks)
1007 {
1008   bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1009   sbitmap considered = sbitmap_alloc (last_basic_block);
1010   bitmap_iterator bi;
1011   unsigned int *bbindex_to_postorder;
1012   int i;
1013   unsigned int index;
1014   enum df_flow_dir dir = dataflow->problem->dir;
1015
1016   gcc_assert (dir != DF_NONE);
1017
1018   /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  */
1019   bbindex_to_postorder =
1020     (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
1021
1022   /* Initialize the array to an out-of-bound value.  */
1023   for (i = 0; i < last_basic_block; i++)
1024     bbindex_to_postorder[i] = last_basic_block;
1025
1026   /* Initialize the considered map.  */
1027   sbitmap_zero (considered);
1028   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1029     {
1030       SET_BIT (considered, index);
1031     }
1032
1033   /* Initialize the mapping of block index to postorder.  */
1034   for (i = 0; i < n_blocks; i++)
1035     {
1036       bbindex_to_postorder[blocks_in_postorder[i]] = i;
1037       /* Add all blocks to the worklist.  */
1038       bitmap_set_bit (pending, i);
1039     }
1040
1041   /* Initialize the problem. */
1042   if (dataflow->problem->init_fun)
1043     dataflow->problem->init_fun (blocks_to_consider);
1044
1045   /* Solve it.  */
1046   df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1047                                     blocks_in_postorder,
1048                                     bbindex_to_postorder);
1049
1050   sbitmap_free (considered);
1051   free (bbindex_to_postorder);
1052 }
1053
1054
1055 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1056    the order of the remaining entries.  Returns the length of the resulting
1057    list.  */
1058
1059 static unsigned
1060 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1061 {
1062   unsigned act, last;
1063
1064   for (act = 0, last = 0; act < len; act++)
1065     if (bitmap_bit_p (blocks, list[act]))
1066       list[last++] = list[act];
1067
1068   return last;
1069 }
1070
1071
1072 /* Execute dataflow analysis on a single dataflow problem. 
1073
1074    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1075    examined or will be computed.  For calls from DF_ANALYZE, this is
1076    the set of blocks that has been passed to DF_SET_BLOCKS.  
1077 */
1078
1079 void
1080 df_analyze_problem (struct dataflow *dflow, 
1081                     bitmap blocks_to_consider, 
1082                     int *postorder, int n_blocks)
1083 {
1084   timevar_push (dflow->problem->tv_id);
1085
1086 #ifdef ENABLE_DF_CHECKING
1087   if (dflow->problem->verify_start_fun)
1088     dflow->problem->verify_start_fun ();
1089 #endif
1090
1091   /* (Re)Allocate the datastructures necessary to solve the problem.  */ 
1092   if (dflow->problem->alloc_fun)
1093     dflow->problem->alloc_fun (blocks_to_consider);
1094
1095   /* Set up the problem and compute the local information.  */
1096   if (dflow->problem->local_compute_fun)
1097     dflow->problem->local_compute_fun (blocks_to_consider);
1098
1099   /* Solve the equations.  */
1100   if (dflow->problem->dataflow_fun)
1101     dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1102                                   postorder, n_blocks);
1103
1104   /* Massage the solution.  */
1105   if (dflow->problem->finalize_fun)
1106     dflow->problem->finalize_fun (blocks_to_consider);
1107
1108 #ifdef ENABLE_DF_CHECKING
1109   if (dflow->problem->verify_end_fun)
1110     dflow->problem->verify_end_fun ();
1111 #endif
1112
1113   timevar_pop (dflow->problem->tv_id);
1114
1115   dflow->computed = true;
1116 }
1117
1118
1119 /* Analyze dataflow info for the basic blocks specified by the bitmap
1120    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
1121
1122 void
1123 df_analyze (void)
1124 {
1125   bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1126   bool everything;
1127   int i;
1128   
1129   if (df->postorder)
1130     free (df->postorder);
1131   if (df->postorder_inverted)
1132     free (df->postorder_inverted);
1133   df->postorder = XNEWVEC (int, last_basic_block);
1134   df->postorder_inverted = XNEWVEC (int, last_basic_block);
1135   df->n_blocks = post_order_compute (df->postorder, true, true);
1136   df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1137
1138   /* These should be the same.  */
1139   gcc_assert (df->n_blocks == df->n_blocks_inverted);
1140
1141   /* We need to do this before the df_verify_all because this is
1142      not kept incrementally up to date.  */
1143   df_compute_regs_ever_live (false);
1144   df_process_deferred_rescans ();
1145
1146   if (dump_file)
1147     fprintf (dump_file, "df_analyze called\n");
1148
1149 #ifndef ENABLE_DF_CHECKING
1150   if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1151 #endif
1152     df_verify ();
1153
1154   for (i = 0; i < df->n_blocks; i++)
1155     bitmap_set_bit (current_all_blocks, df->postorder[i]);
1156
1157 #ifdef ENABLE_CHECKING
1158   /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1159      the ENTRY block.  */
1160   for (i = 0; i < df->n_blocks_inverted; i++)
1161     gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1162 #endif
1163
1164   /* Make sure that we have pruned any unreachable blocks from these
1165      sets.  */
1166   if (df->analyze_subset)
1167     {
1168       everything = false;
1169       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1170       df->n_blocks = df_prune_to_subcfg (df->postorder, 
1171                                          df->n_blocks, df->blocks_to_analyze);
1172       df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted, 
1173                                                   df->n_blocks_inverted, 
1174                                                   df->blocks_to_analyze);
1175       BITMAP_FREE (current_all_blocks);
1176     }
1177   else
1178     {
1179       everything = true;
1180       df->blocks_to_analyze = current_all_blocks;
1181       current_all_blocks = NULL;
1182     }
1183
1184   /* Skip over the DF_SCAN problem. */
1185   for (i = 1; i < df->num_problems_defined; i++)
1186     {
1187       struct dataflow *dflow = df->problems_in_order[i];
1188       if (dflow->solutions_dirty)
1189         {
1190           if (dflow->problem->dir == DF_FORWARD)
1191             df_analyze_problem (dflow,
1192                                 df->blocks_to_analyze,
1193                                 df->postorder_inverted,
1194                                 df->n_blocks_inverted);
1195           else
1196             df_analyze_problem (dflow,
1197                                 df->blocks_to_analyze,
1198                                 df->postorder,
1199                                 df->n_blocks);
1200         }
1201     }
1202
1203   if (everything)
1204     {
1205       BITMAP_FREE (df->blocks_to_analyze);
1206       df->blocks_to_analyze = NULL;
1207     }
1208
1209 #ifdef DF_DEBUG_CFG
1210   df_set_clean_cfg ();
1211 #endif
1212 }
1213
1214
1215 /* Return the number of basic blocks from the last call to df_analyze.  */
1216
1217 int 
1218 df_get_n_blocks (enum df_flow_dir dir)
1219 {
1220   gcc_assert (dir != DF_NONE);
1221
1222   if (dir == DF_FORWARD)
1223     {
1224       gcc_assert (df->postorder_inverted);
1225       return df->n_blocks_inverted;
1226     }
1227
1228   gcc_assert (df->postorder);
1229   return df->n_blocks;
1230 }
1231
1232
1233 /* Return a pointer to the array of basic blocks in the reverse postorder. 
1234    Depending on the direction of the dataflow problem,
1235    it returns either the usual reverse postorder array
1236    or the reverse postorder of inverted traversal. */
1237 int *
1238 df_get_postorder (enum df_flow_dir dir)
1239 {
1240   gcc_assert (dir != DF_NONE);
1241
1242   if (dir == DF_FORWARD)
1243     {
1244       gcc_assert (df->postorder_inverted);
1245       return df->postorder_inverted;
1246     }
1247   gcc_assert (df->postorder);
1248   return df->postorder;
1249 }
1250
1251 static struct df_problem user_problem; 
1252 static struct dataflow user_dflow;
1253
1254 /* Interface for calling iterative dataflow with user defined
1255    confluence and transfer functions.  All that is necessary is to
1256    supply DIR, a direction, CONF_FUN_0, a confluence function for
1257    blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1258    confluence function, TRANS_FUN, the basic block transfer function,
1259    and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1260    postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1261
1262 void
1263 df_simple_dataflow (enum df_flow_dir dir,
1264                     df_init_function init_fun,
1265                     df_confluence_function_0 con_fun_0,
1266                     df_confluence_function_n con_fun_n,
1267                     df_transfer_function trans_fun,
1268                     bitmap blocks, int * postorder, int n_blocks)
1269 {
1270   memset (&user_problem, 0, sizeof (struct df_problem));
1271   user_problem.dir = dir;
1272   user_problem.init_fun = init_fun;
1273   user_problem.con_fun_0 = con_fun_0;
1274   user_problem.con_fun_n = con_fun_n;
1275   user_problem.trans_fun = trans_fun;
1276   user_dflow.problem = &user_problem;
1277   df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1278 }
1279
1280                               
1281 \f
1282 /*----------------------------------------------------------------------------
1283    Functions to support limited incremental change.
1284 ----------------------------------------------------------------------------*/
1285
1286
1287 /* Get basic block info.  */
1288
1289 static void *
1290 df_get_bb_info (struct dataflow *dflow, unsigned int index)
1291 {
1292   if (dflow->block_info == NULL)
1293     return NULL;
1294   if (index >= dflow->block_info_size)
1295     return NULL;
1296   return (struct df_scan_bb_info *) dflow->block_info[index];
1297 }
1298
1299
1300 /* Set basic block info.  */
1301
1302 static void
1303 df_set_bb_info (struct dataflow *dflow, unsigned int index, 
1304                 void *bb_info)
1305 {
1306   gcc_assert (dflow->block_info);
1307   dflow->block_info[index] = bb_info;
1308 }
1309
1310
1311 /* Mark the solutions as being out of date.  */
1312
1313 void 
1314 df_mark_solutions_dirty (void)
1315 {
1316   if (df)
1317     {
1318       int p; 
1319       for (p = 1; p < df->num_problems_defined; p++)
1320         df->problems_in_order[p]->solutions_dirty = true;
1321     }
1322 }
1323
1324
1325 /* Return true if BB needs it's transfer functions recomputed.  */
1326
1327 bool 
1328 df_get_bb_dirty (basic_block bb)
1329 {
1330   if (df && df_live)
1331     return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
1332   else 
1333     return false;
1334 }
1335
1336
1337 /* Mark BB as needing it's transfer functions as being out of
1338    date.  */
1339
1340 void 
1341 df_set_bb_dirty (basic_block bb)
1342 {
1343   if (df)
1344     {
1345       int p; 
1346       for (p = 1; p < df->num_problems_defined; p++)
1347         {
1348           struct dataflow *dflow = df->problems_in_order[p];
1349           if (dflow->out_of_date_transfer_functions)
1350             bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1351         }
1352       df_mark_solutions_dirty ();
1353     }
1354 }
1355
1356
1357 /* Clear the dirty bits.  This is called from places that delete
1358    blocks.  */
1359 static void
1360 df_clear_bb_dirty (basic_block bb)
1361 {
1362   int p; 
1363   for (p = 1; p < df->num_problems_defined; p++)
1364     {
1365       struct dataflow *dflow = df->problems_in_order[p];
1366       if (dflow->out_of_date_transfer_functions)
1367         bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1368     }
1369 }
1370 /* Called from the rtl_compact_blocks to reorganize the problems basic
1371    block info.  */
1372
1373 void 
1374 df_compact_blocks (void)
1375 {
1376   int i, p;
1377   basic_block bb;
1378   void **problem_temps;
1379   int size = last_basic_block * sizeof (void *);
1380   bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1381   problem_temps = XNEWVAR (void *, size);
1382
1383   for (p = 0; p < df->num_problems_defined; p++)
1384     {
1385       struct dataflow *dflow = df->problems_in_order[p];
1386
1387       /* Need to reorganize the out_of_date_transfer_functions for the
1388          dflow problem.  */
1389       if (dflow->out_of_date_transfer_functions)
1390         {
1391           bitmap_copy (tmp, dflow->out_of_date_transfer_functions);
1392           bitmap_clear (dflow->out_of_date_transfer_functions);
1393           if (bitmap_bit_p (tmp, ENTRY_BLOCK))
1394             bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1395           if (bitmap_bit_p (tmp, EXIT_BLOCK))
1396             bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1397
1398           i = NUM_FIXED_BLOCKS;
1399           FOR_EACH_BB (bb) 
1400             {
1401               if (bitmap_bit_p (tmp, bb->index))
1402                 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1403               i++;
1404             }
1405         }
1406
1407       /* Now shuffle the block info for the problem.  */
1408       if (dflow->problem->free_bb_fun)
1409         {
1410           df_grow_bb_info (dflow);
1411           memcpy (problem_temps, dflow->block_info, size);
1412
1413           /* Copy the bb info from the problem tmps to the proper
1414              place in the block_info vector.  Null out the copied
1415              item.  The entry and exit blocks never move.  */
1416           i = NUM_FIXED_BLOCKS;
1417           FOR_EACH_BB (bb) 
1418             {
1419               df_set_bb_info (dflow, i, problem_temps[bb->index]);
1420               problem_temps[bb->index] = NULL;
1421               i++;
1422             }
1423           memset (dflow->block_info + i, 0, 
1424                   (last_basic_block - i) *sizeof (void *));
1425
1426           /* Free any block infos that were not copied (and NULLed).
1427              These are from orphaned blocks.  */
1428           for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
1429             {
1430               basic_block bb = BASIC_BLOCK (i); 
1431               if (problem_temps[i] && bb)
1432                 dflow->problem->free_bb_fun
1433                   (bb, problem_temps[i]);
1434             }
1435         }
1436     }
1437
1438   /* Shuffle the bits in the basic_block indexed arrays.  */
1439
1440   if (df->blocks_to_analyze)
1441     {
1442       if (bitmap_bit_p (tmp, ENTRY_BLOCK))
1443         bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1444       if (bitmap_bit_p (tmp, EXIT_BLOCK))
1445         bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1446       bitmap_copy (tmp, df->blocks_to_analyze);
1447       bitmap_clear (df->blocks_to_analyze);
1448       i = NUM_FIXED_BLOCKS;
1449       FOR_EACH_BB (bb) 
1450         {
1451           if (bitmap_bit_p (tmp, bb->index))
1452             bitmap_set_bit (df->blocks_to_analyze, i);
1453           i++;
1454         }
1455     }
1456
1457   BITMAP_FREE (tmp);
1458
1459   free (problem_temps);
1460
1461   i = NUM_FIXED_BLOCKS;
1462   FOR_EACH_BB (bb) 
1463     {
1464       SET_BASIC_BLOCK (i, bb);
1465       bb->index = i;
1466       i++;
1467     }
1468
1469   gcc_assert (i == n_basic_blocks);
1470
1471   for (; i < last_basic_block; i++)
1472     SET_BASIC_BLOCK (i, NULL);
1473
1474 #ifdef DF_DEBUG_CFG
1475   if (!df_lr->solutions_dirty)
1476     df_set_clean_cfg ();
1477 #endif
1478 }
1479
1480
1481 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
1482    block.  There is no excuse for people to do this kind of thing.  */
1483
1484 void 
1485 df_bb_replace (int old_index, basic_block new_block)
1486 {
1487   int new_block_index = new_block->index;
1488   int p;
1489
1490   if (dump_file)
1491     fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1492
1493   gcc_assert (df);
1494   gcc_assert (BASIC_BLOCK (old_index) == NULL);
1495
1496   for (p = 0; p < df->num_problems_defined; p++)
1497     {
1498       struct dataflow *dflow = df->problems_in_order[p];
1499       if (dflow->block_info)
1500         {
1501           df_grow_bb_info (dflow);
1502           gcc_assert (df_get_bb_info (dflow, old_index) == NULL);
1503           df_set_bb_info (dflow, old_index, 
1504                           df_get_bb_info (dflow, new_block_index));
1505         }
1506     }
1507
1508   df_clear_bb_dirty (new_block);
1509   SET_BASIC_BLOCK (old_index, new_block);
1510   new_block->index = old_index;
1511   df_set_bb_dirty (BASIC_BLOCK (old_index));
1512   SET_BASIC_BLOCK (new_block_index, NULL);
1513 }
1514
1515
1516 /* Free all of the per basic block dataflow from all of the problems.
1517    This is typically called before a basic block is deleted and the
1518    problem will be reanalyzed.  */
1519
1520 void
1521 df_bb_delete (int bb_index)
1522 {
1523   basic_block bb = BASIC_BLOCK (bb_index);
1524   int i;
1525
1526   if (!df)
1527     return;
1528   
1529   for (i = 0; i < df->num_problems_defined; i++)
1530     {
1531       struct dataflow *dflow = df->problems_in_order[i];
1532       if (dflow->problem->free_bb_fun)
1533         {
1534           void *bb_info = df_get_bb_info (dflow, bb_index);
1535           if (bb_info)
1536             {
1537               dflow->problem->free_bb_fun (bb, bb_info); 
1538               df_set_bb_info (dflow, bb_index, NULL);
1539             }
1540         }
1541     }
1542   df_clear_bb_dirty (bb);
1543   df_mark_solutions_dirty ();
1544 }
1545
1546
1547 /* Verify that there is a place for everything and everything is in
1548    its place.  This is too expensive to run after every pass in the
1549    mainline.  However this is an excellent debugging tool if the
1550    dataflow information is not being updated properly.  You can just
1551    sprinkle calls in until you find the place that is changing an
1552    underlying structure without calling the proper updating
1553    routine.  */
1554
1555 void
1556 df_verify (void)
1557 {
1558   df_scan_verify ();
1559 #ifdef ENABLE_DF_CHECKING
1560   df_lr_verify_transfer_functions ();
1561   if (df_live)
1562     df_live_verify_transfer_functions ();
1563 #endif
1564 }
1565
1566 #ifdef DF_DEBUG_CFG
1567
1568 /* Compute an array of ints that describes the cfg.  This can be used
1569    to discover places where the cfg is modified by the appropriate
1570    calls have not been made to the keep df informed.  The internals of
1571    this are unexciting, the key is that two instances of this can be
1572    compared to see if any changes have been made to the cfg.  */
1573
1574 static int *
1575 df_compute_cfg_image (void)
1576 {
1577   basic_block bb;
1578   int size = 2 + (2 * n_basic_blocks);
1579   int i;
1580   int * map;
1581
1582   FOR_ALL_BB (bb)
1583     {
1584       size += EDGE_COUNT (bb->succs);
1585     }
1586
1587   map = XNEWVEC (int, size);
1588   map[0] = size;
1589   i = 1;
1590   FOR_ALL_BB (bb)
1591     {
1592       edge_iterator ei;
1593       edge e;
1594
1595       map[i++] = bb->index;
1596       FOR_EACH_EDGE (e, ei, bb->succs)
1597         map[i++] = e->dest->index;
1598       map[i++] = -1;
1599     }
1600   map[i] = -1;
1601   return map;
1602 }
1603
1604 static int *saved_cfg = NULL;
1605
1606
1607 /* This function compares the saved version of the cfg with the
1608    current cfg and aborts if the two are identical.  The function
1609    silently returns if the cfg has been marked as dirty or the two are
1610    the same.  */
1611
1612 void
1613 df_check_cfg_clean (void)
1614 {
1615   int *new_map;
1616
1617   if (!df)
1618     return;
1619
1620   if (df_lr->solutions_dirty)
1621     return;
1622
1623   if (saved_cfg == NULL) 
1624     return;
1625
1626   new_map = df_compute_cfg_image ();
1627   gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1628   free (new_map);
1629 }
1630
1631
1632 /* This function builds a cfg fingerprint and squirrels it away in
1633    saved_cfg.  */
1634
1635 static void
1636 df_set_clean_cfg (void)
1637 {
1638   if (saved_cfg)
1639     free (saved_cfg);
1640   saved_cfg = df_compute_cfg_image ();
1641 }
1642
1643 #endif /* DF_DEBUG_CFG  */
1644 /*----------------------------------------------------------------------------
1645    PUBLIC INTERFACES TO QUERY INFORMATION.
1646 ----------------------------------------------------------------------------*/
1647
1648
1649 /* Return first def of REGNO within BB.  */
1650
1651 df_ref 
1652 df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1653 {
1654   rtx insn;
1655   df_ref *def_rec;
1656   unsigned int uid;
1657
1658   FOR_BB_INSNS (bb, insn)
1659     {
1660       if (!INSN_P (insn))
1661         continue;
1662
1663       uid = INSN_UID (insn);
1664       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1665         {
1666           df_ref def = *def_rec;
1667           if (DF_REF_REGNO (def) == regno)
1668             return def;
1669         }
1670     }
1671   return NULL;
1672 }
1673
1674
1675 /* Return last def of REGNO within BB.  */
1676
1677 df_ref 
1678 df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1679 {
1680   rtx insn;
1681   df_ref *def_rec;
1682   unsigned int uid;
1683
1684   FOR_BB_INSNS_REVERSE (bb, insn)
1685     {
1686       if (!INSN_P (insn))
1687         continue;
1688
1689       uid = INSN_UID (insn);
1690       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1691         {
1692           df_ref def = *def_rec;
1693           if (DF_REF_REGNO (def) == regno)
1694             return def;
1695         }
1696     }
1697
1698   return NULL;
1699 }
1700
1701 /* Finds the reference corresponding to the definition of REG in INSN.
1702    DF is the dataflow object.  */
1703
1704 df_ref 
1705 df_find_def (rtx insn, rtx reg)
1706 {
1707   unsigned int uid;
1708   df_ref *def_rec;
1709
1710   if (GET_CODE (reg) == SUBREG)
1711     reg = SUBREG_REG (reg);
1712   gcc_assert (REG_P (reg));
1713
1714   uid = INSN_UID (insn);
1715   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1716     {
1717       df_ref def = *def_rec;
1718       if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1719         return def;
1720     }
1721
1722   return NULL;
1723 }
1724
1725
1726 /* Return true if REG is defined in INSN, zero otherwise.  */ 
1727
1728 bool
1729 df_reg_defined (rtx insn, rtx reg)
1730 {
1731   return df_find_def (insn, reg) != NULL;
1732 }
1733   
1734
1735 /* Finds the reference corresponding to the use of REG in INSN.
1736    DF is the dataflow object.  */
1737   
1738 df_ref 
1739 df_find_use (rtx insn, rtx reg)
1740 {
1741   unsigned int uid;
1742   df_ref *use_rec;
1743
1744   if (GET_CODE (reg) == SUBREG)
1745     reg = SUBREG_REG (reg);
1746   gcc_assert (REG_P (reg));
1747
1748   uid = INSN_UID (insn);
1749   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1750     {
1751       df_ref use = *use_rec;
1752       if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1753         return use;
1754     } 
1755   if (df->changeable_flags & DF_EQ_NOTES)
1756     for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1757       {
1758         df_ref use = *use_rec;
1759         if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1760           return use; 
1761       }
1762   return NULL;
1763 }
1764
1765
1766 /* Return true if REG is referenced in INSN, zero otherwise.  */ 
1767
1768 bool
1769 df_reg_used (rtx insn, rtx reg)
1770 {
1771   return df_find_use (insn, reg) != NULL;
1772 }
1773   
1774 \f
1775 /*----------------------------------------------------------------------------
1776    Debugging and printing functions.
1777 ----------------------------------------------------------------------------*/
1778
1779
1780 /* Write information about registers and basic blocks into FILE.
1781    This is part of making a debugging dump.  */
1782
1783 void
1784 df_print_regset (FILE *file, bitmap r)
1785 {
1786   unsigned int i;
1787   bitmap_iterator bi;
1788
1789   if (r == NULL)
1790     fputs (" (nil)", file);
1791   else
1792     {
1793       EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1794         {
1795           fprintf (file, " %d", i);
1796           if (i < FIRST_PSEUDO_REGISTER)
1797             fprintf (file, " [%s]", reg_names[i]);
1798         }
1799     }
1800   fprintf (file, "\n");
1801 }
1802
1803
1804 /* Write information about registers and basic blocks into FILE.  The
1805    bitmap is in the form used by df_byte_lr.  This is part of making a
1806    debugging dump.  */
1807
1808 void
1809 df_print_byte_regset (FILE *file, bitmap r)
1810 {
1811   unsigned int max_reg = max_reg_num ();
1812   bitmap_iterator bi;
1813
1814   if (r == NULL)
1815     fputs (" (nil)", file);
1816   else
1817     {
1818       unsigned int i;
1819       for (i = 0; i < max_reg; i++)
1820         {
1821           unsigned int first = df_byte_lr_get_regno_start (i);
1822           unsigned int len = df_byte_lr_get_regno_len (i);
1823
1824           if (len > 1)
1825             {
1826               bool found = false;
1827               unsigned int j;
1828
1829               EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
1830                 {
1831                   found = j < first + len;
1832                   break;
1833                 }
1834               if (found)
1835                 {
1836                   const char * sep = "";
1837                   fprintf (file, " %d", i);
1838                   if (i < FIRST_PSEUDO_REGISTER)
1839                     fprintf (file, " [%s]", reg_names[i]);
1840                   fprintf (file, "(");
1841                   EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
1842                     {
1843                       if (j > first + len - 1)
1844                         break;
1845                       fprintf (file, "%s%d", sep, j-first);
1846                       sep = ", ";
1847                     }
1848                   fprintf (file, ")");
1849                 }
1850             }
1851           else
1852             {
1853               if (bitmap_bit_p (r, first))
1854                 {
1855                   fprintf (file, " %d", i);
1856                   if (i < FIRST_PSEUDO_REGISTER)
1857                     fprintf (file, " [%s]", reg_names[i]);
1858                 }
1859             }
1860
1861         }
1862     }
1863   fprintf (file, "\n");
1864 }
1865
1866
1867 /* Dump dataflow info.  */
1868
1869 void
1870 df_dump (FILE *file)
1871 {
1872   basic_block bb;
1873   df_dump_start (file);
1874
1875   FOR_ALL_BB (bb)
1876     {
1877       df_print_bb_index (bb, file);
1878       df_dump_top (bb, file);
1879       df_dump_bottom (bb, file);
1880     }
1881
1882   fprintf (file, "\n");
1883 }
1884
1885
1886 /* Dump dataflow info for df->blocks_to_analyze.  */
1887
1888 void
1889 df_dump_region (FILE *file)
1890 {
1891   if (df->blocks_to_analyze)
1892     {
1893       bitmap_iterator bi;
1894       unsigned int bb_index;
1895
1896       fprintf (file, "\n\nstarting region dump\n");
1897       df_dump_start (file);
1898       
1899       EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi) 
1900         {
1901           basic_block bb = BASIC_BLOCK (bb_index);
1902           
1903           df_print_bb_index (bb, file);
1904           df_dump_top (bb, file);
1905           df_dump_bottom (bb, file);
1906         }
1907       fprintf (file, "\n");
1908     }
1909   else 
1910     df_dump (file);
1911 }
1912
1913
1914 /* Dump the introductory information for each problem defined.  */
1915
1916 void
1917 df_dump_start (FILE *file)
1918 {
1919   int i;
1920
1921   if (!df || !file)
1922     return;
1923
1924   fprintf (file, "\n\n%s\n", current_function_name ());
1925   fprintf (file, "\nDataflow summary:\n");
1926   if (df->blocks_to_analyze)
1927     fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
1928              DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1929
1930   for (i = 0; i < df->num_problems_defined; i++)
1931     {
1932       struct dataflow *dflow = df->problems_in_order[i];
1933       if (dflow->computed)
1934         {
1935           df_dump_problem_function fun = dflow->problem->dump_start_fun;
1936           if (fun)
1937             fun(file); 
1938         }
1939     }
1940 }
1941
1942
1943 /* Dump the top of the block information for BB.  */ 
1944
1945 void
1946 df_dump_top (basic_block bb, FILE *file)
1947 {
1948   int i;
1949
1950   if (!df || !file)
1951     return;
1952
1953   for (i = 0; i < df->num_problems_defined; i++)
1954     {
1955       struct dataflow *dflow = df->problems_in_order[i];
1956       if (dflow->computed)
1957         {
1958           df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
1959           if (bbfun)
1960             bbfun (bb, file); 
1961         }
1962     }
1963 }
1964
1965
1966 /* Dump the bottom of the block information for BB.  */ 
1967
1968 void
1969 df_dump_bottom (basic_block bb, FILE *file)
1970 {
1971   int i;
1972
1973   if (!df || !file)
1974     return;
1975
1976   for (i = 0; i < df->num_problems_defined; i++)
1977     {
1978       struct dataflow *dflow = df->problems_in_order[i];
1979       if (dflow->computed)
1980         {
1981           df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
1982           if (bbfun)
1983             bbfun (bb, file); 
1984         }
1985     }
1986 }
1987
1988
1989 void
1990 df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
1991 {
1992   fprintf (file, "{ ");
1993   while (*ref_rec)
1994     {
1995       df_ref ref = *ref_rec;
1996       fprintf (file, "%c%d(%d)",
1997                DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
1998                DF_REF_ID (ref),
1999                DF_REF_REGNO (ref));
2000       if (follow_chain)
2001         df_chain_dump (DF_REF_CHAIN (ref), file);
2002       ref_rec++;
2003     }
2004   fprintf (file, "}");
2005 }
2006
2007
2008 /* Dump either a ref-def or reg-use chain.  */
2009
2010 void
2011 df_regs_chain_dump (df_ref ref,  FILE *file)
2012 {
2013   fprintf (file, "{ ");
2014   while (ref)
2015     {
2016       fprintf (file, "%c%d(%d) ",
2017                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2018                DF_REF_ID (ref),
2019                DF_REF_REGNO (ref));
2020       ref = DF_REF_NEXT_REG (ref);
2021     }
2022   fprintf (file, "}");
2023 }
2024
2025
2026 static void
2027 df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
2028 {
2029   while (*mws)
2030     {
2031       fprintf (file, "mw %c r[%d..%d]\n", 
2032                (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
2033                (*mws)->start_regno, (*mws)->end_regno);
2034       mws++;
2035     }
2036 }
2037
2038
2039 static void 
2040 df_insn_uid_debug (unsigned int uid, 
2041                    bool follow_chain, FILE *file)
2042 {
2043   fprintf (file, "insn %d luid %d",
2044            uid, DF_INSN_UID_LUID (uid));
2045
2046   if (DF_INSN_UID_DEFS (uid))
2047     {
2048       fprintf (file, " defs ");
2049       df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2050     }
2051
2052   if (DF_INSN_UID_USES (uid))
2053     {
2054       fprintf (file, " uses ");
2055       df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2056     }
2057
2058   if (DF_INSN_UID_EQ_USES (uid))
2059     {
2060       fprintf (file, " eq uses ");
2061       df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2062     }
2063
2064   if (DF_INSN_UID_MWS (uid))
2065     {
2066       fprintf (file, " mws ");
2067       df_mws_dump (DF_INSN_UID_MWS (uid), file);
2068     }
2069   fprintf (file, "\n");
2070 }
2071
2072
2073 void
2074 df_insn_debug (rtx insn, bool follow_chain, FILE *file)
2075 {
2076   df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2077 }
2078
2079 void
2080 df_insn_debug_regno (rtx insn, FILE *file)
2081 {
2082   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2083
2084   fprintf (file, "insn %d bb %d luid %d defs ",
2085            INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2086            DF_INSN_INFO_LUID (insn_info));
2087   df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2088     
2089   fprintf (file, " uses ");
2090   df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2091
2092   fprintf (file, " eq_uses ");
2093   df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2094   fprintf (file, "\n");
2095 }
2096
2097 void
2098 df_regno_debug (unsigned int regno, FILE *file)
2099 {
2100   fprintf (file, "reg %d defs ", regno);
2101   df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2102   fprintf (file, " uses ");
2103   df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2104   fprintf (file, " eq_uses ");
2105   df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2106   fprintf (file, "\n");
2107 }
2108
2109
2110 void
2111 df_ref_debug (df_ref ref, FILE *file)
2112 {
2113   fprintf (file, "%c%d ",
2114            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2115            DF_REF_ID (ref));
2116   fprintf (file, "reg %d bb %d insn %d flag 0x%x type 0x%x ",
2117            DF_REF_REGNO (ref),
2118            DF_REF_BBNO (ref),
2119            DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2120            DF_REF_FLAGS (ref),
2121            DF_REF_TYPE (ref));
2122   if (DF_REF_LOC (ref))
2123     fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref), (void *)*DF_REF_LOC (ref));
2124   else
2125     fprintf (file, "chain ");
2126   df_chain_dump (DF_REF_CHAIN (ref), file);
2127   fprintf (file, "\n");
2128 }
2129 \f
2130 /* Functions for debugging from GDB.  */
2131
2132 void
2133 debug_df_insn (rtx insn)
2134 {
2135   df_insn_debug (insn, true, stderr);
2136   debug_rtx (insn);
2137 }
2138
2139
2140 void
2141 debug_df_reg (rtx reg)
2142 {
2143   df_regno_debug (REGNO (reg), stderr);
2144 }
2145
2146
2147 void
2148 debug_df_regno (unsigned int regno)
2149 {
2150   df_regno_debug (regno, stderr);
2151 }
2152
2153
2154 void
2155 debug_df_ref (df_ref ref)
2156 {
2157   df_ref_debug (ref, stderr);
2158 }
2159
2160
2161 void
2162 debug_df_defno (unsigned int defno)
2163 {
2164   df_ref_debug (DF_DEFS_GET (defno), stderr);
2165 }
2166
2167
2168 void
2169 debug_df_useno (unsigned int defno)
2170 {
2171   df_ref_debug (DF_USES_GET (defno), stderr);
2172 }
2173
2174
2175 void
2176 debug_df_chain (struct df_link *link)
2177 {
2178   df_chain_dump (link, stderr);
2179   fputc ('\n', stderr);
2180 }