1 /* Allocation for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
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
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
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/>. */
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.
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.
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.
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 tha can be reached from a definition of a variable. The LIVE
46 problem finds the intersection of these two areas.
48 There are several optional problems. These can be enabled when they
49 are needed and disabled when they are not needed.
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
59 In the middle layer, basic blocks are scanned to produce transfer
60 functions which describe the effects of that block on the a global
61 dataflow solution. The transfer functions are only rebuilt if the
62 some instruction within the block has changed.
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.
72 Here is an example of using the dataflow routines.
74 df_[ru,rd,urec,ri,chain]_add_problem (flags);
76 df_set_blocks (blocks);
84 DF_[ru,rd,urec,ri,chain]_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.
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.
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.
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.
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.
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.
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.
136 There are four ways of doing the incremental scanning:
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
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 apon even after changes have been made to the instructions. This
148 technique is contra indicated in several cases:
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
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.
167 c) If the pass modifies insns several times, this incremental
168 updating may be expensive.
170 d) If the pass modifies all of the insns, as does register
171 allocation, it is simply better to rescan the entire function.
173 e) If the pass uses either non-standard or ancient techniques to
174 modify insns, automatic detection of the insns that need to be
175 rescanned may be impractical. Cse and regrename fall into this
178 2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
179 df_insn_delete do not immediately change the insn but instead make
180 a note that the insn needs to be rescanned. The next call to
181 df_analyze, df_finish_pass, or df_process_deferred_rescans will
182 cause all of the pending rescans to be processed.
184 This is the technique of choice if either 1a, 1b, or 1c are issues
185 in the pass. In the case of 1a or 1b, a call to df_remove_problem
186 (df_chain) should be made before the next call to df_analyze or
187 df_process_deferred_rescans.
189 To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
190 (This mode can be cleared by calling df_clear_flags
191 (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
194 3) Total rescanning - In this mode the rescanning is disabled.
195 However, the df information associated with deleted insn is delete
196 at the time the insn is deleted. At the end of the pass, a call
197 must be made to df_insn_rescan_all. This method is used by the
198 register allocator since it generally changes each insn multiple
199 times (once for each ref) and does not need to make use of the
200 updated scanning information.
202 It is also currently used by two older passes (cse, and regrename)
203 which change insns in hard to track ways. It is hoped that this
204 will be fixed soon since this it is expensive to rescan all of the
205 insns when only a small number of them have really changed.
207 4) Do it yourself - In this mechanism, the pass updates the insns
208 itself using the low level df primitives. Currently no pass does
209 this, but it has the advantage that it is quite efficient given
210 that the pass generally has exact knowledge of what it is changing.
214 Scanning produces a `struct df_ref' data structure (ref) is allocated
215 for every register reference (def or use) and this records the insn
216 and bb the ref is found within. The refs are linked together in
217 chains of uses and defs for each insn and for each register. Each ref
218 also has a chain field that links all the use refs for a def or all
219 the def refs for a use. This is used to create use-def or def-use
222 Different optimizations have different needs. Ultimately, only
223 register allocation and schedulers should be using the bitmaps
224 produced for the live register and uninitialized register problems.
225 The rest of the backend should be upgraded to using and maintaining
226 the linked information such as def use or use def chains.
231 While incremental bitmaps are not worthwhile to maintain, incremental
232 chains may be perfectly reasonable. The fastest way to build chains
233 from scratch or after significant modifications is to build reaching
234 definitions (RD) and build the chains from this.
236 However, general algorithms for maintaining use-def or def-use chains
237 are not practical. The amount of work to recompute the chain any
238 chain after an arbitrary change is large. However, with a modest
239 amount of work it is generally possible to have the application that
240 uses the chains keep them up to date. The high level knowledge of
241 what is really happening is essential to crafting efficient
242 incremental algorithms.
244 As for the bit vector problems, there is no interface to give a set of
245 blocks over with to resolve the iteration. In general, restarting a
246 dataflow iteration is difficult and expensive. Again, the best way to
247 keep the dataflow information up to data (if this is really what is
248 needed) it to formulate a problem specific solution.
250 There are fine grained calls for creating and deleting references from
251 instructions in df-scan.c. However, these are not currently connected
252 to the engine that resolves the dataflow equations.
257 The basic object is a DF_REF (reference) and this may either be a
258 DEF (definition) or a USE of a register.
260 These are linked into a variety of lists; namely reg-def, reg-use,
261 insn-def, insn-use, def-use, and use-def lists. For example, the
262 reg-def lists contain all the locations that define a given register
263 while the insn-use lists contain all the locations that use a
266 Note that the reg-def and reg-use chains are generally short for
267 pseudos and long for the hard registers.
271 1) The df insn information is kept in the insns array. This array is
274 2) Each insn has three sets of refs: They are linked into one of three
275 lists: the insn's defs list (accessed by the DF_INSN_DEFS or
276 DF_INSN_UID_DEFS macros), the insn's uses list (accessed by the
277 DF_INSN_USES or DF_INSN_UID_USES macros) or the insn's eq_uses list
278 (accessed by the DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
279 The latter list are the list of references in REG_EQUAL or
280 REG_EQUIV notes. These macros produce a ref (or NULL), the rest of
281 the list can be obtained by traversal of the NEXT_REF field
282 (accessed by the DF_REF_NEXT_REF macro.) There is no significance
283 to the ordering of the uses or refs in an instruction.
285 3) Each insn has a logical uid field (LUID). When properly set, this
286 is an integer that numbers each insn in the basic block, in order from
287 the start of the block. The numbers are only correct after a call to
288 df_analyse. They will rot after insns are added deleted or moved
293 There are 4 ways to obtain access to refs:
295 1) References are divided into two categories, REAL and ARTIFICIAL.
297 REAL refs are associated with instructions.
299 ARTIFICIAL refs are associated with basic blocks. The heads of
300 these lists can be accessed by calling df_get_artificial_defs or
301 df_get_artificial_uses for the particular basic block.
303 Artificial defs and uses occur both at the beginning and ends of blocks.
305 For blocks that area at the destination of eh edges, the
306 artificial uses and defs occur at the beginning. The defs relate
307 to the registers specified in EH_RETURN_DATA_REGNO and the uses
308 relate to the registers specified in ED_USES. Logically these
309 defs and uses should really occur along the eh edge, but there is
310 no convenient way to do this. Artificial edges that occur at the
311 beginning of the block have the DF_REF_AT_TOP flag set.
313 Artificial uses occur at the end of all blocks. These arise from
314 the hard registers that are always live, such as the stack
315 register and are put there to keep the code from forgetting about
318 Artificial defs occur at the end of the entry block. These arise
319 from registers that are live at entry to the function.
321 2) There are three types of refs: defs, uses and eq_uses. (Eq_uses are
322 uses that appear inside a REG_EQUAL or REG_EQUIV note.)
324 All of the eq_uses, uses and defs associated with each pseudo or
325 hard register may be linked in a bidirectional chain. These are
326 called reg-use or reg_def chains. If the changeable flag
327 DF_EQ_NOTES is set when the chains are built, the eq_uses will be
328 treated like uses. If it is not set they are ignored.
330 The first use, eq_use or def for a register can be obtained using
331 the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN
332 macros. Subsequent uses for the same regno can be obtained by
333 following the next_reg field of the ref. The number of elements in
334 each of the chains can be found by using the DF_REG_USE_COUNT,
335 DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.
337 In previous versions of this code, these chains were ordered. It
338 has not been practical to continue this practice.
340 3) If def-use or use-def chains are built, these can be traversed to
341 get to other refs. If the flag DF_EQ_NOTES has been set, the chains
342 include the eq_uses. Otherwise these are ignored when building the
345 4) An array of all of the uses (and an array of all of the defs) can
347 be built. These arrays are indexed by the value in the id
348 structure. These arrays are only lazily kept up to date, and that
349 process can be expensive. To have these arrays built, call
350 df_reorganize_defs or df_reorganize_uses. If the flag DF_EQ_NOTES
351 has been set the array will contain the eq_uses. Otherwise these
352 are ignored when building the array and assigning the ids. Note
353 that the values in the id field of a ref may change across calls to
354 df_analyze or df_reorganize_defs or df_reorganize_uses.
356 If the only use of this array is to find all of the refs, it is
357 better to traverse all of the registers and then traverse all of
358 reg-use or reg-def chains.
362 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
363 both a use and a def. These are both marked read/write to show that they
364 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
365 will generate a use of reg 42 followed by a def of reg 42 (both marked
366 read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
367 generates a use of reg 41 then a def of reg 41 (both marked read/write),
368 even though reg 41 is decremented before it is used for the memory
369 address in this second example.
371 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
372 for which the number of word_mode units covered by the outer mode is
373 smaller than that covered by the inner mode, invokes a read-modify-write.
374 operation. We generate both a use and a def and again mark them
377 Paradoxical subreg writes do not leave a trace of the old content, so they
378 are write-only operations.
384 #include "coretypes.h"
388 #include "insn-config.h"
390 #include "function.h"
393 #include "alloc-pool.h"
395 #include "hard-reg-set.h"
396 #include "basic-block.h"
401 #include "tree-pass.h"
403 static void *df_get_bb_info (struct dataflow *, unsigned int);
404 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
406 static void df_set_clean_cfg (void);
409 /* An obstack for bitmap not related to specific dataflow problems.
410 This obstack should e.g. be used for bitmaps with a short life time
411 such as temporary bitmaps. */
413 bitmap_obstack df_bitmap_obstack;
416 /*----------------------------------------------------------------------------
417 Functions to create, destroy and manipulate an instance of df.
418 ----------------------------------------------------------------------------*/
422 /* Add PROBLEM (and any dependent problems) to the DF instance. */
425 df_add_problem (struct df_problem *problem)
427 struct dataflow *dflow;
430 /* First try to add the dependent problem. */
431 if (problem->dependent_problem)
432 df_add_problem (problem->dependent_problem);
434 /* Check to see if this problem has already been defined. If it
435 has, just return that instance, if not, add it to the end of the
437 dflow = df->problems_by_index[problem->id];
441 /* Make a new one and add it to the end. */
442 dflow = XCNEW (struct dataflow);
443 dflow->problem = problem;
444 dflow->computed = false;
445 dflow->solutions_dirty = true;
446 df->problems_by_index[dflow->problem->id] = dflow;
448 /* Keep the defined problems ordered by index. This solves the
449 problem that RI will use the information from UREC if UREC has
450 been defined, or from LIVE if LIVE is defined and otherwise LR.
451 However for this to work, the computation of RI must be pushed
452 after which ever of those problems is defined, but we do not
453 require any of those except for LR to have actually been
455 df->num_problems_defined++;
456 for (i = df->num_problems_defined - 2; i >= 0; i--)
458 if (problem->id < df->problems_in_order[i]->problem->id)
459 df->problems_in_order[i+1] = df->problems_in_order[i];
462 df->problems_in_order[i+1] = dflow;
466 df->problems_in_order[0] = dflow;
470 /* Set the MASK flags in the DFLOW problem. The old flags are
471 returned. If a flag is not allowed to be changed this will fail if
472 checking is enabled. */
473 enum df_changeable_flags
474 df_set_flags (enum df_changeable_flags changeable_flags)
476 enum df_changeable_flags old_flags = df->changeable_flags;
477 df->changeable_flags |= changeable_flags;
482 /* Clear the MASK flags in the DFLOW problem. The old flags are
483 returned. If a flag is not allowed to be changed this will fail if
484 checking is enabled. */
485 enum df_changeable_flags
486 df_clear_flags (enum df_changeable_flags changeable_flags)
488 enum df_changeable_flags old_flags = df->changeable_flags;
489 df->changeable_flags &= ~changeable_flags;
494 /* Set the blocks that are to be considered for analysis. If this is
495 not called or is called with null, the entire function in
499 df_set_blocks (bitmap blocks)
504 bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
505 if (df->blocks_to_analyze)
507 /* This block is called to change the focus from one subset
510 bitmap diff = BITMAP_ALLOC (&df_bitmap_obstack);
511 bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
512 for (p = 0; p < df->num_problems_defined; p++)
514 struct dataflow *dflow = df->problems_in_order[p];
515 if (dflow->optional_p && dflow->problem->reset_fun)
516 dflow->problem->reset_fun (df->blocks_to_analyze);
517 else if (dflow->problem->free_blocks_on_set_blocks)
520 unsigned int bb_index;
522 EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
524 basic_block bb = BASIC_BLOCK (bb_index);
527 void *bb_info = df_get_bb_info (dflow, bb_index);
530 dflow->problem->free_bb_fun (bb, bb_info);
531 df_set_bb_info (dflow, bb_index, NULL);
542 /* This block of code is executed to change the focus from
543 the entire function to a subset. */
544 bitmap blocks_to_reset = NULL;
546 for (p = 0; p < df->num_problems_defined; p++)
548 struct dataflow *dflow = df->problems_in_order[p];
549 if (dflow->optional_p && dflow->problem->reset_fun)
551 if (!blocks_to_reset)
555 BITMAP_ALLOC (&df_bitmap_obstack);
558 bitmap_set_bit (blocks_to_reset, bb->index);
561 dflow->problem->reset_fun (blocks_to_reset);
565 BITMAP_FREE (blocks_to_reset);
567 df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
569 bitmap_copy (df->blocks_to_analyze, blocks);
570 df->analyze_subset = true;
574 /* This block is executed to reset the focus to the entire
577 fprintf (dump_file, "clearing blocks_to_analyze\n");
578 if (df->blocks_to_analyze)
580 BITMAP_FREE (df->blocks_to_analyze);
581 df->blocks_to_analyze = NULL;
583 df->analyze_subset = false;
586 /* Setting the blocks causes the refs to be unorganized since only
587 the refs in the blocks are seen. */
588 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
589 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
590 df_mark_solutions_dirty ();
594 /* Delete a DFLOW problem (and any problems that depend on this
598 df_remove_problem (struct dataflow *dflow)
600 struct df_problem *problem;
606 problem = dflow->problem;
607 gcc_assert (problem->remove_problem_fun);
609 /* Delete any problems that depended on this problem first. */
610 for (i = 0; i < df->num_problems_defined; i++)
611 if (df->problems_in_order[i]->problem->dependent_problem == problem)
612 df_remove_problem (df->problems_in_order[i]);
614 /* Now remove this problem. */
615 for (i = 0; i < df->num_problems_defined; i++)
616 if (df->problems_in_order[i] == dflow)
619 for (j = i + 1; j < df->num_problems_defined; j++)
620 df->problems_in_order[j-1] = df->problems_in_order[j];
621 df->problems_in_order[j] = NULL;
622 df->num_problems_defined--;
626 (problem->remove_problem_fun) ();
627 df->problems_by_index[problem->id] = NULL;
631 /* Remove all of the problems that are not permanent. Scanning, lr,
632 ur and live are permanent, the rest are removable. Also clear all
633 of the changeable_flags. */
636 df_finish_pass (void)
641 #ifdef ENABLE_DF_CHECKING
642 enum df_changeable_flags saved_flags;
648 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
649 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
651 #ifdef ENABLE_DF_CHECKING
652 saved_flags = df->changeable_flags;
655 for (i = 0; i < df->num_problems_defined; i++)
657 struct dataflow *dflow = df->problems_in_order[i];
658 struct df_problem *problem = dflow->problem;
660 if (dflow->optional_p)
662 gcc_assert (problem->remove_problem_fun);
663 (problem->remove_problem_fun) ();
664 df->problems_in_order[i] = NULL;
665 df->problems_by_index[problem->id] = NULL;
669 df->num_problems_defined -= removed;
671 /* Clear all of the flags. */
672 df->changeable_flags = 0;
673 df_process_deferred_rescans ();
675 /* Set the focus back to the whole function. */
676 if (df->blocks_to_analyze)
678 BITMAP_FREE (df->blocks_to_analyze);
679 df->blocks_to_analyze = NULL;
680 df_mark_solutions_dirty ();
681 df->analyze_subset = false;
684 #ifdef ENABLE_DF_CHECKING
685 /* Verification will fail in DF_NO_INSN_RESCAN. */
686 if (!(saved_flags & DF_NO_INSN_RESCAN))
688 df_lr_verify_transfer_functions ();
690 df_live_verify_transfer_functions ();
700 /* Set up the dataflow instance for the entire back end. */
703 rest_of_handle_df_initialize (void)
706 df = XCNEW (struct df);
707 df->changeable_flags = 0;
709 bitmap_obstack_initialize (&df_bitmap_obstack);
711 /* Set this to a conservative value. Stack_ptr_mod will compute it
713 current_function_sp_is_unchanging = 0;
715 df_scan_add_problem ();
716 df_scan_alloc (NULL);
718 /* These three problems are permanent. */
719 df_lr_add_problem ();
721 df_live_add_problem ();
723 df->postorder = XNEWVEC (int, last_basic_block);
724 df->postorder_inverted = XNEWVEC (int, last_basic_block);
725 df->n_blocks = post_order_compute (df->postorder, true, true);
726 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
727 gcc_assert (df->n_blocks == df->n_blocks_inverted);
729 df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
730 memset (df->hard_regs_live_count, 0,
731 sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
734 /* After reload, some ports add certain bits to regs_ever_live so
735 this cannot be reset. */
736 df_compute_regs_ever_live (true);
738 df_compute_regs_ever_live (false);
750 struct tree_opt_pass pass_df_initialize_opt =
754 rest_of_handle_df_initialize, /* execute */
757 0, /* static_pass_number */
759 0, /* properties_required */
760 0, /* properties_provided */
761 0, /* properties_destroyed */
762 0, /* todo_flags_start */
763 0, /* todo_flags_finish */
771 return optimize == 0;
775 struct tree_opt_pass pass_df_initialize_no_opt =
778 gate_no_opt, /* gate */
779 rest_of_handle_df_initialize, /* execute */
782 0, /* static_pass_number */
784 0, /* properties_required */
785 0, /* properties_provided */
786 0, /* properties_destroyed */
787 0, /* todo_flags_start */
788 0, /* todo_flags_finish */
793 /* Free all the dataflow info and the DF structure. This should be
794 called from the df_finish macro which also NULLs the parm. */
797 rest_of_handle_df_finish (void)
803 for (i = 0; i < df->num_problems_defined; i++)
805 struct dataflow *dflow = df->problems_in_order[i];
806 dflow->problem->free_fun ();
810 free (df->postorder);
811 if (df->postorder_inverted)
812 free (df->postorder_inverted);
813 free (df->hard_regs_live_count);
817 bitmap_obstack_release (&df_bitmap_obstack);
822 struct tree_opt_pass pass_df_finish =
824 "dfinish", /* name */
826 rest_of_handle_df_finish, /* execute */
829 0, /* static_pass_number */
831 0, /* properties_required */
832 0, /* properties_provided */
833 0, /* properties_destroyed */
834 0, /* todo_flags_start */
835 0, /* todo_flags_finish */
843 /*----------------------------------------------------------------------------
844 The general data flow analysis engine.
845 ----------------------------------------------------------------------------*/
848 /* Helper function for df_worklist_dataflow.
849 Propagate the dataflow forward.
850 Given a BB_INDEX, do the dataflow propagation
851 and set bits on for successors in PENDING
852 if the out set of the dataflow has changed. */
855 df_worklist_propagate_forward (struct dataflow *dataflow,
857 unsigned *bbindex_to_postorder,
863 basic_block bb = BASIC_BLOCK (bb_index);
865 /* Calculate <conf_op> of incoming edges. */
866 if (EDGE_COUNT (bb->preds) > 0)
867 FOR_EACH_EDGE (e, ei, bb->preds)
869 if (TEST_BIT (considered, e->src->index))
870 dataflow->problem->con_fun_n (e);
872 else if (dataflow->problem->con_fun_0)
873 dataflow->problem->con_fun_0 (bb);
875 if (dataflow->problem->trans_fun (bb_index))
877 /* The out set of this block has changed.
878 Propagate to the outgoing blocks. */
879 FOR_EACH_EDGE (e, ei, bb->succs)
881 unsigned ob_index = e->dest->index;
883 if (TEST_BIT (considered, ob_index))
884 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
890 /* Helper function for df_worklist_dataflow.
891 Propagate the dataflow backward. */
894 df_worklist_propagate_backward (struct dataflow *dataflow,
896 unsigned *bbindex_to_postorder,
902 basic_block bb = BASIC_BLOCK (bb_index);
904 /* Calculate <conf_op> of incoming edges. */
905 if (EDGE_COUNT (bb->succs) > 0)
906 FOR_EACH_EDGE (e, ei, bb->succs)
908 if (TEST_BIT (considered, e->dest->index))
909 dataflow->problem->con_fun_n (e);
911 else if (dataflow->problem->con_fun_0)
912 dataflow->problem->con_fun_0 (bb);
914 if (dataflow->problem->trans_fun (bb_index))
916 /* The out set of this block has changed.
917 Propagate to the outgoing blocks. */
918 FOR_EACH_EDGE (e, ei, bb->preds)
920 unsigned ob_index = e->src->index;
922 if (TEST_BIT (considered, ob_index))
923 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
929 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
930 with "n"-th bit representing the n-th block in the reverse-postorder order.
931 This is so-called over-eager algorithm where it propagates
932 changes on demand. This algorithm may visit blocks more than
933 iterative method if there are deeply nested loops.
934 Worklist algorithm works better than iterative algorithm
935 for CFGs with no nested loops.
936 In practice, the measurement shows worklist algorithm beats
937 iterative algorithm by some margin overall.
938 Note that this is slightly different from the traditional textbook worklist solver,
939 in that the worklist is effectively sorted by the reverse postorder.
940 For CFGs with no nested loops, this is optimal. */
943 df_worklist_dataflow (struct dataflow *dataflow,
944 bitmap blocks_to_consider,
945 int *blocks_in_postorder,
948 bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
949 sbitmap considered = sbitmap_alloc (last_basic_block);
951 unsigned int *bbindex_to_postorder;
954 enum df_flow_dir dir = dataflow->problem->dir;
956 gcc_assert (dir != DF_NONE);
958 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
959 bbindex_to_postorder =
960 (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
962 /* Initialize the array to an out-of-bound value. */
963 for (i = 0; i < last_basic_block; i++)
964 bbindex_to_postorder[i] = last_basic_block;
966 /* Initialize the considered map. */
967 sbitmap_zero (considered);
968 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
970 SET_BIT (considered, index);
973 /* Initialize the mapping of block index to postorder. */
974 for (i = 0; i < n_blocks; i++)
976 bbindex_to_postorder[blocks_in_postorder[i]] = i;
977 /* Add all blocks to the worklist. */
978 bitmap_set_bit (pending, i);
981 if (dataflow->problem->init_fun)
982 dataflow->problem->init_fun (blocks_to_consider);
984 while (!bitmap_empty_p (pending))
988 index = bitmap_first_set_bit (pending);
989 bitmap_clear_bit (pending, index);
991 bb_index = blocks_in_postorder[index];
993 if (dir == DF_FORWARD)
994 df_worklist_propagate_forward (dataflow, bb_index,
995 bbindex_to_postorder,
996 pending, considered);
998 df_worklist_propagate_backward (dataflow, bb_index,
999 bbindex_to_postorder,
1000 pending, considered);
1003 BITMAP_FREE (pending);
1004 sbitmap_free (considered);
1005 free (bbindex_to_postorder);
1009 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1010 the order of the remaining entries. Returns the length of the resulting
1014 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1018 for (act = 0, last = 0; act < len; act++)
1019 if (bitmap_bit_p (blocks, list[act]))
1020 list[last++] = list[act];
1026 /* Execute dataflow analysis on a single dataflow problem.
1028 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1029 examined or will be computed. For calls from DF_ANALYZE, this is
1030 the set of blocks that has been passed to DF_SET_BLOCKS.
1034 df_analyze_problem (struct dataflow *dflow,
1035 bitmap blocks_to_consider,
1036 int *postorder, int n_blocks)
1038 timevar_push (dflow->problem->tv_id);
1040 #ifdef ENABLE_DF_CHECKING
1041 if (dflow->problem->verify_start_fun)
1042 dflow->problem->verify_start_fun ();
1045 /* (Re)Allocate the datastructures necessary to solve the problem. */
1046 if (dflow->problem->alloc_fun)
1047 dflow->problem->alloc_fun (blocks_to_consider);
1049 /* Set up the problem and compute the local information. */
1050 if (dflow->problem->local_compute_fun)
1051 dflow->problem->local_compute_fun (blocks_to_consider);
1053 /* Solve the equations. */
1054 if (dflow->problem->dataflow_fun)
1055 dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1056 postorder, n_blocks);
1058 /* Massage the solution. */
1059 if (dflow->problem->finalize_fun)
1060 dflow->problem->finalize_fun (blocks_to_consider);
1062 #ifdef ENABLE_DF_CHECKING
1063 if (dflow->problem->verify_end_fun)
1064 dflow->problem->verify_end_fun ();
1067 timevar_pop (dflow->problem->tv_id);
1069 dflow->computed = true;
1073 /* Analyze dataflow info for the basic blocks specified by the bitmap
1074 BLOCKS, or for the whole CFG if BLOCKS is zero. */
1079 bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1084 free (df->postorder);
1085 if (df->postorder_inverted)
1086 free (df->postorder_inverted);
1087 df->postorder = XNEWVEC (int, last_basic_block);
1088 df->postorder_inverted = XNEWVEC (int, last_basic_block);
1089 df->n_blocks = post_order_compute (df->postorder, true, true);
1090 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1092 /* These should be the same. */
1093 gcc_assert (df->n_blocks == df->n_blocks_inverted);
1095 /* We need to do this before the df_verify_all because this is
1096 not kept incrementally up to date. */
1097 df_compute_regs_ever_live (false);
1098 df_process_deferred_rescans ();
1101 fprintf (dump_file, "df_analyze called\n");
1103 #ifdef ENABLE_DF_CHECKING
1107 for (i = 0; i < df->n_blocks; i++)
1108 bitmap_set_bit (current_all_blocks, df->postorder[i]);
1110 #ifdef ENABLE_CHECKING
1111 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1113 for (i = 0; i < df->n_blocks_inverted; i++)
1114 gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1117 /* Make sure that we have pruned any unreachable blocks from these
1119 if (df->analyze_subset)
1122 bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1123 df->n_blocks = df_prune_to_subcfg (df->postorder,
1124 df->n_blocks, df->blocks_to_analyze);
1125 df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1126 df->n_blocks_inverted,
1127 df->blocks_to_analyze);
1128 BITMAP_FREE (current_all_blocks);
1133 df->blocks_to_analyze = current_all_blocks;
1134 current_all_blocks = NULL;
1137 /* Skip over the DF_SCAN problem. */
1138 for (i = 1; i < df->num_problems_defined; i++)
1140 struct dataflow *dflow = df->problems_in_order[i];
1141 if (dflow->solutions_dirty)
1143 if (dflow->problem->dir == DF_FORWARD)
1144 df_analyze_problem (dflow,
1145 df->blocks_to_analyze,
1146 df->postorder_inverted,
1147 df->n_blocks_inverted);
1149 df_analyze_problem (dflow,
1150 df->blocks_to_analyze,
1158 BITMAP_FREE (df->blocks_to_analyze);
1159 df->blocks_to_analyze = NULL;
1163 df_set_clean_cfg ();
1168 /* Return the number of basic blocks from the last call to df_analyze. */
1171 df_get_n_blocks (enum df_flow_dir dir)
1173 gcc_assert (dir != DF_NONE);
1175 if (dir == DF_FORWARD)
1177 gcc_assert (df->postorder_inverted);
1178 return df->n_blocks_inverted;
1181 gcc_assert (df->postorder);
1182 return df->n_blocks;
1186 /* Return a pointer to the array of basic blocks in the reverse postorder.
1187 Depending on the direction of the dataflow problem,
1188 it returns either the usual reverse postorder array
1189 or the reverse postorder of inverted traversal. */
1191 df_get_postorder (enum df_flow_dir dir)
1193 gcc_assert (dir != DF_NONE);
1195 if (dir == DF_FORWARD)
1197 gcc_assert (df->postorder_inverted);
1198 return df->postorder_inverted;
1200 gcc_assert (df->postorder);
1201 return df->postorder;
1204 static struct df_problem user_problem;
1205 static struct dataflow user_dflow;
1207 /* Interface for calling iterative dataflow with user defined
1208 confluence and transfer functions. All that is necessary is to
1209 supply DIR, a direction, CONF_FUN_0, a confluence function for
1210 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1211 confluence function, TRANS_FUN, the basic block transfer function,
1212 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1213 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1216 df_simple_dataflow (enum df_flow_dir dir,
1217 df_init_function init_fun,
1218 df_confluence_function_0 con_fun_0,
1219 df_confluence_function_n con_fun_n,
1220 df_transfer_function trans_fun,
1221 bitmap blocks, int * postorder, int n_blocks)
1223 memset (&user_problem, 0, sizeof (struct df_problem));
1224 user_problem.dir = dir;
1225 user_problem.init_fun = init_fun;
1226 user_problem.con_fun_0 = con_fun_0;
1227 user_problem.con_fun_n = con_fun_n;
1228 user_problem.trans_fun = trans_fun;
1229 user_dflow.problem = &user_problem;
1230 df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1235 /*----------------------------------------------------------------------------
1236 Functions to support limited incremental change.
1237 ----------------------------------------------------------------------------*/
1240 /* Get basic block info. */
1243 df_get_bb_info (struct dataflow *dflow, unsigned int index)
1245 if (dflow->block_info == NULL)
1247 if (index >= dflow->block_info_size)
1249 return (struct df_scan_bb_info *) dflow->block_info[index];
1253 /* Set basic block info. */
1256 df_set_bb_info (struct dataflow *dflow, unsigned int index,
1259 gcc_assert (dflow->block_info);
1260 dflow->block_info[index] = bb_info;
1264 /* Mark the solutions as being out of date. */
1267 df_mark_solutions_dirty (void)
1272 for (p = 1; p < df->num_problems_defined; p++)
1273 df->problems_in_order[p]->solutions_dirty = true;
1278 /* Return true if BB needs it's transfer functions recomputed. */
1281 df_get_bb_dirty (basic_block bb)
1284 return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
1290 /* Mark BB as needing it's transfer functions as being out of
1294 df_set_bb_dirty (basic_block bb)
1299 for (p = 1; p < df->num_problems_defined; p++)
1301 struct dataflow *dflow = df->problems_in_order[p];
1302 if (dflow->out_of_date_transfer_functions)
1303 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1305 df_mark_solutions_dirty ();
1310 /* Clear the dirty bits. This is called from places that delete
1313 df_clear_bb_dirty (basic_block bb)
1316 for (p = 1; p < df->num_problems_defined; p++)
1318 struct dataflow *dflow = df->problems_in_order[p];
1319 if (dflow->out_of_date_transfer_functions)
1320 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1323 /* Called from the rtl_compact_blocks to reorganize the problems basic
1327 df_compact_blocks (void)
1331 void **problem_temps;
1332 int size = last_basic_block * sizeof (void *);
1333 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1334 problem_temps = xmalloc (size);
1336 for (p = 0; p < df->num_problems_defined; p++)
1338 struct dataflow *dflow = df->problems_in_order[p];
1340 /* Need to reorganize the out_of_date_transfer_functions for the
1342 if (dflow->out_of_date_transfer_functions)
1344 bitmap_copy (tmp, dflow->out_of_date_transfer_functions);
1345 bitmap_clear (dflow->out_of_date_transfer_functions);
1346 if (bitmap_bit_p (tmp, ENTRY_BLOCK))
1347 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1348 if (bitmap_bit_p (tmp, EXIT_BLOCK))
1349 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1351 i = NUM_FIXED_BLOCKS;
1354 if (bitmap_bit_p (tmp, bb->index))
1355 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1360 /* Now shuffle the block info for the problem. */
1361 if (dflow->problem->free_bb_fun)
1363 df_grow_bb_info (dflow);
1364 memcpy (problem_temps, dflow->block_info, size);
1366 /* Copy the bb info from the problem tmps to the proper
1367 place in the block_info vector. Null out the copied
1368 item. The entry and exit blocks never move. */
1369 i = NUM_FIXED_BLOCKS;
1372 df_set_bb_info (dflow, i, problem_temps[bb->index]);
1373 problem_temps[bb->index] = NULL;
1376 memset (dflow->block_info + i, 0,
1377 (last_basic_block - i) *sizeof (void *));
1379 /* Free any block infos that were not copied (and NULLed).
1380 These are from orphaned blocks. */
1381 for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
1383 basic_block bb = BASIC_BLOCK (i);
1384 if (problem_temps[i] && bb)
1385 dflow->problem->free_bb_fun
1386 (bb, problem_temps[i]);
1391 /* Shuffle the bits in the basic_block indexed arrays. */
1393 if (df->blocks_to_analyze)
1395 if (bitmap_bit_p (tmp, ENTRY_BLOCK))
1396 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1397 if (bitmap_bit_p (tmp, EXIT_BLOCK))
1398 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1399 bitmap_copy (tmp, df->blocks_to_analyze);
1400 bitmap_clear (df->blocks_to_analyze);
1401 i = NUM_FIXED_BLOCKS;
1404 if (bitmap_bit_p (tmp, bb->index))
1405 bitmap_set_bit (df->blocks_to_analyze, i);
1412 free (problem_temps);
1414 i = NUM_FIXED_BLOCKS;
1417 SET_BASIC_BLOCK (i, bb);
1422 gcc_assert (i == n_basic_blocks);
1424 for (; i < last_basic_block; i++)
1425 SET_BASIC_BLOCK (i, NULL);
1428 if (!df_lr->solutions_dirty)
1429 df_set_clean_cfg ();
1434 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1435 block. There is no excuse for people to do this kind of thing. */
1438 df_bb_replace (int old_index, basic_block new_block)
1440 int new_block_index = new_block->index;
1444 fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1447 gcc_assert (BASIC_BLOCK (old_index) == NULL);
1449 for (p = 0; p < df->num_problems_defined; p++)
1451 struct dataflow *dflow = df->problems_in_order[p];
1452 if (dflow->block_info)
1454 df_grow_bb_info (dflow);
1455 gcc_assert (df_get_bb_info (dflow, old_index) == NULL);
1456 df_set_bb_info (dflow, old_index,
1457 df_get_bb_info (dflow, new_block_index));
1461 df_clear_bb_dirty (new_block);
1462 SET_BASIC_BLOCK (old_index, new_block);
1463 new_block->index = old_index;
1464 df_set_bb_dirty (BASIC_BLOCK (old_index));
1465 SET_BASIC_BLOCK (new_block_index, NULL);
1469 /* Free all of the per basic block dataflow from all of the problems.
1470 This is typically called before a basic block is deleted and the
1471 problem will be reanalyzed. */
1474 df_bb_delete (int bb_index)
1476 basic_block bb = BASIC_BLOCK (bb_index);
1482 for (i = 0; i < df->num_problems_defined; i++)
1484 struct dataflow *dflow = df->problems_in_order[i];
1485 if (dflow->problem->free_bb_fun)
1487 void *bb_info = df_get_bb_info (dflow, bb_index);
1490 dflow->problem->free_bb_fun (bb, bb_info);
1491 df_set_bb_info (dflow, bb_index, NULL);
1495 df_clear_bb_dirty (bb);
1496 df_mark_solutions_dirty ();
1500 /* Verify that there is a place for everything and everything is in
1501 its place. This is too expensive to run after every pass in the
1502 mainline. However this is an excellent debugging tool if the
1503 dataflow information is not being updated properly. You can just
1504 sprinkle calls in until you find the place that is changing an
1505 underlying structure without calling the proper updating
1512 df_lr_verify_transfer_functions ();
1514 df_live_verify_transfer_functions ();
1519 /* Compute an array of ints that describes the cfg. This can be used
1520 to discover places where the cfg is modified by the appropriate
1521 calls have not been made to the keep df informed. The internals of
1522 this are unexciting, the key is that two instances of this can be
1523 compared to see if any changes have been made to the cfg. */
1526 df_compute_cfg_image (void)
1529 int size = 2 + (2 * n_basic_blocks);
1535 size += EDGE_COUNT (bb->succs);
1538 map = XNEWVEC (int, size);
1546 map[i++] = bb->index;
1547 FOR_EACH_EDGE (e, ei, bb->succs)
1548 map[i++] = e->dest->index;
1555 static int *saved_cfg = NULL;
1558 /* This function compares the saved version of the cfg with the
1559 current cfg and aborts if the two are identical. The function
1560 silently returns if the cfg has been marked as dirty or the two are
1564 df_check_cfg_clean (void)
1571 if (df_lr->solutions_dirty)
1574 if (saved_cfg == NULL)
1577 new_map = df_compute_cfg_image ();
1578 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1583 /* This function builds a cfg fingerprint and squirrels it away in
1587 df_set_clean_cfg (void)
1591 saved_cfg = df_compute_cfg_image ();
1594 #endif /* DF_DEBUG_CFG */
1595 /*----------------------------------------------------------------------------
1596 PUBLIC INTERFACES TO QUERY INFORMATION.
1597 ----------------------------------------------------------------------------*/
1600 /* Return first def of REGNO within BB. */
1603 df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1606 struct df_ref **def_rec;
1609 FOR_BB_INSNS (bb, insn)
1614 uid = INSN_UID (insn);
1615 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1617 struct df_ref *def = *def_rec;
1618 if (DF_REF_REGNO (def) == regno)
1626 /* Return last def of REGNO within BB. */
1629 df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1632 struct df_ref **def_rec;
1635 FOR_BB_INSNS_REVERSE (bb, insn)
1640 uid = INSN_UID (insn);
1641 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1643 struct df_ref *def = *def_rec;
1644 if (DF_REF_REGNO (def) == regno)
1652 /* Finds the reference corresponding to the definition of REG in INSN.
1653 DF is the dataflow object. */
1656 df_find_def (rtx insn, rtx reg)
1659 struct df_ref **def_rec;
1661 if (GET_CODE (reg) == SUBREG)
1662 reg = SUBREG_REG (reg);
1663 gcc_assert (REG_P (reg));
1665 uid = INSN_UID (insn);
1666 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1668 struct df_ref *def = *def_rec;
1669 if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1677 /* Return true if REG is defined in INSN, zero otherwise. */
1680 df_reg_defined (rtx insn, rtx reg)
1682 return df_find_def (insn, reg) != NULL;
1686 /* Finds the reference corresponding to the use of REG in INSN.
1687 DF is the dataflow object. */
1690 df_find_use (rtx insn, rtx reg)
1693 struct df_ref **use_rec;
1695 if (GET_CODE (reg) == SUBREG)
1696 reg = SUBREG_REG (reg);
1697 gcc_assert (REG_P (reg));
1699 uid = INSN_UID (insn);
1700 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1702 struct df_ref *use = *use_rec;
1703 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1706 if (df->changeable_flags & DF_EQ_NOTES)
1707 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1709 struct df_ref *use = *use_rec;
1710 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1717 /* Return true if REG is referenced in INSN, zero otherwise. */
1720 df_reg_used (rtx insn, rtx reg)
1722 return df_find_use (insn, reg) != NULL;
1726 /*----------------------------------------------------------------------------
1727 Debugging and printing functions.
1728 ----------------------------------------------------------------------------*/
1731 /* Write information about registers and basic blocks into FILE.
1732 This is part of making a debugging dump. */
1735 df_print_regset (FILE *file, bitmap r)
1741 fputs (" (nil)", file);
1744 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1746 fprintf (file, " %d", i);
1747 if (i < FIRST_PSEUDO_REGISTER)
1748 fprintf (file, " [%s]", reg_names[i]);
1751 fprintf (file, "\n");
1755 /* Dump dataflow info. */
1757 df_dump (FILE *file)
1760 df_dump_start (file);
1764 df_print_bb_index (bb, file);
1765 df_dump_top (bb, file);
1766 df_dump_bottom (bb, file);
1769 fprintf (file, "\n");
1773 /* Dump the introductory information for each problem defined. */
1776 df_dump_start (FILE *file)
1783 fprintf (file, "\n\n%s\n", current_function_name ());
1784 fprintf (file, "\nDataflow summary:\n");
1785 if (df->blocks_to_analyze)
1786 fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
1787 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1789 for (i = 0; i < df->num_problems_defined; i++)
1791 struct dataflow *dflow = df->problems_in_order[i];
1792 if (dflow->computed)
1794 df_dump_problem_function fun = dflow->problem->dump_start_fun;
1802 /* Dump the top of the block information for BB. */
1805 df_dump_top (basic_block bb, FILE *file)
1812 for (i = 0; i < df->num_problems_defined; i++)
1814 struct dataflow *dflow = df->problems_in_order[i];
1815 if (dflow->computed)
1817 df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
1825 /* Dump the bottom of the block information for BB. */
1828 df_dump_bottom (basic_block bb, FILE *file)
1835 for (i = 0; i < df->num_problems_defined; i++)
1837 struct dataflow *dflow = df->problems_in_order[i];
1838 if (dflow->computed)
1840 df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
1849 df_refs_chain_dump (struct df_ref **ref_rec, bool follow_chain, FILE *file)
1851 fprintf (file, "{ ");
1854 struct df_ref *ref = *ref_rec;
1855 fprintf (file, "%c%d(%d)",
1856 DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
1858 DF_REF_REGNO (ref));
1860 df_chain_dump (DF_REF_CHAIN (ref), file);
1863 fprintf (file, "}");
1867 /* Dump either a ref-def or reg-use chain. */
1870 df_regs_chain_dump (struct df_ref *ref, FILE *file)
1872 fprintf (file, "{ ");
1875 fprintf (file, "%c%d(%d) ",
1876 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1878 DF_REF_REGNO (ref));
1879 ref = ref->next_reg;
1881 fprintf (file, "}");
1886 df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
1890 fprintf (file, "mw %c r[%d..%d]\n",
1891 ((*mws)->type == DF_REF_REG_DEF) ? 'd' : 'u',
1892 (*mws)->start_regno, (*mws)->end_regno);
1899 df_insn_uid_debug (unsigned int uid,
1900 bool follow_chain, FILE *file)
1902 fprintf (file, "insn %d luid %d",
1903 uid, DF_INSN_UID_LUID (uid));
1905 if (DF_INSN_UID_DEFS (uid))
1907 fprintf (file, " defs ");
1908 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
1911 if (DF_INSN_UID_USES (uid))
1913 fprintf (file, " uses ");
1914 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
1917 if (DF_INSN_UID_EQ_USES (uid))
1919 fprintf (file, " eq uses ");
1920 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
1923 if (DF_INSN_UID_MWS (uid))
1925 fprintf (file, " mws ");
1926 df_mws_dump (DF_INSN_UID_MWS (uid), file);
1928 fprintf (file, "\n");
1933 df_insn_debug (rtx insn, bool follow_chain, FILE *file)
1935 df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
1939 df_insn_debug_regno (rtx insn, FILE *file)
1941 unsigned int uid = INSN_UID(insn);
1943 fprintf (file, "insn %d bb %d luid %d defs ",
1944 uid, BLOCK_FOR_INSN (insn)->index, DF_INSN_LUID (insn));
1945 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), false, file);
1947 fprintf (file, " uses ");
1948 df_refs_chain_dump (DF_INSN_UID_USES (uid), false, file);
1950 fprintf (file, " eq_uses ");
1951 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), false, file);
1952 fprintf (file, "\n");
1956 df_regno_debug (unsigned int regno, FILE *file)
1958 fprintf (file, "reg %d defs ", regno);
1959 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
1960 fprintf (file, " uses ");
1961 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
1962 fprintf (file, " eq_uses ");
1963 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
1964 fprintf (file, "\n");
1969 df_ref_debug (struct df_ref *ref, FILE *file)
1971 fprintf (file, "%c%d ",
1972 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1974 fprintf (file, "reg %d bb %d insn %d flag 0x%x type 0x%x ",
1977 DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1,
1980 if (DF_REF_LOC (ref))
1981 fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref), (void *)*DF_REF_LOC (ref));
1983 fprintf (file, "chain ");
1984 df_chain_dump (DF_REF_CHAIN (ref), file);
1985 fprintf (file, "\n");
1988 /* Functions for debugging from GDB. */
1991 debug_df_insn (rtx insn)
1993 df_insn_debug (insn, true, stderr);
1999 debug_df_reg (rtx reg)
2001 df_regno_debug (REGNO (reg), stderr);
2006 debug_df_regno (unsigned int regno)
2008 df_regno_debug (regno, stderr);
2013 debug_df_ref (struct df_ref *ref)
2015 df_ref_debug (ref, stderr);
2020 debug_df_defno (unsigned int defno)
2022 df_ref_debug (DF_DEFS_GET (defno), stderr);
2027 debug_df_useno (unsigned int defno)
2029 df_ref_debug (DF_USES_GET (defno), stderr);
2034 debug_df_chain (struct df_link *link)
2036 df_chain_dump (link, stderr);
2037 fputc ('\n', stderr);