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 *);
403 static void df_set_clean_cfg (void);
406 /* An obstack for bitmap not related to specific dataflow problems.
407 This obstack should e.g. be used for bitmaps with a short life time
408 such as temporary bitmaps. */
410 bitmap_obstack df_bitmap_obstack
;
413 /*----------------------------------------------------------------------------
414 Functions to create, destroy and manipulate an instance of df.
415 ----------------------------------------------------------------------------*/
419 /* Add PROBLEM (and any dependent problems) to the DF instance. */
422 df_add_problem (struct df_problem
*problem
)
424 struct dataflow
*dflow
;
427 /* First try to add the dependent problem. */
428 if (problem
->dependent_problem
)
429 df_add_problem (problem
->dependent_problem
);
431 /* Check to see if this problem has already been defined. If it
432 has, just return that instance, if not, add it to the end of the
434 dflow
= df
->problems_by_index
[problem
->id
];
438 /* Make a new one and add it to the end. */
439 dflow
= XCNEW (struct dataflow
);
440 dflow
->problem
= problem
;
441 dflow
->computed
= false;
442 dflow
->solutions_dirty
= true;
443 df
->problems_by_index
[dflow
->problem
->id
] = dflow
;
445 /* Keep the defined problems ordered by index. This solves the
446 problem that RI will use the information from UREC if UREC has
447 been defined, or from LIVE if LIVE is defined and otherwise LR.
448 However for this to work, the computation of RI must be pushed
449 after which ever of those problems is defined, but we do not
450 require any of those except for LR to have actually been
452 df
->num_problems_defined
++;
453 for (i
= df
->num_problems_defined
- 2; i
>= 0; i
--)
455 if (problem
->id
< df
->problems_in_order
[i
]->problem
->id
)
456 df
->problems_in_order
[i
+1] = df
->problems_in_order
[i
];
459 df
->problems_in_order
[i
+1] = dflow
;
463 df
->problems_in_order
[0] = dflow
;
467 /* Set the MASK flags in the DFLOW problem. The old flags are
468 returned. If a flag is not allowed to be changed this will fail if
469 checking is enabled. */
471 df_set_flags (int changeable_flags
)
473 int old_flags
= df
->changeable_flags
;
474 df
->changeable_flags
|= changeable_flags
;
479 /* Clear the MASK flags in the DFLOW problem. The old flags are
480 returned. If a flag is not allowed to be changed this will fail if
481 checking is enabled. */
483 df_clear_flags (int changeable_flags
)
485 int old_flags
= df
->changeable_flags
;
486 df
->changeable_flags
&= ~changeable_flags
;
491 /* Set the blocks that are to be considered for analysis. If this is
492 not called or is called with null, the entire function in
496 df_set_blocks (bitmap blocks
)
501 bitmap_print (dump_file
, blocks
, "setting blocks to analyze ", "\n");
502 if (df
->blocks_to_analyze
)
504 /* This block is called to change the focus from one subset
508 bitmap_initialize (&diff
, &df_bitmap_obstack
);
509 bitmap_and_compl (&diff
, df
->blocks_to_analyze
, blocks
);
510 for (p
= 0; p
< df
->num_problems_defined
; p
++)
512 struct dataflow
*dflow
= df
->problems_in_order
[p
];
513 if (dflow
->optional_p
&& dflow
->problem
->reset_fun
)
514 dflow
->problem
->reset_fun (df
->blocks_to_analyze
);
515 else if (dflow
->problem
->free_blocks_on_set_blocks
)
518 unsigned int bb_index
;
520 EXECUTE_IF_SET_IN_BITMAP (&diff
, 0, bb_index
, bi
)
522 basic_block bb
= BASIC_BLOCK (bb_index
);
525 void *bb_info
= df_get_bb_info (dflow
, bb_index
);
528 dflow
->problem
->free_bb_fun (bb
, bb_info
);
529 df_set_bb_info (dflow
, bb_index
, NULL
);
536 bitmap_clear (&diff
);
540 /* This block of code is executed to change the focus from
541 the entire function to a subset. */
542 bitmap_head blocks_to_reset
;
543 bool initialized
= false;
545 for (p
= 0; p
< df
->num_problems_defined
; p
++)
547 struct dataflow
*dflow
= df
->problems_in_order
[p
];
548 if (dflow
->optional_p
&& dflow
->problem
->reset_fun
)
553 bitmap_initialize (&blocks_to_reset
, &df_bitmap_obstack
);
556 bitmap_set_bit (&blocks_to_reset
, bb
->index
);
559 dflow
->problem
->reset_fun (&blocks_to_reset
);
563 bitmap_clear (&blocks_to_reset
);
565 df
->blocks_to_analyze
= BITMAP_ALLOC (&df_bitmap_obstack
);
567 bitmap_copy (df
->blocks_to_analyze
, blocks
);
568 df
->analyze_subset
= true;
572 /* This block is executed to reset the focus to the entire
575 fprintf (dump_file
, "clearing blocks_to_analyze\n");
576 if (df
->blocks_to_analyze
)
578 BITMAP_FREE (df
->blocks_to_analyze
);
579 df
->blocks_to_analyze
= NULL
;
581 df
->analyze_subset
= false;
584 /* Setting the blocks causes the refs to be unorganized since only
585 the refs in the blocks are seen. */
586 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE
);
587 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE
);
588 df_mark_solutions_dirty ();
592 /* Delete a DFLOW problem (and any problems that depend on this
596 df_remove_problem (struct dataflow
*dflow
)
598 struct df_problem
*problem
;
604 problem
= dflow
->problem
;
605 gcc_assert (problem
->remove_problem_fun
);
607 /* Delete any problems that depended on this problem first. */
608 for (i
= 0; i
< df
->num_problems_defined
; i
++)
609 if (df
->problems_in_order
[i
]->problem
->dependent_problem
== problem
)
610 df_remove_problem (df
->problems_in_order
[i
]);
612 /* Now remove this problem. */
613 for (i
= 0; i
< df
->num_problems_defined
; i
++)
614 if (df
->problems_in_order
[i
] == dflow
)
617 for (j
= i
+ 1; j
< df
->num_problems_defined
; j
++)
618 df
->problems_in_order
[j
-1] = df
->problems_in_order
[j
];
619 df
->problems_in_order
[j
-1] = NULL
;
620 df
->num_problems_defined
--;
624 (problem
->remove_problem_fun
) ();
625 df
->problems_by_index
[problem
->id
] = NULL
;
629 /* Remove all of the problems that are not permanent. Scanning, LR
630 and (at -O2 or higher) LIVE are permanent, the rest are removable.
631 Also clear all of the changeable_flags. */
634 df_finish_pass (bool verify ATTRIBUTE_UNUSED
)
639 #ifdef ENABLE_DF_CHECKING
646 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE
);
647 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE
);
649 #ifdef ENABLE_DF_CHECKING
650 saved_flags
= df
->changeable_flags
;
653 for (i
= 0; i
< df
->num_problems_defined
; i
++)
655 struct dataflow
*dflow
= df
->problems_in_order
[i
];
656 struct df_problem
*problem
= dflow
->problem
;
658 if (dflow
->optional_p
)
660 gcc_assert (problem
->remove_problem_fun
);
661 (problem
->remove_problem_fun
) ();
662 df
->problems_in_order
[i
] = NULL
;
663 df
->problems_by_index
[problem
->id
] = NULL
;
667 df
->num_problems_defined
-= removed
;
669 /* Clear all of the flags. */
670 df
->changeable_flags
= 0;
671 df_process_deferred_rescans ();
673 /* Set the focus back to the whole function. */
674 if (df
->blocks_to_analyze
)
676 BITMAP_FREE (df
->blocks_to_analyze
);
677 df
->blocks_to_analyze
= NULL
;
678 df_mark_solutions_dirty ();
679 df
->analyze_subset
= false;
682 #ifdef ENABLE_DF_CHECKING
683 /* Verification will fail in DF_NO_INSN_RESCAN. */
684 if (!(saved_flags
& DF_NO_INSN_RESCAN
))
686 df_lr_verify_transfer_functions ();
688 df_live_verify_transfer_functions ();
696 #ifdef ENABLE_CHECKING
698 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
703 /* Set up the dataflow instance for the entire back end. */
706 rest_of_handle_df_initialize (void)
709 df
= XCNEW (struct df
);
710 df
->changeable_flags
= 0;
712 bitmap_obstack_initialize (&df_bitmap_obstack
);
714 /* Set this to a conservative value. Stack_ptr_mod will compute it
716 current_function_sp_is_unchanging
= 0;
718 df_scan_add_problem ();
719 df_scan_alloc (NULL
);
721 /* These three problems are permanent. */
722 df_lr_add_problem ();
724 df_live_add_problem ();
726 df
->postorder
= XNEWVEC (int, last_basic_block
);
727 df
->postorder_inverted
= XNEWVEC (int, last_basic_block
);
728 df
->n_blocks
= post_order_compute (df
->postorder
, true, true);
729 df
->n_blocks_inverted
= inverted_post_order_compute (df
->postorder_inverted
);
730 gcc_assert (df
->n_blocks
== df
->n_blocks_inverted
);
732 df
->hard_regs_live_count
= XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER
);
733 memset (df
->hard_regs_live_count
, 0,
734 sizeof (unsigned int) * FIRST_PSEUDO_REGISTER
);
737 /* After reload, some ports add certain bits to regs_ever_live so
738 this cannot be reset. */
739 df_compute_regs_ever_live (true);
741 df_compute_regs_ever_live (false);
753 struct rtl_opt_pass pass_df_initialize_opt
=
759 rest_of_handle_df_initialize
, /* execute */
762 0, /* static_pass_number */
764 0, /* properties_required */
765 0, /* properties_provided */
766 0, /* properties_destroyed */
767 0, /* todo_flags_start */
768 0 /* todo_flags_finish */
776 return optimize
== 0;
780 struct rtl_opt_pass pass_df_initialize_no_opt
=
784 "no-opt dfinit", /* name */
785 gate_no_opt
, /* gate */
786 rest_of_handle_df_initialize
, /* execute */
789 0, /* static_pass_number */
791 0, /* properties_required */
792 0, /* properties_provided */
793 0, /* properties_destroyed */
794 0, /* todo_flags_start */
795 0 /* todo_flags_finish */
800 /* Free all the dataflow info and the DF structure. This should be
801 called from the df_finish macro which also NULLs the parm. */
804 rest_of_handle_df_finish (void)
810 for (i
= 0; i
< df
->num_problems_defined
; i
++)
812 struct dataflow
*dflow
= df
->problems_in_order
[i
];
813 dflow
->problem
->free_fun ();
817 free (df
->postorder
);
818 if (df
->postorder_inverted
)
819 free (df
->postorder_inverted
);
820 free (df
->hard_regs_live_count
);
824 bitmap_obstack_release (&df_bitmap_obstack
);
829 struct rtl_opt_pass pass_df_finish
=
833 "dfinish", /* name */
835 rest_of_handle_df_finish
, /* execute */
838 0, /* static_pass_number */
840 0, /* properties_required */
841 0, /* properties_provided */
842 0, /* properties_destroyed */
843 0, /* todo_flags_start */
844 0 /* todo_flags_finish */
852 /*----------------------------------------------------------------------------
853 The general data flow analysis engine.
854 ----------------------------------------------------------------------------*/
857 /* Helper function for df_worklist_dataflow.
858 Propagate the dataflow forward.
859 Given a BB_INDEX, do the dataflow propagation
860 and set bits on for successors in PENDING
861 if the out set of the dataflow has changed. */
864 df_worklist_propagate_forward (struct dataflow
*dataflow
,
866 unsigned *bbindex_to_postorder
,
872 basic_block bb
= BASIC_BLOCK (bb_index
);
874 /* Calculate <conf_op> of incoming edges. */
875 if (EDGE_COUNT (bb
->preds
) > 0)
876 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
878 if (TEST_BIT (considered
, e
->src
->index
))
879 dataflow
->problem
->con_fun_n (e
);
881 else if (dataflow
->problem
->con_fun_0
)
882 dataflow
->problem
->con_fun_0 (bb
);
884 if (dataflow
->problem
->trans_fun (bb_index
))
886 /* The out set of this block has changed.
887 Propagate to the outgoing blocks. */
888 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
890 unsigned ob_index
= e
->dest
->index
;
892 if (TEST_BIT (considered
, ob_index
))
893 bitmap_set_bit (pending
, bbindex_to_postorder
[ob_index
]);
899 /* Helper function for df_worklist_dataflow.
900 Propagate the dataflow backward. */
903 df_worklist_propagate_backward (struct dataflow
*dataflow
,
905 unsigned *bbindex_to_postorder
,
911 basic_block bb
= BASIC_BLOCK (bb_index
);
913 /* Calculate <conf_op> of incoming edges. */
914 if (EDGE_COUNT (bb
->succs
) > 0)
915 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
917 if (TEST_BIT (considered
, e
->dest
->index
))
918 dataflow
->problem
->con_fun_n (e
);
920 else if (dataflow
->problem
->con_fun_0
)
921 dataflow
->problem
->con_fun_0 (bb
);
923 if (dataflow
->problem
->trans_fun (bb_index
))
925 /* The out set of this block has changed.
926 Propagate to the outgoing blocks. */
927 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
929 unsigned ob_index
= e
->src
->index
;
931 if (TEST_BIT (considered
, ob_index
))
932 bitmap_set_bit (pending
, bbindex_to_postorder
[ob_index
]);
939 /* This will free "pending". */
942 df_worklist_dataflow_doublequeue (struct dataflow
*dataflow
,
945 int *blocks_in_postorder
,
946 unsigned *bbindex_to_postorder
)
948 enum df_flow_dir dir
= dataflow
->problem
->dir
;
950 bitmap worklist
= BITMAP_ALLOC (&df_bitmap_obstack
);
952 /* Double-queueing. Worklist is for the current iteration,
953 and pending is for the next. */
954 while (!bitmap_empty_p (pending
))
956 /* Swap pending and worklist. */
957 bitmap temp
= worklist
;
967 index
= bitmap_first_set_bit (worklist
);
968 bitmap_clear_bit (worklist
, index
);
970 bb_index
= blocks_in_postorder
[index
];
972 if (dir
== DF_FORWARD
)
973 df_worklist_propagate_forward (dataflow
, bb_index
,
974 bbindex_to_postorder
,
975 pending
, considered
);
977 df_worklist_propagate_backward (dataflow
, bb_index
,
978 bbindex_to_postorder
,
979 pending
, considered
);
981 while (!bitmap_empty_p (worklist
));
984 BITMAP_FREE (worklist
);
985 BITMAP_FREE (pending
);
987 /* Dump statistics. */
989 fprintf (dump_file
, "df_worklist_dataflow_doublequeue:"
990 "n_basic_blocks %d n_edges %d"
991 " count %d (%5.2g)\n",
992 n_basic_blocks
, n_edges
,
993 dcount
, dcount
/ (float)n_basic_blocks
);
996 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
997 with "n"-th bit representing the n-th block in the reverse-postorder order.
998 The solver is a double-queue algorithm similar to the "double stack" solver
999 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1000 The only significant difference is that the worklist in this implementation
1001 is always sorted in RPO of the CFG visiting direction. */
1004 df_worklist_dataflow (struct dataflow
*dataflow
,
1005 bitmap blocks_to_consider
,
1006 int *blocks_in_postorder
,
1009 bitmap pending
= BITMAP_ALLOC (&df_bitmap_obstack
);
1010 sbitmap considered
= sbitmap_alloc (last_basic_block
);
1012 unsigned int *bbindex_to_postorder
;
1015 enum df_flow_dir dir
= dataflow
->problem
->dir
;
1017 gcc_assert (dir
!= DF_NONE
);
1019 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
1020 bbindex_to_postorder
=
1021 (unsigned int *)xmalloc (last_basic_block
* sizeof (unsigned int));
1023 /* Initialize the array to an out-of-bound value. */
1024 for (i
= 0; i
< last_basic_block
; i
++)
1025 bbindex_to_postorder
[i
] = last_basic_block
;
1027 /* Initialize the considered map. */
1028 sbitmap_zero (considered
);
1029 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider
, 0, index
, bi
)
1031 SET_BIT (considered
, index
);
1034 /* Initialize the mapping of block index to postorder. */
1035 for (i
= 0; i
< n_blocks
; i
++)
1037 bbindex_to_postorder
[blocks_in_postorder
[i
]] = i
;
1038 /* Add all blocks to the worklist. */
1039 bitmap_set_bit (pending
, i
);
1042 /* Initialize the problem. */
1043 if (dataflow
->problem
->init_fun
)
1044 dataflow
->problem
->init_fun (blocks_to_consider
);
1047 df_worklist_dataflow_doublequeue (dataflow
, pending
, considered
,
1048 blocks_in_postorder
,
1049 bbindex_to_postorder
);
1051 sbitmap_free (considered
);
1052 free (bbindex_to_postorder
);
1056 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1057 the order of the remaining entries. Returns the length of the resulting
1061 df_prune_to_subcfg (int list
[], unsigned len
, bitmap blocks
)
1065 for (act
= 0, last
= 0; act
< len
; act
++)
1066 if (bitmap_bit_p (blocks
, list
[act
]))
1067 list
[last
++] = list
[act
];
1073 /* Execute dataflow analysis on a single dataflow problem.
1075 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1076 examined or will be computed. For calls from DF_ANALYZE, this is
1077 the set of blocks that has been passed to DF_SET_BLOCKS.
1081 df_analyze_problem (struct dataflow
*dflow
,
1082 bitmap blocks_to_consider
,
1083 int *postorder
, int n_blocks
)
1085 timevar_push (dflow
->problem
->tv_id
);
1087 /* (Re)Allocate the datastructures necessary to solve the problem. */
1088 if (dflow
->problem
->alloc_fun
)
1089 dflow
->problem
->alloc_fun (blocks_to_consider
);
1091 #ifdef ENABLE_DF_CHECKING
1092 if (dflow
->problem
->verify_start_fun
)
1093 dflow
->problem
->verify_start_fun ();
1096 /* Set up the problem and compute the local information. */
1097 if (dflow
->problem
->local_compute_fun
)
1098 dflow
->problem
->local_compute_fun (blocks_to_consider
);
1100 /* Solve the equations. */
1101 if (dflow
->problem
->dataflow_fun
)
1102 dflow
->problem
->dataflow_fun (dflow
, blocks_to_consider
,
1103 postorder
, n_blocks
);
1105 /* Massage the solution. */
1106 if (dflow
->problem
->finalize_fun
)
1107 dflow
->problem
->finalize_fun (blocks_to_consider
);
1109 #ifdef ENABLE_DF_CHECKING
1110 if (dflow
->problem
->verify_end_fun
)
1111 dflow
->problem
->verify_end_fun ();
1114 timevar_pop (dflow
->problem
->tv_id
);
1116 dflow
->computed
= true;
1120 /* Analyze dataflow info for the basic blocks specified by the bitmap
1121 BLOCKS, or for the whole CFG if BLOCKS is zero. */
1126 bitmap current_all_blocks
= BITMAP_ALLOC (&df_bitmap_obstack
);
1131 free (df
->postorder
);
1132 if (df
->postorder_inverted
)
1133 free (df
->postorder_inverted
);
1134 df
->postorder
= XNEWVEC (int, last_basic_block
);
1135 df
->postorder_inverted
= XNEWVEC (int, last_basic_block
);
1136 df
->n_blocks
= post_order_compute (df
->postorder
, true, true);
1137 df
->n_blocks_inverted
= inverted_post_order_compute (df
->postorder_inverted
);
1139 /* These should be the same. */
1140 gcc_assert (df
->n_blocks
== df
->n_blocks_inverted
);
1142 /* We need to do this before the df_verify_all because this is
1143 not kept incrementally up to date. */
1144 df_compute_regs_ever_live (false);
1145 df_process_deferred_rescans ();
1148 fprintf (dump_file
, "df_analyze called\n");
1150 #ifndef ENABLE_DF_CHECKING
1151 if (df
->changeable_flags
& DF_VERIFY_SCHEDULED
)
1155 for (i
= 0; i
< df
->n_blocks
; i
++)
1156 bitmap_set_bit (current_all_blocks
, df
->postorder
[i
]);
1158 #ifdef ENABLE_CHECKING
1159 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1161 for (i
= 0; i
< df
->n_blocks_inverted
; i
++)
1162 gcc_assert (bitmap_bit_p (current_all_blocks
, df
->postorder_inverted
[i
]));
1165 /* Make sure that we have pruned any unreachable blocks from these
1167 if (df
->analyze_subset
)
1170 bitmap_and_into (df
->blocks_to_analyze
, current_all_blocks
);
1171 df
->n_blocks
= df_prune_to_subcfg (df
->postorder
,
1172 df
->n_blocks
, df
->blocks_to_analyze
);
1173 df
->n_blocks_inverted
= df_prune_to_subcfg (df
->postorder_inverted
,
1174 df
->n_blocks_inverted
,
1175 df
->blocks_to_analyze
);
1176 BITMAP_FREE (current_all_blocks
);
1181 df
->blocks_to_analyze
= current_all_blocks
;
1182 current_all_blocks
= NULL
;
1185 /* Skip over the DF_SCAN problem. */
1186 for (i
= 1; i
< df
->num_problems_defined
; i
++)
1188 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1189 if (dflow
->solutions_dirty
)
1191 if (dflow
->problem
->dir
== DF_FORWARD
)
1192 df_analyze_problem (dflow
,
1193 df
->blocks_to_analyze
,
1194 df
->postorder_inverted
,
1195 df
->n_blocks_inverted
);
1197 df_analyze_problem (dflow
,
1198 df
->blocks_to_analyze
,
1206 BITMAP_FREE (df
->blocks_to_analyze
);
1207 df
->blocks_to_analyze
= NULL
;
1211 df_set_clean_cfg ();
1216 /* Return the number of basic blocks from the last call to df_analyze. */
1219 df_get_n_blocks (enum df_flow_dir dir
)
1221 gcc_assert (dir
!= DF_NONE
);
1223 if (dir
== DF_FORWARD
)
1225 gcc_assert (df
->postorder_inverted
);
1226 return df
->n_blocks_inverted
;
1229 gcc_assert (df
->postorder
);
1230 return df
->n_blocks
;
1234 /* Return a pointer to the array of basic blocks in the reverse postorder.
1235 Depending on the direction of the dataflow problem,
1236 it returns either the usual reverse postorder array
1237 or the reverse postorder of inverted traversal. */
1239 df_get_postorder (enum df_flow_dir dir
)
1241 gcc_assert (dir
!= DF_NONE
);
1243 if (dir
== DF_FORWARD
)
1245 gcc_assert (df
->postorder_inverted
);
1246 return df
->postorder_inverted
;
1248 gcc_assert (df
->postorder
);
1249 return df
->postorder
;
1252 static struct df_problem user_problem
;
1253 static struct dataflow user_dflow
;
1255 /* Interface for calling iterative dataflow with user defined
1256 confluence and transfer functions. All that is necessary is to
1257 supply DIR, a direction, CONF_FUN_0, a confluence function for
1258 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1259 confluence function, TRANS_FUN, the basic block transfer function,
1260 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1261 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1264 df_simple_dataflow (enum df_flow_dir dir
,
1265 df_init_function init_fun
,
1266 df_confluence_function_0 con_fun_0
,
1267 df_confluence_function_n con_fun_n
,
1268 df_transfer_function trans_fun
,
1269 bitmap blocks
, int * postorder
, int n_blocks
)
1271 memset (&user_problem
, 0, sizeof (struct df_problem
));
1272 user_problem
.dir
= dir
;
1273 user_problem
.init_fun
= init_fun
;
1274 user_problem
.con_fun_0
= con_fun_0
;
1275 user_problem
.con_fun_n
= con_fun_n
;
1276 user_problem
.trans_fun
= trans_fun
;
1277 user_dflow
.problem
= &user_problem
;
1278 df_worklist_dataflow (&user_dflow
, blocks
, postorder
, n_blocks
);
1283 /*----------------------------------------------------------------------------
1284 Functions to support limited incremental change.
1285 ----------------------------------------------------------------------------*/
1288 /* Get basic block info. */
1291 df_get_bb_info (struct dataflow
*dflow
, unsigned int index
)
1293 if (dflow
->block_info
== NULL
)
1295 if (index
>= dflow
->block_info_size
)
1297 return (struct df_scan_bb_info
*) dflow
->block_info
[index
];
1301 /* Set basic block info. */
1304 df_set_bb_info (struct dataflow
*dflow
, unsigned int index
,
1307 gcc_assert (dflow
->block_info
);
1308 dflow
->block_info
[index
] = bb_info
;
1312 /* Mark the solutions as being out of date. */
1315 df_mark_solutions_dirty (void)
1320 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1321 df
->problems_in_order
[p
]->solutions_dirty
= true;
1326 /* Return true if BB needs it's transfer functions recomputed. */
1329 df_get_bb_dirty (basic_block bb
)
1332 return bitmap_bit_p (df_live
->out_of_date_transfer_functions
, bb
->index
);
1338 /* Mark BB as needing it's transfer functions as being out of
1342 df_set_bb_dirty (basic_block bb
)
1347 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1349 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1350 if (dflow
->out_of_date_transfer_functions
)
1351 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, bb
->index
);
1353 df_mark_solutions_dirty ();
1358 /* Mark BB as needing it's transfer functions as being out of
1359 date, except for LR problem. Used when analyzing DEBUG_INSNs,
1360 as LR problem can trigger DCE, and DEBUG_INSNs shouldn't ever
1361 shorten or enlarge lifetime of regs. */
1364 df_set_bb_dirty_nonlr (basic_block bb
)
1369 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1371 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1374 if (dflow
->out_of_date_transfer_functions
)
1375 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, bb
->index
);
1376 dflow
->solutions_dirty
= true;
1382 /* Clear the dirty bits. This is called from places that delete
1385 df_clear_bb_dirty (basic_block bb
)
1388 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1390 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1391 if (dflow
->out_of_date_transfer_functions
)
1392 bitmap_clear_bit (dflow
->out_of_date_transfer_functions
, bb
->index
);
1395 /* Called from the rtl_compact_blocks to reorganize the problems basic
1399 df_compact_blocks (void)
1403 void **problem_temps
;
1404 int size
= last_basic_block
* sizeof (void *);
1406 problem_temps
= XNEWVAR (void *, size
);
1408 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
1409 for (p
= 0; p
< df
->num_problems_defined
; p
++)
1411 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1413 /* Need to reorganize the out_of_date_transfer_functions for the
1415 if (dflow
->out_of_date_transfer_functions
)
1417 bitmap_copy (&tmp
, dflow
->out_of_date_transfer_functions
);
1418 bitmap_clear (dflow
->out_of_date_transfer_functions
);
1419 if (bitmap_bit_p (&tmp
, ENTRY_BLOCK
))
1420 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
1421 if (bitmap_bit_p (&tmp
, EXIT_BLOCK
))
1422 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, EXIT_BLOCK
);
1424 i
= NUM_FIXED_BLOCKS
;
1427 if (bitmap_bit_p (&tmp
, bb
->index
))
1428 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, i
);
1433 /* Now shuffle the block info for the problem. */
1434 if (dflow
->problem
->free_bb_fun
)
1436 df_grow_bb_info (dflow
);
1437 memcpy (problem_temps
, dflow
->block_info
, size
);
1439 /* Copy the bb info from the problem tmps to the proper
1440 place in the block_info vector. Null out the copied
1441 item. The entry and exit blocks never move. */
1442 i
= NUM_FIXED_BLOCKS
;
1445 df_set_bb_info (dflow
, i
, problem_temps
[bb
->index
]);
1446 problem_temps
[bb
->index
] = NULL
;
1449 memset (dflow
->block_info
+ i
, 0,
1450 (last_basic_block
- i
) *sizeof (void *));
1452 /* Free any block infos that were not copied (and NULLed).
1453 These are from orphaned blocks. */
1454 for (i
= NUM_FIXED_BLOCKS
; i
< last_basic_block
; i
++)
1456 basic_block bb
= BASIC_BLOCK (i
);
1457 if (problem_temps
[i
] && bb
)
1458 dflow
->problem
->free_bb_fun
1459 (bb
, problem_temps
[i
]);
1464 /* Shuffle the bits in the basic_block indexed arrays. */
1466 if (df
->blocks_to_analyze
)
1468 if (bitmap_bit_p (&tmp
, ENTRY_BLOCK
))
1469 bitmap_set_bit (df
->blocks_to_analyze
, ENTRY_BLOCK
);
1470 if (bitmap_bit_p (&tmp
, EXIT_BLOCK
))
1471 bitmap_set_bit (df
->blocks_to_analyze
, EXIT_BLOCK
);
1472 bitmap_copy (&tmp
, df
->blocks_to_analyze
);
1473 bitmap_clear (df
->blocks_to_analyze
);
1474 i
= NUM_FIXED_BLOCKS
;
1477 if (bitmap_bit_p (&tmp
, bb
->index
))
1478 bitmap_set_bit (df
->blocks_to_analyze
, i
);
1483 bitmap_clear (&tmp
);
1485 free (problem_temps
);
1487 i
= NUM_FIXED_BLOCKS
;
1490 SET_BASIC_BLOCK (i
, bb
);
1495 gcc_assert (i
== n_basic_blocks
);
1497 for (; i
< last_basic_block
; i
++)
1498 SET_BASIC_BLOCK (i
, NULL
);
1501 if (!df_lr
->solutions_dirty
)
1502 df_set_clean_cfg ();
1507 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1508 block. There is no excuse for people to do this kind of thing. */
1511 df_bb_replace (int old_index
, basic_block new_block
)
1513 int new_block_index
= new_block
->index
;
1517 fprintf (dump_file
, "shoving block %d into %d\n", new_block_index
, old_index
);
1520 gcc_assert (BASIC_BLOCK (old_index
) == NULL
);
1522 for (p
= 0; p
< df
->num_problems_defined
; p
++)
1524 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1525 if (dflow
->block_info
)
1527 df_grow_bb_info (dflow
);
1528 gcc_assert (df_get_bb_info (dflow
, old_index
) == NULL
);
1529 df_set_bb_info (dflow
, old_index
,
1530 df_get_bb_info (dflow
, new_block_index
));
1534 df_clear_bb_dirty (new_block
);
1535 SET_BASIC_BLOCK (old_index
, new_block
);
1536 new_block
->index
= old_index
;
1537 df_set_bb_dirty (BASIC_BLOCK (old_index
));
1538 SET_BASIC_BLOCK (new_block_index
, NULL
);
1542 /* Free all of the per basic block dataflow from all of the problems.
1543 This is typically called before a basic block is deleted and the
1544 problem will be reanalyzed. */
1547 df_bb_delete (int bb_index
)
1549 basic_block bb
= BASIC_BLOCK (bb_index
);
1555 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1557 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1558 if (dflow
->problem
->free_bb_fun
)
1560 void *bb_info
= df_get_bb_info (dflow
, bb_index
);
1563 dflow
->problem
->free_bb_fun (bb
, bb_info
);
1564 df_set_bb_info (dflow
, bb_index
, NULL
);
1568 df_clear_bb_dirty (bb
);
1569 df_mark_solutions_dirty ();
1573 /* Verify that there is a place for everything and everything is in
1574 its place. This is too expensive to run after every pass in the
1575 mainline. However this is an excellent debugging tool if the
1576 dataflow information is not being updated properly. You can just
1577 sprinkle calls in until you find the place that is changing an
1578 underlying structure without calling the proper updating
1585 #ifdef ENABLE_DF_CHECKING
1586 df_lr_verify_transfer_functions ();
1588 df_live_verify_transfer_functions ();
1594 /* Compute an array of ints that describes the cfg. This can be used
1595 to discover places where the cfg is modified by the appropriate
1596 calls have not been made to the keep df informed. The internals of
1597 this are unexciting, the key is that two instances of this can be
1598 compared to see if any changes have been made to the cfg. */
1601 df_compute_cfg_image (void)
1604 int size
= 2 + (2 * n_basic_blocks
);
1610 size
+= EDGE_COUNT (bb
->succs
);
1613 map
= XNEWVEC (int, size
);
1621 map
[i
++] = bb
->index
;
1622 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1623 map
[i
++] = e
->dest
->index
;
1630 static int *saved_cfg
= NULL
;
1633 /* This function compares the saved version of the cfg with the
1634 current cfg and aborts if the two are identical. The function
1635 silently returns if the cfg has been marked as dirty or the two are
1639 df_check_cfg_clean (void)
1646 if (df_lr
->solutions_dirty
)
1649 if (saved_cfg
== NULL
)
1652 new_map
= df_compute_cfg_image ();
1653 gcc_assert (memcmp (saved_cfg
, new_map
, saved_cfg
[0] * sizeof (int)) == 0);
1658 /* This function builds a cfg fingerprint and squirrels it away in
1662 df_set_clean_cfg (void)
1666 saved_cfg
= df_compute_cfg_image ();
1669 #endif /* DF_DEBUG_CFG */
1670 /*----------------------------------------------------------------------------
1671 PUBLIC INTERFACES TO QUERY INFORMATION.
1672 ----------------------------------------------------------------------------*/
1675 /* Return first def of REGNO within BB. */
1678 df_bb_regno_first_def_find (basic_block bb
, unsigned int regno
)
1684 FOR_BB_INSNS (bb
, insn
)
1689 uid
= INSN_UID (insn
);
1690 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1692 df_ref def
= *def_rec
;
1693 if (DF_REF_REGNO (def
) == regno
)
1701 /* Return last def of REGNO within BB. */
1704 df_bb_regno_last_def_find (basic_block bb
, unsigned int regno
)
1710 FOR_BB_INSNS_REVERSE (bb
, insn
)
1715 uid
= INSN_UID (insn
);
1716 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1718 df_ref def
= *def_rec
;
1719 if (DF_REF_REGNO (def
) == regno
)
1727 /* Finds the reference corresponding to the definition of REG in INSN.
1728 DF is the dataflow object. */
1731 df_find_def (rtx insn
, rtx reg
)
1736 if (GET_CODE (reg
) == SUBREG
)
1737 reg
= SUBREG_REG (reg
);
1738 gcc_assert (REG_P (reg
));
1740 uid
= INSN_UID (insn
);
1741 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1743 df_ref def
= *def_rec
;
1744 if (rtx_equal_p (DF_REF_REAL_REG (def
), reg
))
1752 /* Return true if REG is defined in INSN, zero otherwise. */
1755 df_reg_defined (rtx insn
, rtx reg
)
1757 return df_find_def (insn
, reg
) != NULL
;
1761 /* Finds the reference corresponding to the use of REG in INSN.
1762 DF is the dataflow object. */
1765 df_find_use (rtx insn
, rtx reg
)
1770 if (GET_CODE (reg
) == SUBREG
)
1771 reg
= SUBREG_REG (reg
);
1772 gcc_assert (REG_P (reg
));
1774 uid
= INSN_UID (insn
);
1775 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1777 df_ref use
= *use_rec
;
1778 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1781 if (df
->changeable_flags
& DF_EQ_NOTES
)
1782 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
1784 df_ref use
= *use_rec
;
1785 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1792 /* Return true if REG is referenced in INSN, zero otherwise. */
1795 df_reg_used (rtx insn
, rtx reg
)
1797 return df_find_use (insn
, reg
) != NULL
;
1801 /*----------------------------------------------------------------------------
1802 Debugging and printing functions.
1803 ----------------------------------------------------------------------------*/
1806 /* Write information about registers and basic blocks into FILE.
1807 This is part of making a debugging dump. */
1810 df_print_regset (FILE *file
, bitmap r
)
1816 fputs (" (nil)", file
);
1819 EXECUTE_IF_SET_IN_BITMAP (r
, 0, i
, bi
)
1821 fprintf (file
, " %d", i
);
1822 if (i
< FIRST_PSEUDO_REGISTER
)
1823 fprintf (file
, " [%s]", reg_names
[i
]);
1826 fprintf (file
, "\n");
1830 /* Write information about registers and basic blocks into FILE. The
1831 bitmap is in the form used by df_byte_lr. This is part of making a
1835 df_print_byte_regset (FILE *file
, bitmap r
)
1837 unsigned int max_reg
= max_reg_num ();
1841 fputs (" (nil)", file
);
1845 for (i
= 0; i
< max_reg
; i
++)
1847 unsigned int first
= df_byte_lr_get_regno_start (i
);
1848 unsigned int len
= df_byte_lr_get_regno_len (i
);
1855 EXECUTE_IF_SET_IN_BITMAP (r
, first
, j
, bi
)
1857 found
= j
< first
+ len
;
1862 const char * sep
= "";
1863 fprintf (file
, " %d", i
);
1864 if (i
< FIRST_PSEUDO_REGISTER
)
1865 fprintf (file
, " [%s]", reg_names
[i
]);
1866 fprintf (file
, "(");
1867 EXECUTE_IF_SET_IN_BITMAP (r
, first
, j
, bi
)
1869 if (j
> first
+ len
- 1)
1871 fprintf (file
, "%s%d", sep
, j
-first
);
1874 fprintf (file
, ")");
1879 if (bitmap_bit_p (r
, first
))
1881 fprintf (file
, " %d", i
);
1882 if (i
< FIRST_PSEUDO_REGISTER
)
1883 fprintf (file
, " [%s]", reg_names
[i
]);
1889 fprintf (file
, "\n");
1893 /* Dump dataflow info. */
1896 df_dump (FILE *file
)
1899 df_dump_start (file
);
1903 df_print_bb_index (bb
, file
);
1904 df_dump_top (bb
, file
);
1905 df_dump_bottom (bb
, file
);
1908 fprintf (file
, "\n");
1912 /* Dump dataflow info for df->blocks_to_analyze. */
1915 df_dump_region (FILE *file
)
1917 if (df
->blocks_to_analyze
)
1920 unsigned int bb_index
;
1922 fprintf (file
, "\n\nstarting region dump\n");
1923 df_dump_start (file
);
1925 EXECUTE_IF_SET_IN_BITMAP (df
->blocks_to_analyze
, 0, bb_index
, bi
)
1927 basic_block bb
= BASIC_BLOCK (bb_index
);
1929 df_print_bb_index (bb
, file
);
1930 df_dump_top (bb
, file
);
1931 df_dump_bottom (bb
, file
);
1933 fprintf (file
, "\n");
1940 /* Dump the introductory information for each problem defined. */
1943 df_dump_start (FILE *file
)
1950 fprintf (file
, "\n\n%s\n", current_function_name ());
1951 fprintf (file
, "\nDataflow summary:\n");
1952 if (df
->blocks_to_analyze
)
1953 fprintf (file
, "def_info->table_size = %d, use_info->table_size = %d\n",
1954 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1956 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1958 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1959 if (dflow
->computed
)
1961 df_dump_problem_function fun
= dflow
->problem
->dump_start_fun
;
1969 /* Dump the top of the block information for BB. */
1972 df_dump_top (basic_block bb
, FILE *file
)
1979 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1981 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1982 if (dflow
->computed
)
1984 df_dump_bb_problem_function bbfun
= dflow
->problem
->dump_top_fun
;
1992 /* Dump the bottom of the block information for BB. */
1995 df_dump_bottom (basic_block bb
, FILE *file
)
2002 for (i
= 0; i
< df
->num_problems_defined
; i
++)
2004 struct dataflow
*dflow
= df
->problems_in_order
[i
];
2005 if (dflow
->computed
)
2007 df_dump_bb_problem_function bbfun
= dflow
->problem
->dump_bottom_fun
;
2016 df_refs_chain_dump (df_ref
*ref_rec
, bool follow_chain
, FILE *file
)
2018 fprintf (file
, "{ ");
2021 df_ref ref
= *ref_rec
;
2022 fprintf (file
, "%c%d(%d)",
2023 DF_REF_REG_DEF_P (ref
) ? 'd' : (DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
2025 DF_REF_REGNO (ref
));
2027 df_chain_dump (DF_REF_CHAIN (ref
), file
);
2030 fprintf (file
, "}");
2034 /* Dump either a ref-def or reg-use chain. */
2037 df_regs_chain_dump (df_ref ref
, FILE *file
)
2039 fprintf (file
, "{ ");
2042 fprintf (file
, "%c%d(%d) ",
2043 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
2045 DF_REF_REGNO (ref
));
2046 ref
= DF_REF_NEXT_REG (ref
);
2048 fprintf (file
, "}");
2053 df_mws_dump (struct df_mw_hardreg
**mws
, FILE *file
)
2057 fprintf (file
, "mw %c r[%d..%d]\n",
2058 (DF_MWS_REG_DEF_P (*mws
)) ? 'd' : 'u',
2059 (*mws
)->start_regno
, (*mws
)->end_regno
);
2066 df_insn_uid_debug (unsigned int uid
,
2067 bool follow_chain
, FILE *file
)
2069 fprintf (file
, "insn %d luid %d",
2070 uid
, DF_INSN_UID_LUID (uid
));
2072 if (DF_INSN_UID_DEFS (uid
))
2074 fprintf (file
, " defs ");
2075 df_refs_chain_dump (DF_INSN_UID_DEFS (uid
), follow_chain
, file
);
2078 if (DF_INSN_UID_USES (uid
))
2080 fprintf (file
, " uses ");
2081 df_refs_chain_dump (DF_INSN_UID_USES (uid
), follow_chain
, file
);
2084 if (DF_INSN_UID_EQ_USES (uid
))
2086 fprintf (file
, " eq uses ");
2087 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid
), follow_chain
, file
);
2090 if (DF_INSN_UID_MWS (uid
))
2092 fprintf (file
, " mws ");
2093 df_mws_dump (DF_INSN_UID_MWS (uid
), file
);
2095 fprintf (file
, "\n");
2100 df_insn_debug (rtx insn
, bool follow_chain
, FILE *file
)
2102 df_insn_uid_debug (INSN_UID (insn
), follow_chain
, file
);
2106 df_insn_debug_regno (rtx insn
, FILE *file
)
2108 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2110 fprintf (file
, "insn %d bb %d luid %d defs ",
2111 INSN_UID (insn
), BLOCK_FOR_INSN (insn
)->index
,
2112 DF_INSN_INFO_LUID (insn_info
));
2113 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info
), false, file
);
2115 fprintf (file
, " uses ");
2116 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info
), false, file
);
2118 fprintf (file
, " eq_uses ");
2119 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info
), false, file
);
2120 fprintf (file
, "\n");
2124 df_regno_debug (unsigned int regno
, FILE *file
)
2126 fprintf (file
, "reg %d defs ", regno
);
2127 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno
), file
);
2128 fprintf (file
, " uses ");
2129 df_regs_chain_dump (DF_REG_USE_CHAIN (regno
), file
);
2130 fprintf (file
, " eq_uses ");
2131 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno
), file
);
2132 fprintf (file
, "\n");
2137 df_ref_debug (df_ref ref
, FILE *file
)
2139 fprintf (file
, "%c%d ",
2140 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
2142 fprintf (file
, "reg %d bb %d insn %d flag %#x type %#x ",
2145 DF_REF_IS_ARTIFICIAL (ref
) ? -1 : DF_REF_INSN_UID (ref
),
2148 if (DF_REF_LOC (ref
))
2150 if (flag_dump_noaddr
)
2151 fprintf (file
, "loc #(#) chain ");
2153 fprintf (file
, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref
),
2154 (void *)*DF_REF_LOC (ref
));
2157 fprintf (file
, "chain ");
2158 df_chain_dump (DF_REF_CHAIN (ref
), file
);
2159 fprintf (file
, "\n");
2162 /* Functions for debugging from GDB. */
2165 debug_df_insn (rtx insn
)
2167 df_insn_debug (insn
, true, stderr
);
2173 debug_df_reg (rtx reg
)
2175 df_regno_debug (REGNO (reg
), stderr
);
2180 debug_df_regno (unsigned int regno
)
2182 df_regno_debug (regno
, stderr
);
2187 debug_df_ref (df_ref ref
)
2189 df_ref_debug (ref
, stderr
);
2194 debug_df_defno (unsigned int defno
)
2196 df_ref_debug (DF_DEFS_GET (defno
), stderr
);
2201 debug_df_useno (unsigned int defno
)
2203 df_ref_debug (DF_USES_GET (defno
), stderr
);
2208 debug_df_chain (struct df_link
*link
)
2210 df_chain_dump (link
, stderr
);
2211 fputc ('\n', stderr
);