1 /* Allocation for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008, 2009, 2010 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
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 that 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 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_[chain,live,note,rd]_add_problem (flags);
76 df_set_blocks (blocks);
82 df_finish_pass (false);
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.
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 upon 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 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.
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.
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.
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
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.
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.
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
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.
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.
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.
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.
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.
250 The basic object is a DF_REF (reference) and this may either be a
251 DEF (definition) or a USE of a register.
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
259 Note that the reg-def and reg-use chains are generally short for
260 pseudos and long for the hard registers.
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.
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.
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.
290 There are 4 ways to obtain access to refs:
292 1) References are divided into two categories, REAL and ARTIFICIAL.
294 REAL refs are associated with instructions.
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.
300 Artificial defs and uses occur both at the beginning and ends of blocks.
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.
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
315 Artificial defs occur at the end of the entry block. These arise
316 from registers that are live at entry to the function.
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.)
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.
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.
334 In previous versions of this code, these chains were ordered. It
335 has not been practical to continue this practice.
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
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.
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.
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.
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
373 Paradoxical subreg writes do not leave a trace of the old content, so they
374 are write-only operations.
380 #include "coretypes.h"
384 #include "insn-config.h"
386 #include "function.h"
389 #include "alloc-pool.h"
391 #include "hard-reg-set.h"
392 #include "basic-block.h"
397 #include "tree-pass.h"
400 static void *df_get_bb_info (struct dataflow *, unsigned int);
401 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
402 static void df_clear_bb_info (struct dataflow *, unsigned int);
404 static void df_set_clean_cfg (void);
407 /* An obstack for bitmap not related to specific dataflow problems.
408 This obstack should e.g. be used for bitmaps with a short life time
409 such as temporary bitmaps. */
411 bitmap_obstack df_bitmap_obstack;
414 /*----------------------------------------------------------------------------
415 Functions to create, destroy and manipulate an instance of df.
416 ----------------------------------------------------------------------------*/
420 /* Add PROBLEM (and any dependent problems) to the DF instance. */
423 df_add_problem (struct df_problem *problem)
425 struct dataflow *dflow;
428 /* First try to add the dependent problem. */
429 if (problem->dependent_problem)
430 df_add_problem (problem->dependent_problem);
432 /* Check to see if this problem has already been defined. If it
433 has, just return that instance, if not, add it to the end of the
435 dflow = df->problems_by_index[problem->id];
439 /* Make a new one and add it to the end. */
440 dflow = XCNEW (struct dataflow);
441 dflow->problem = problem;
442 dflow->computed = false;
443 dflow->solutions_dirty = true;
444 df->problems_by_index[dflow->problem->id] = dflow;
446 /* Keep the defined problems ordered by index. This solves the
447 problem that RI will use the information from UREC if UREC has
448 been defined, or from LIVE if LIVE is defined and otherwise LR.
449 However for this to work, the computation of RI must be pushed
450 after which ever of those problems is defined, but we do not
451 require any of those except for LR to have actually been
453 df->num_problems_defined++;
454 for (i = df->num_problems_defined - 2; i >= 0; i--)
456 if (problem->id < df->problems_in_order[i]->problem->id)
457 df->problems_in_order[i+1] = df->problems_in_order[i];
460 df->problems_in_order[i+1] = dflow;
464 df->problems_in_order[0] = dflow;
468 /* Set the MASK flags in the DFLOW problem. The old flags are
469 returned. If a flag is not allowed to be changed this will fail if
470 checking is enabled. */
472 df_set_flags (int changeable_flags)
474 int old_flags = df->changeable_flags;
475 df->changeable_flags |= changeable_flags;
480 /* Clear the MASK flags in the DFLOW problem. The old flags are
481 returned. If a flag is not allowed to be changed this will fail if
482 checking is enabled. */
484 df_clear_flags (int changeable_flags)
486 int old_flags = df->changeable_flags;
487 df->changeable_flags &= ~changeable_flags;
492 /* Set the blocks that are to be considered for analysis. If this is
493 not called or is called with null, the entire function in
497 df_set_blocks (bitmap blocks)
502 bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
503 if (df->blocks_to_analyze)
505 /* This block is called to change the focus from one subset
509 bitmap_initialize (&diff, &df_bitmap_obstack);
510 bitmap_and_compl (&diff, df->blocks_to_analyze, blocks);
511 for (p = 0; p < df->num_problems_defined; p++)
513 struct dataflow *dflow = df->problems_in_order[p];
514 if (dflow->optional_p && dflow->problem->reset_fun)
515 dflow->problem->reset_fun (df->blocks_to_analyze);
516 else if (dflow->problem->free_blocks_on_set_blocks)
519 unsigned int bb_index;
521 EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
523 basic_block bb = BASIC_BLOCK (bb_index);
526 void *bb_info = df_get_bb_info (dflow, bb_index);
527 dflow->problem->free_bb_fun (bb, bb_info);
528 df_clear_bb_info (dflow, bb_index);
534 bitmap_clear (&diff);
538 /* This block of code is executed to change the focus from
539 the entire function to a subset. */
540 bitmap_head blocks_to_reset;
541 bool initialized = false;
543 for (p = 0; p < df->num_problems_defined; p++)
545 struct dataflow *dflow = df->problems_in_order[p];
546 if (dflow->optional_p && dflow->problem->reset_fun)
551 bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack);
554 bitmap_set_bit (&blocks_to_reset, bb->index);
557 dflow->problem->reset_fun (&blocks_to_reset);
561 bitmap_clear (&blocks_to_reset);
563 df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
565 bitmap_copy (df->blocks_to_analyze, blocks);
566 df->analyze_subset = true;
570 /* This block is executed to reset the focus to the entire
573 fprintf (dump_file, "clearing blocks_to_analyze\n");
574 if (df->blocks_to_analyze)
576 BITMAP_FREE (df->blocks_to_analyze);
577 df->blocks_to_analyze = NULL;
579 df->analyze_subset = false;
582 /* Setting the blocks causes the refs to be unorganized since only
583 the refs in the blocks are seen. */
584 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
585 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
586 df_mark_solutions_dirty ();
590 /* Delete a DFLOW problem (and any problems that depend on this
594 df_remove_problem (struct dataflow *dflow)
596 struct df_problem *problem;
602 problem = dflow->problem;
603 gcc_assert (problem->remove_problem_fun);
605 /* Delete any problems that depended on this problem first. */
606 for (i = 0; i < df->num_problems_defined; i++)
607 if (df->problems_in_order[i]->problem->dependent_problem == problem)
608 df_remove_problem (df->problems_in_order[i]);
610 /* Now remove this problem. */
611 for (i = 0; i < df->num_problems_defined; i++)
612 if (df->problems_in_order[i] == dflow)
615 for (j = i + 1; j < df->num_problems_defined; j++)
616 df->problems_in_order[j-1] = df->problems_in_order[j];
617 df->problems_in_order[j-1] = NULL;
618 df->num_problems_defined--;
622 (problem->remove_problem_fun) ();
623 df->problems_by_index[problem->id] = NULL;
627 /* Remove all of the problems that are not permanent. Scanning, LR
628 and (at -O2 or higher) LIVE are permanent, the rest are removable.
629 Also clear all of the changeable_flags. */
632 df_finish_pass (bool verify ATTRIBUTE_UNUSED)
637 #ifdef ENABLE_DF_CHECKING
644 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
645 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
647 #ifdef ENABLE_DF_CHECKING
648 saved_flags = df->changeable_flags;
651 for (i = 0; i < df->num_problems_defined; i++)
653 struct dataflow *dflow = df->problems_in_order[i];
654 struct df_problem *problem = dflow->problem;
656 if (dflow->optional_p)
658 gcc_assert (problem->remove_problem_fun);
659 (problem->remove_problem_fun) ();
660 df->problems_in_order[i] = NULL;
661 df->problems_by_index[problem->id] = NULL;
665 df->num_problems_defined -= removed;
667 /* Clear all of the flags. */
668 df->changeable_flags = 0;
669 df_process_deferred_rescans ();
671 /* Set the focus back to the whole function. */
672 if (df->blocks_to_analyze)
674 BITMAP_FREE (df->blocks_to_analyze);
675 df->blocks_to_analyze = NULL;
676 df_mark_solutions_dirty ();
677 df->analyze_subset = false;
680 #ifdef ENABLE_DF_CHECKING
681 /* Verification will fail in DF_NO_INSN_RESCAN. */
682 if (!(saved_flags & DF_NO_INSN_RESCAN))
684 df_lr_verify_transfer_functions ();
686 df_live_verify_transfer_functions ();
694 #ifdef ENABLE_CHECKING
696 df->changeable_flags |= DF_VERIFY_SCHEDULED;
701 /* Set up the dataflow instance for the entire back end. */
704 rest_of_handle_df_initialize (void)
707 df = XCNEW (struct df);
708 df->changeable_flags = 0;
710 bitmap_obstack_initialize (&df_bitmap_obstack);
712 /* Set this to a conservative value. Stack_ptr_mod will compute it
714 current_function_sp_is_unchanging = 0;
716 df_scan_add_problem ();
717 df_scan_alloc (NULL);
719 /* These three problems are permanent. */
720 df_lr_add_problem ();
722 df_live_add_problem ();
724 df->postorder = XNEWVEC (int, last_basic_block);
725 df->postorder_inverted = XNEWVEC (int, last_basic_block);
726 df->n_blocks = post_order_compute (df->postorder, true, true);
727 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
728 gcc_assert (df->n_blocks == df->n_blocks_inverted);
730 df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
731 memset (df->hard_regs_live_count, 0,
732 sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
735 /* After reload, some ports add certain bits to regs_ever_live so
736 this cannot be reset. */
737 df_compute_regs_ever_live (true);
739 df_compute_regs_ever_live (false);
751 struct rtl_opt_pass pass_df_initialize_opt =
757 rest_of_handle_df_initialize, /* execute */
760 0, /* static_pass_number */
762 0, /* properties_required */
763 0, /* properties_provided */
764 0, /* properties_destroyed */
765 0, /* todo_flags_start */
766 0 /* todo_flags_finish */
774 return optimize == 0;
778 struct rtl_opt_pass pass_df_initialize_no_opt =
782 "no-opt dfinit", /* name */
783 gate_no_opt, /* gate */
784 rest_of_handle_df_initialize, /* execute */
787 0, /* static_pass_number */
789 0, /* properties_required */
790 0, /* properties_provided */
791 0, /* properties_destroyed */
792 0, /* todo_flags_start */
793 0 /* todo_flags_finish */
798 /* Free all the dataflow info and the DF structure. This should be
799 called from the df_finish macro which also NULLs the parm. */
802 rest_of_handle_df_finish (void)
808 for (i = 0; i < df->num_problems_defined; i++)
810 struct dataflow *dflow = df->problems_in_order[i];
811 dflow->problem->free_fun ();
815 free (df->postorder);
816 if (df->postorder_inverted)
817 free (df->postorder_inverted);
818 free (df->hard_regs_live_count);
822 bitmap_obstack_release (&df_bitmap_obstack);
827 struct rtl_opt_pass pass_df_finish =
831 "dfinish", /* name */
833 rest_of_handle_df_finish, /* execute */
836 0, /* static_pass_number */
838 0, /* properties_required */
839 0, /* properties_provided */
840 0, /* properties_destroyed */
841 0, /* todo_flags_start */
842 0 /* todo_flags_finish */
850 /*----------------------------------------------------------------------------
851 The general data flow analysis engine.
852 ----------------------------------------------------------------------------*/
855 /* Helper function for df_worklist_dataflow.
856 Propagate the dataflow forward.
857 Given a BB_INDEX, do the dataflow propagation
858 and set bits on for successors in PENDING
859 if the out set of the dataflow has changed. */
862 df_worklist_propagate_forward (struct dataflow *dataflow,
864 unsigned *bbindex_to_postorder,
870 basic_block bb = BASIC_BLOCK (bb_index);
872 /* Calculate <conf_op> of incoming edges. */
873 if (EDGE_COUNT (bb->preds) > 0)
874 FOR_EACH_EDGE (e, ei, bb->preds)
876 if (TEST_BIT (considered, e->src->index))
877 dataflow->problem->con_fun_n (e);
879 else if (dataflow->problem->con_fun_0)
880 dataflow->problem->con_fun_0 (bb);
882 if (dataflow->problem->trans_fun (bb_index))
884 /* The out set of this block has changed.
885 Propagate to the outgoing blocks. */
886 FOR_EACH_EDGE (e, ei, bb->succs)
888 unsigned ob_index = e->dest->index;
890 if (TEST_BIT (considered, ob_index))
891 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
897 /* Helper function for df_worklist_dataflow.
898 Propagate the dataflow backward. */
901 df_worklist_propagate_backward (struct dataflow *dataflow,
903 unsigned *bbindex_to_postorder,
909 basic_block bb = BASIC_BLOCK (bb_index);
911 /* Calculate <conf_op> of incoming edges. */
912 if (EDGE_COUNT (bb->succs) > 0)
913 FOR_EACH_EDGE (e, ei, bb->succs)
915 if (TEST_BIT (considered, e->dest->index))
916 dataflow->problem->con_fun_n (e);
918 else if (dataflow->problem->con_fun_0)
919 dataflow->problem->con_fun_0 (bb);
921 if (dataflow->problem->trans_fun (bb_index))
923 /* The out set of this block has changed.
924 Propagate to the outgoing blocks. */
925 FOR_EACH_EDGE (e, ei, bb->preds)
927 unsigned ob_index = e->src->index;
929 if (TEST_BIT (considered, ob_index))
930 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
937 /* This will free "pending". */
940 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
943 int *blocks_in_postorder,
944 unsigned *bbindex_to_postorder)
946 enum df_flow_dir dir = dataflow->problem->dir;
948 bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
950 /* Double-queueing. Worklist is for the current iteration,
951 and pending is for the next. */
952 while (!bitmap_empty_p (pending))
954 /* Swap pending and worklist. */
955 bitmap temp = worklist;
965 index = bitmap_first_set_bit (worklist);
966 bitmap_clear_bit (worklist, index);
968 bb_index = blocks_in_postorder[index];
970 if (dir == DF_FORWARD)
971 df_worklist_propagate_forward (dataflow, bb_index,
972 bbindex_to_postorder,
973 pending, considered);
975 df_worklist_propagate_backward (dataflow, bb_index,
976 bbindex_to_postorder,
977 pending, considered);
979 while (!bitmap_empty_p (worklist));
982 BITMAP_FREE (worklist);
983 BITMAP_FREE (pending);
985 /* Dump statistics. */
987 fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
988 "n_basic_blocks %d n_edges %d"
989 " count %d (%5.2g)\n",
990 n_basic_blocks, n_edges,
991 dcount, dcount / (float)n_basic_blocks);
994 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
995 with "n"-th bit representing the n-th block in the reverse-postorder order.
996 The solver is a double-queue algorithm similar to the "double stack" solver
997 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
998 The only significant difference is that the worklist in this implementation
999 is always sorted in RPO of the CFG visiting direction. */
1002 df_worklist_dataflow (struct dataflow *dataflow,
1003 bitmap blocks_to_consider,
1004 int *blocks_in_postorder,
1007 bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1008 sbitmap considered = sbitmap_alloc (last_basic_block);
1010 unsigned int *bbindex_to_postorder;
1013 enum df_flow_dir dir = dataflow->problem->dir;
1015 gcc_assert (dir != DF_NONE);
1017 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
1018 bbindex_to_postorder =
1019 (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
1021 /* Initialize the array to an out-of-bound value. */
1022 for (i = 0; i < last_basic_block; i++)
1023 bbindex_to_postorder[i] = last_basic_block;
1025 /* Initialize the considered map. */
1026 sbitmap_zero (considered);
1027 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1029 SET_BIT (considered, index);
1032 /* Initialize the mapping of block index to postorder. */
1033 for (i = 0; i < n_blocks; i++)
1035 bbindex_to_postorder[blocks_in_postorder[i]] = i;
1036 /* Add all blocks to the worklist. */
1037 bitmap_set_bit (pending, i);
1040 /* Initialize the problem. */
1041 if (dataflow->problem->init_fun)
1042 dataflow->problem->init_fun (blocks_to_consider);
1045 df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1046 blocks_in_postorder,
1047 bbindex_to_postorder);
1049 sbitmap_free (considered);
1050 free (bbindex_to_postorder);
1054 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1055 the order of the remaining entries. Returns the length of the resulting
1059 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1063 for (act = 0, last = 0; act < len; act++)
1064 if (bitmap_bit_p (blocks, list[act]))
1065 list[last++] = list[act];
1071 /* Execute dataflow analysis on a single dataflow problem.
1073 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1074 examined or will be computed. For calls from DF_ANALYZE, this is
1075 the set of blocks that has been passed to DF_SET_BLOCKS.
1079 df_analyze_problem (struct dataflow *dflow,
1080 bitmap blocks_to_consider,
1081 int *postorder, int n_blocks)
1083 timevar_push (dflow->problem->tv_id);
1085 /* (Re)Allocate the datastructures necessary to solve the problem. */
1086 if (dflow->problem->alloc_fun)
1087 dflow->problem->alloc_fun (blocks_to_consider);
1089 #ifdef ENABLE_DF_CHECKING
1090 if (dflow->problem->verify_start_fun)
1091 dflow->problem->verify_start_fun ();
1094 /* Set up the problem and compute the local information. */
1095 if (dflow->problem->local_compute_fun)
1096 dflow->problem->local_compute_fun (blocks_to_consider);
1098 /* Solve the equations. */
1099 if (dflow->problem->dataflow_fun)
1100 dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1101 postorder, n_blocks);
1103 /* Massage the solution. */
1104 if (dflow->problem->finalize_fun)
1105 dflow->problem->finalize_fun (blocks_to_consider);
1107 #ifdef ENABLE_DF_CHECKING
1108 if (dflow->problem->verify_end_fun)
1109 dflow->problem->verify_end_fun ();
1112 timevar_pop (dflow->problem->tv_id);
1114 dflow->computed = true;
1118 /* Analyze dataflow info for the basic blocks specified by the bitmap
1119 BLOCKS, or for the whole CFG if BLOCKS is zero. */
1124 bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1129 free (df->postorder);
1130 if (df->postorder_inverted)
1131 free (df->postorder_inverted);
1132 df->postorder = XNEWVEC (int, last_basic_block);
1133 df->postorder_inverted = XNEWVEC (int, last_basic_block);
1134 df->n_blocks = post_order_compute (df->postorder, true, true);
1135 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1137 /* These should be the same. */
1138 gcc_assert (df->n_blocks == df->n_blocks_inverted);
1140 /* We need to do this before the df_verify_all because this is
1141 not kept incrementally up to date. */
1142 df_compute_regs_ever_live (false);
1143 df_process_deferred_rescans ();
1146 fprintf (dump_file, "df_analyze called\n");
1148 #ifndef ENABLE_DF_CHECKING
1149 if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1153 for (i = 0; i < df->n_blocks; i++)
1154 bitmap_set_bit (current_all_blocks, df->postorder[i]);
1156 #ifdef ENABLE_CHECKING
1157 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1159 for (i = 0; i < df->n_blocks_inverted; i++)
1160 gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1163 /* Make sure that we have pruned any unreachable blocks from these
1165 if (df->analyze_subset)
1168 bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1169 df->n_blocks = df_prune_to_subcfg (df->postorder,
1170 df->n_blocks, df->blocks_to_analyze);
1171 df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1172 df->n_blocks_inverted,
1173 df->blocks_to_analyze);
1174 BITMAP_FREE (current_all_blocks);
1179 df->blocks_to_analyze = current_all_blocks;
1180 current_all_blocks = NULL;
1183 /* Skip over the DF_SCAN problem. */
1184 for (i = 1; i < df->num_problems_defined; i++)
1186 struct dataflow *dflow = df->problems_in_order[i];
1187 if (dflow->solutions_dirty)
1189 if (dflow->problem->dir == DF_FORWARD)
1190 df_analyze_problem (dflow,
1191 df->blocks_to_analyze,
1192 df->postorder_inverted,
1193 df->n_blocks_inverted);
1195 df_analyze_problem (dflow,
1196 df->blocks_to_analyze,
1204 BITMAP_FREE (df->blocks_to_analyze);
1205 df->blocks_to_analyze = NULL;
1209 df_set_clean_cfg ();
1214 /* Return the number of basic blocks from the last call to df_analyze. */
1217 df_get_n_blocks (enum df_flow_dir dir)
1219 gcc_assert (dir != DF_NONE);
1221 if (dir == DF_FORWARD)
1223 gcc_assert (df->postorder_inverted);
1224 return df->n_blocks_inverted;
1227 gcc_assert (df->postorder);
1228 return df->n_blocks;
1232 /* Return a pointer to the array of basic blocks in the reverse postorder.
1233 Depending on the direction of the dataflow problem,
1234 it returns either the usual reverse postorder array
1235 or the reverse postorder of inverted traversal. */
1237 df_get_postorder (enum df_flow_dir dir)
1239 gcc_assert (dir != DF_NONE);
1241 if (dir == DF_FORWARD)
1243 gcc_assert (df->postorder_inverted);
1244 return df->postorder_inverted;
1246 gcc_assert (df->postorder);
1247 return df->postorder;
1250 static struct df_problem user_problem;
1251 static struct dataflow user_dflow;
1253 /* Interface for calling iterative dataflow with user defined
1254 confluence and transfer functions. All that is necessary is to
1255 supply DIR, a direction, CONF_FUN_0, a confluence function for
1256 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1257 confluence function, TRANS_FUN, the basic block transfer function,
1258 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1259 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1262 df_simple_dataflow (enum df_flow_dir dir,
1263 df_init_function init_fun,
1264 df_confluence_function_0 con_fun_0,
1265 df_confluence_function_n con_fun_n,
1266 df_transfer_function trans_fun,
1267 bitmap blocks, int * postorder, int n_blocks)
1269 memset (&user_problem, 0, sizeof (struct df_problem));
1270 user_problem.dir = dir;
1271 user_problem.init_fun = init_fun;
1272 user_problem.con_fun_0 = con_fun_0;
1273 user_problem.con_fun_n = con_fun_n;
1274 user_problem.trans_fun = trans_fun;
1275 user_dflow.problem = &user_problem;
1276 df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1281 /*----------------------------------------------------------------------------
1282 Functions to support limited incremental change.
1283 ----------------------------------------------------------------------------*/
1286 /* Get basic block info. */
1289 df_get_bb_info (struct dataflow *dflow, unsigned int index)
1291 if (dflow->block_info == NULL)
1293 if (index >= dflow->block_info_size)
1295 return (void *)((char *)dflow->block_info
1296 + index * dflow->problem->block_info_elt_size);
1300 /* Set basic block info. */
1303 df_set_bb_info (struct dataflow *dflow, unsigned int index,
1306 gcc_assert (dflow->block_info);
1307 memcpy ((char *)dflow->block_info
1308 + index * dflow->problem->block_info_elt_size,
1309 bb_info, dflow->problem->block_info_elt_size);
1313 /* Clear basic block info. */
1316 df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1318 gcc_assert (dflow->block_info);
1319 gcc_assert (dflow->block_info_size > index);
1320 memset ((char *)dflow->block_info
1321 + index * dflow->problem->block_info_elt_size,
1322 0, dflow->problem->block_info_elt_size);
1326 /* Mark the solutions as being out of date. */
1329 df_mark_solutions_dirty (void)
1334 for (p = 1; p < df->num_problems_defined; p++)
1335 df->problems_in_order[p]->solutions_dirty = true;
1340 /* Return true if BB needs it's transfer functions recomputed. */
1343 df_get_bb_dirty (basic_block bb)
1346 return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
1352 /* Mark BB as needing it's transfer functions as being out of
1356 df_set_bb_dirty (basic_block bb)
1361 for (p = 1; p < df->num_problems_defined; p++)
1363 struct dataflow *dflow = df->problems_in_order[p];
1364 if (dflow->out_of_date_transfer_functions)
1365 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1367 df_mark_solutions_dirty ();
1372 /* Mark BB as needing it's transfer functions as being out of
1373 date, except for LR problem. Used when analyzing DEBUG_INSNs,
1374 as LR problem can trigger DCE, and DEBUG_INSNs shouldn't ever
1375 shorten or enlarge lifetime of regs. */
1378 df_set_bb_dirty_nonlr (basic_block bb)
1383 for (p = 1; p < df->num_problems_defined; p++)
1385 struct dataflow *dflow = df->problems_in_order[p];
1388 if (dflow->out_of_date_transfer_functions)
1389 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1390 dflow->solutions_dirty = true;
1395 /* Grow the bb_info array. */
1398 df_grow_bb_info (struct dataflow *dflow)
1400 unsigned int new_size = last_basic_block + 1;
1401 if (dflow->block_info_size < new_size)
1403 new_size += new_size / 4;
1405 = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1407 * dflow->problem->block_info_elt_size);
1408 memset ((char *)dflow->block_info
1409 + dflow->block_info_size
1410 * dflow->problem->block_info_elt_size,
1412 (new_size - dflow->block_info_size)
1413 * dflow->problem->block_info_elt_size);
1414 dflow->block_info_size = new_size;
1419 /* Clear the dirty bits. This is called from places that delete
1422 df_clear_bb_dirty (basic_block bb)
1425 for (p = 1; p < df->num_problems_defined; p++)
1427 struct dataflow *dflow = df->problems_in_order[p];
1428 if (dflow->out_of_date_transfer_functions)
1429 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1433 /* Called from the rtl_compact_blocks to reorganize the problems basic
1437 df_compact_blocks (void)
1441 void *problem_temps;
1444 bitmap_initialize (&tmp, &df_bitmap_obstack);
1445 for (p = 0; p < df->num_problems_defined; p++)
1447 struct dataflow *dflow = df->problems_in_order[p];
1449 /* Need to reorganize the out_of_date_transfer_functions for the
1451 if (dflow->out_of_date_transfer_functions)
1453 bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
1454 bitmap_clear (dflow->out_of_date_transfer_functions);
1455 if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1456 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1457 if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1458 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1460 i = NUM_FIXED_BLOCKS;
1463 if (bitmap_bit_p (&tmp, bb->index))
1464 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1469 /* Now shuffle the block info for the problem. */
1470 if (dflow->problem->free_bb_fun)
1472 int size = last_basic_block * dflow->problem->block_info_elt_size;
1473 problem_temps = XNEWVAR (char, size);
1474 df_grow_bb_info (dflow);
1475 memcpy (problem_temps, dflow->block_info, size);
1477 /* Copy the bb info from the problem tmps to the proper
1478 place in the block_info vector. Null out the copied
1479 item. The entry and exit blocks never move. */
1480 i = NUM_FIXED_BLOCKS;
1483 df_set_bb_info (dflow, i,
1484 (char *)problem_temps
1485 + bb->index * dflow->problem->block_info_elt_size);
1488 memset ((char *)dflow->block_info
1489 + i * dflow->problem->block_info_elt_size, 0,
1490 (last_basic_block - i)
1491 * dflow->problem->block_info_elt_size);
1492 free (problem_temps);
1496 /* Shuffle the bits in the basic_block indexed arrays. */
1498 if (df->blocks_to_analyze)
1500 if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1501 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1502 if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1503 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1504 bitmap_copy (&tmp, df->blocks_to_analyze);
1505 bitmap_clear (df->blocks_to_analyze);
1506 i = NUM_FIXED_BLOCKS;
1509 if (bitmap_bit_p (&tmp, bb->index))
1510 bitmap_set_bit (df->blocks_to_analyze, i);
1515 bitmap_clear (&tmp);
1517 i = NUM_FIXED_BLOCKS;
1520 SET_BASIC_BLOCK (i, bb);
1525 gcc_assert (i == n_basic_blocks);
1527 for (; i < last_basic_block; i++)
1528 SET_BASIC_BLOCK (i, NULL);
1531 if (!df_lr->solutions_dirty)
1532 df_set_clean_cfg ();
1537 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1538 block. There is no excuse for people to do this kind of thing. */
1541 df_bb_replace (int old_index, basic_block new_block)
1543 int new_block_index = new_block->index;
1547 fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1550 gcc_assert (BASIC_BLOCK (old_index) == NULL);
1552 for (p = 0; p < df->num_problems_defined; p++)
1554 struct dataflow *dflow = df->problems_in_order[p];
1555 if (dflow->block_info)
1557 df_grow_bb_info (dflow);
1558 df_set_bb_info (dflow, old_index,
1559 df_get_bb_info (dflow, new_block_index));
1563 df_clear_bb_dirty (new_block);
1564 SET_BASIC_BLOCK (old_index, new_block);
1565 new_block->index = old_index;
1566 df_set_bb_dirty (BASIC_BLOCK (old_index));
1567 SET_BASIC_BLOCK (new_block_index, NULL);
1571 /* Free all of the per basic block dataflow from all of the problems.
1572 This is typically called before a basic block is deleted and the
1573 problem will be reanalyzed. */
1576 df_bb_delete (int bb_index)
1578 basic_block bb = BASIC_BLOCK (bb_index);
1584 for (i = 0; i < df->num_problems_defined; i++)
1586 struct dataflow *dflow = df->problems_in_order[i];
1587 if (dflow->problem->free_bb_fun)
1589 void *bb_info = df_get_bb_info (dflow, bb_index);
1592 dflow->problem->free_bb_fun (bb, bb_info);
1593 df_clear_bb_info (dflow, bb_index);
1597 df_clear_bb_dirty (bb);
1598 df_mark_solutions_dirty ();
1602 /* Verify that there is a place for everything and everything is in
1603 its place. This is too expensive to run after every pass in the
1604 mainline. However this is an excellent debugging tool if the
1605 dataflow information is not being updated properly. You can just
1606 sprinkle calls in until you find the place that is changing an
1607 underlying structure without calling the proper updating
1614 #ifdef ENABLE_DF_CHECKING
1615 df_lr_verify_transfer_functions ();
1617 df_live_verify_transfer_functions ();
1623 /* Compute an array of ints that describes the cfg. This can be used
1624 to discover places where the cfg is modified by the appropriate
1625 calls have not been made to the keep df informed. The internals of
1626 this are unexciting, the key is that two instances of this can be
1627 compared to see if any changes have been made to the cfg. */
1630 df_compute_cfg_image (void)
1633 int size = 2 + (2 * n_basic_blocks);
1639 size += EDGE_COUNT (bb->succs);
1642 map = XNEWVEC (int, size);
1650 map[i++] = bb->index;
1651 FOR_EACH_EDGE (e, ei, bb->succs)
1652 map[i++] = e->dest->index;
1659 static int *saved_cfg = NULL;
1662 /* This function compares the saved version of the cfg with the
1663 current cfg and aborts if the two are identical. The function
1664 silently returns if the cfg has been marked as dirty or the two are
1668 df_check_cfg_clean (void)
1675 if (df_lr->solutions_dirty)
1678 if (saved_cfg == NULL)
1681 new_map = df_compute_cfg_image ();
1682 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1687 /* This function builds a cfg fingerprint and squirrels it away in
1691 df_set_clean_cfg (void)
1695 saved_cfg = df_compute_cfg_image ();
1698 #endif /* DF_DEBUG_CFG */
1699 /*----------------------------------------------------------------------------
1700 PUBLIC INTERFACES TO QUERY INFORMATION.
1701 ----------------------------------------------------------------------------*/
1704 /* Return first def of REGNO within BB. */
1707 df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1713 FOR_BB_INSNS (bb, insn)
1718 uid = INSN_UID (insn);
1719 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1721 df_ref def = *def_rec;
1722 if (DF_REF_REGNO (def) == regno)
1730 /* Return last def of REGNO within BB. */
1733 df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1739 FOR_BB_INSNS_REVERSE (bb, insn)
1744 uid = INSN_UID (insn);
1745 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1747 df_ref def = *def_rec;
1748 if (DF_REF_REGNO (def) == regno)
1756 /* Finds the reference corresponding to the definition of REG in INSN.
1757 DF is the dataflow object. */
1760 df_find_def (rtx insn, rtx reg)
1765 if (GET_CODE (reg) == SUBREG)
1766 reg = SUBREG_REG (reg);
1767 gcc_assert (REG_P (reg));
1769 uid = INSN_UID (insn);
1770 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1772 df_ref def = *def_rec;
1773 if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1781 /* Return true if REG is defined in INSN, zero otherwise. */
1784 df_reg_defined (rtx insn, rtx reg)
1786 return df_find_def (insn, reg) != NULL;
1790 /* Finds the reference corresponding to the use of REG in INSN.
1791 DF is the dataflow object. */
1794 df_find_use (rtx insn, rtx reg)
1799 if (GET_CODE (reg) == SUBREG)
1800 reg = SUBREG_REG (reg);
1801 gcc_assert (REG_P (reg));
1803 uid = INSN_UID (insn);
1804 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1806 df_ref use = *use_rec;
1807 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1810 if (df->changeable_flags & DF_EQ_NOTES)
1811 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1813 df_ref use = *use_rec;
1814 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1821 /* Return true if REG is referenced in INSN, zero otherwise. */
1824 df_reg_used (rtx insn, rtx reg)
1826 return df_find_use (insn, reg) != NULL;
1830 /*----------------------------------------------------------------------------
1831 Debugging and printing functions.
1832 ----------------------------------------------------------------------------*/
1835 /* Write information about registers and basic blocks into FILE.
1836 This is part of making a debugging dump. */
1839 df_print_regset (FILE *file, bitmap r)
1845 fputs (" (nil)", file);
1848 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1850 fprintf (file, " %d", i);
1851 if (i < FIRST_PSEUDO_REGISTER)
1852 fprintf (file, " [%s]", reg_names[i]);
1855 fprintf (file, "\n");
1859 /* Write information about registers and basic blocks into FILE. The
1860 bitmap is in the form used by df_byte_lr. This is part of making a
1864 df_print_byte_regset (FILE *file, bitmap r)
1866 unsigned int max_reg = max_reg_num ();
1870 fputs (" (nil)", file);
1874 for (i = 0; i < max_reg; i++)
1876 unsigned int first = df_byte_lr_get_regno_start (i);
1877 unsigned int len = df_byte_lr_get_regno_len (i);
1884 EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
1886 found = j < first + len;
1891 const char * sep = "";
1892 fprintf (file, " %d", i);
1893 if (i < FIRST_PSEUDO_REGISTER)
1894 fprintf (file, " [%s]", reg_names[i]);
1895 fprintf (file, "(");
1896 EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
1898 if (j > first + len - 1)
1900 fprintf (file, "%s%d", sep, j-first);
1903 fprintf (file, ")");
1908 if (bitmap_bit_p (r, first))
1910 fprintf (file, " %d", i);
1911 if (i < FIRST_PSEUDO_REGISTER)
1912 fprintf (file, " [%s]", reg_names[i]);
1918 fprintf (file, "\n");
1922 /* Dump dataflow info. */
1925 df_dump (FILE *file)
1928 df_dump_start (file);
1932 df_print_bb_index (bb, file);
1933 df_dump_top (bb, file);
1934 df_dump_bottom (bb, file);
1937 fprintf (file, "\n");
1941 /* Dump dataflow info for df->blocks_to_analyze. */
1944 df_dump_region (FILE *file)
1946 if (df->blocks_to_analyze)
1949 unsigned int bb_index;
1951 fprintf (file, "\n\nstarting region dump\n");
1952 df_dump_start (file);
1954 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1956 basic_block bb = BASIC_BLOCK (bb_index);
1958 df_print_bb_index (bb, file);
1959 df_dump_top (bb, file);
1960 df_dump_bottom (bb, file);
1962 fprintf (file, "\n");
1969 /* Dump the introductory information for each problem defined. */
1972 df_dump_start (FILE *file)
1979 fprintf (file, "\n\n%s\n", current_function_name ());
1980 fprintf (file, "\nDataflow summary:\n");
1981 if (df->blocks_to_analyze)
1982 fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
1983 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1985 for (i = 0; i < df->num_problems_defined; i++)
1987 struct dataflow *dflow = df->problems_in_order[i];
1988 if (dflow->computed)
1990 df_dump_problem_function fun = dflow->problem->dump_start_fun;
1998 /* Dump the top of the block information for BB. */
2001 df_dump_top (basic_block bb, FILE *file)
2008 for (i = 0; i < df->num_problems_defined; i++)
2010 struct dataflow *dflow = df->problems_in_order[i];
2011 if (dflow->computed)
2013 df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
2021 /* Dump the bottom of the block information for BB. */
2024 df_dump_bottom (basic_block bb, FILE *file)
2031 for (i = 0; i < df->num_problems_defined; i++)
2033 struct dataflow *dflow = df->problems_in_order[i];
2034 if (dflow->computed)
2036 df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
2045 df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
2047 fprintf (file, "{ ");
2050 df_ref ref = *ref_rec;
2051 fprintf (file, "%c%d(%d)",
2052 DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2054 DF_REF_REGNO (ref));
2056 df_chain_dump (DF_REF_CHAIN (ref), file);
2059 fprintf (file, "}");
2063 /* Dump either a ref-def or reg-use chain. */
2066 df_regs_chain_dump (df_ref ref, FILE *file)
2068 fprintf (file, "{ ");
2071 fprintf (file, "%c%d(%d) ",
2072 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2074 DF_REF_REGNO (ref));
2075 ref = DF_REF_NEXT_REG (ref);
2077 fprintf (file, "}");
2082 df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
2086 fprintf (file, "mw %c r[%d..%d]\n",
2087 (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
2088 (*mws)->start_regno, (*mws)->end_regno);
2095 df_insn_uid_debug (unsigned int uid,
2096 bool follow_chain, FILE *file)
2098 fprintf (file, "insn %d luid %d",
2099 uid, DF_INSN_UID_LUID (uid));
2101 if (DF_INSN_UID_DEFS (uid))
2103 fprintf (file, " defs ");
2104 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2107 if (DF_INSN_UID_USES (uid))
2109 fprintf (file, " uses ");
2110 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2113 if (DF_INSN_UID_EQ_USES (uid))
2115 fprintf (file, " eq uses ");
2116 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2119 if (DF_INSN_UID_MWS (uid))
2121 fprintf (file, " mws ");
2122 df_mws_dump (DF_INSN_UID_MWS (uid), file);
2124 fprintf (file, "\n");
2129 df_insn_debug (rtx insn, bool follow_chain, FILE *file)
2131 df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2135 df_insn_debug_regno (rtx insn, FILE *file)
2137 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2139 fprintf (file, "insn %d bb %d luid %d defs ",
2140 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2141 DF_INSN_INFO_LUID (insn_info));
2142 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2144 fprintf (file, " uses ");
2145 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2147 fprintf (file, " eq_uses ");
2148 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2149 fprintf (file, "\n");
2153 df_regno_debug (unsigned int regno, FILE *file)
2155 fprintf (file, "reg %d defs ", regno);
2156 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2157 fprintf (file, " uses ");
2158 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2159 fprintf (file, " eq_uses ");
2160 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2161 fprintf (file, "\n");
2166 df_ref_debug (df_ref ref, FILE *file)
2168 fprintf (file, "%c%d ",
2169 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2171 fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ",
2174 DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2177 if (DF_REF_LOC (ref))
2179 if (flag_dump_noaddr)
2180 fprintf (file, "loc #(#) chain ");
2182 fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2183 (void *)*DF_REF_LOC (ref));
2186 fprintf (file, "chain ");
2187 df_chain_dump (DF_REF_CHAIN (ref), file);
2188 fprintf (file, "\n");
2191 /* Functions for debugging from GDB. */
2194 debug_df_insn (rtx insn)
2196 df_insn_debug (insn, true, stderr);
2202 debug_df_reg (rtx reg)
2204 df_regno_debug (REGNO (reg), stderr);
2209 debug_df_regno (unsigned int regno)
2211 df_regno_debug (regno, stderr);
2216 debug_df_ref (df_ref ref)
2218 df_ref_debug (ref, stderr);
2223 debug_df_defno (unsigned int defno)
2225 df_ref_debug (DF_DEFS_GET (defno), stderr);
2230 debug_df_useno (unsigned int defno)
2232 df_ref_debug (DF_USES_GET (defno), stderr);
2237 debug_df_chain (struct df_link *link)
2239 df_chain_dump (link, stderr);
2240 fputc ('\n', stderr);