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
);
1495 /* Shuffle the bits in the basic_block indexed arrays. */
1497 if (df
->blocks_to_analyze
)
1499 if (bitmap_bit_p (&tmp
, ENTRY_BLOCK
))
1500 bitmap_set_bit (df
->blocks_to_analyze
, ENTRY_BLOCK
);
1501 if (bitmap_bit_p (&tmp
, EXIT_BLOCK
))
1502 bitmap_set_bit (df
->blocks_to_analyze
, EXIT_BLOCK
);
1503 bitmap_copy (&tmp
, df
->blocks_to_analyze
);
1504 bitmap_clear (df
->blocks_to_analyze
);
1505 i
= NUM_FIXED_BLOCKS
;
1508 if (bitmap_bit_p (&tmp
, bb
->index
))
1509 bitmap_set_bit (df
->blocks_to_analyze
, i
);
1514 bitmap_clear (&tmp
);
1516 i
= NUM_FIXED_BLOCKS
;
1519 SET_BASIC_BLOCK (i
, bb
);
1524 gcc_assert (i
== n_basic_blocks
);
1526 for (; i
< last_basic_block
; i
++)
1527 SET_BASIC_BLOCK (i
, NULL
);
1530 if (!df_lr
->solutions_dirty
)
1531 df_set_clean_cfg ();
1536 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1537 block. There is no excuse for people to do this kind of thing. */
1540 df_bb_replace (int old_index
, basic_block new_block
)
1542 int new_block_index
= new_block
->index
;
1546 fprintf (dump_file
, "shoving block %d into %d\n", new_block_index
, old_index
);
1549 gcc_assert (BASIC_BLOCK (old_index
) == NULL
);
1551 for (p
= 0; p
< df
->num_problems_defined
; p
++)
1553 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1554 if (dflow
->block_info
)
1556 df_grow_bb_info (dflow
);
1557 df_set_bb_info (dflow
, old_index
,
1558 df_get_bb_info (dflow
, new_block_index
));
1562 df_clear_bb_dirty (new_block
);
1563 SET_BASIC_BLOCK (old_index
, new_block
);
1564 new_block
->index
= old_index
;
1565 df_set_bb_dirty (BASIC_BLOCK (old_index
));
1566 SET_BASIC_BLOCK (new_block_index
, NULL
);
1570 /* Free all of the per basic block dataflow from all of the problems.
1571 This is typically called before a basic block is deleted and the
1572 problem will be reanalyzed. */
1575 df_bb_delete (int bb_index
)
1577 basic_block bb
= BASIC_BLOCK (bb_index
);
1583 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1585 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1586 if (dflow
->problem
->free_bb_fun
)
1588 void *bb_info
= df_get_bb_info (dflow
, bb_index
);
1591 dflow
->problem
->free_bb_fun (bb
, bb_info
);
1592 df_clear_bb_info (dflow
, bb_index
);
1596 df_clear_bb_dirty (bb
);
1597 df_mark_solutions_dirty ();
1601 /* Verify that there is a place for everything and everything is in
1602 its place. This is too expensive to run after every pass in the
1603 mainline. However this is an excellent debugging tool if the
1604 dataflow information is not being updated properly. You can just
1605 sprinkle calls in until you find the place that is changing an
1606 underlying structure without calling the proper updating
1613 #ifdef ENABLE_DF_CHECKING
1614 df_lr_verify_transfer_functions ();
1616 df_live_verify_transfer_functions ();
1622 /* Compute an array of ints that describes the cfg. This can be used
1623 to discover places where the cfg is modified by the appropriate
1624 calls have not been made to the keep df informed. The internals of
1625 this are unexciting, the key is that two instances of this can be
1626 compared to see if any changes have been made to the cfg. */
1629 df_compute_cfg_image (void)
1632 int size
= 2 + (2 * n_basic_blocks
);
1638 size
+= EDGE_COUNT (bb
->succs
);
1641 map
= XNEWVEC (int, size
);
1649 map
[i
++] = bb
->index
;
1650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1651 map
[i
++] = e
->dest
->index
;
1658 static int *saved_cfg
= NULL
;
1661 /* This function compares the saved version of the cfg with the
1662 current cfg and aborts if the two are identical. The function
1663 silently returns if the cfg has been marked as dirty or the two are
1667 df_check_cfg_clean (void)
1674 if (df_lr
->solutions_dirty
)
1677 if (saved_cfg
== NULL
)
1680 new_map
= df_compute_cfg_image ();
1681 gcc_assert (memcmp (saved_cfg
, new_map
, saved_cfg
[0] * sizeof (int)) == 0);
1686 /* This function builds a cfg fingerprint and squirrels it away in
1690 df_set_clean_cfg (void)
1694 saved_cfg
= df_compute_cfg_image ();
1697 #endif /* DF_DEBUG_CFG */
1698 /*----------------------------------------------------------------------------
1699 PUBLIC INTERFACES TO QUERY INFORMATION.
1700 ----------------------------------------------------------------------------*/
1703 /* Return first def of REGNO within BB. */
1706 df_bb_regno_first_def_find (basic_block bb
, unsigned int regno
)
1712 FOR_BB_INSNS (bb
, insn
)
1717 uid
= INSN_UID (insn
);
1718 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1720 df_ref def
= *def_rec
;
1721 if (DF_REF_REGNO (def
) == regno
)
1729 /* Return last def of REGNO within BB. */
1732 df_bb_regno_last_def_find (basic_block bb
, unsigned int regno
)
1738 FOR_BB_INSNS_REVERSE (bb
, insn
)
1743 uid
= INSN_UID (insn
);
1744 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1746 df_ref def
= *def_rec
;
1747 if (DF_REF_REGNO (def
) == regno
)
1755 /* Finds the reference corresponding to the definition of REG in INSN.
1756 DF is the dataflow object. */
1759 df_find_def (rtx insn
, rtx reg
)
1764 if (GET_CODE (reg
) == SUBREG
)
1765 reg
= SUBREG_REG (reg
);
1766 gcc_assert (REG_P (reg
));
1768 uid
= INSN_UID (insn
);
1769 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1771 df_ref def
= *def_rec
;
1772 if (rtx_equal_p (DF_REF_REAL_REG (def
), reg
))
1780 /* Return true if REG is defined in INSN, zero otherwise. */
1783 df_reg_defined (rtx insn
, rtx reg
)
1785 return df_find_def (insn
, reg
) != NULL
;
1789 /* Finds the reference corresponding to the use of REG in INSN.
1790 DF is the dataflow object. */
1793 df_find_use (rtx insn
, rtx reg
)
1798 if (GET_CODE (reg
) == SUBREG
)
1799 reg
= SUBREG_REG (reg
);
1800 gcc_assert (REG_P (reg
));
1802 uid
= INSN_UID (insn
);
1803 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1805 df_ref use
= *use_rec
;
1806 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1809 if (df
->changeable_flags
& DF_EQ_NOTES
)
1810 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
1812 df_ref use
= *use_rec
;
1813 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1820 /* Return true if REG is referenced in INSN, zero otherwise. */
1823 df_reg_used (rtx insn
, rtx reg
)
1825 return df_find_use (insn
, reg
) != NULL
;
1829 /*----------------------------------------------------------------------------
1830 Debugging and printing functions.
1831 ----------------------------------------------------------------------------*/
1834 /* Write information about registers and basic blocks into FILE.
1835 This is part of making a debugging dump. */
1838 df_print_regset (FILE *file
, bitmap r
)
1844 fputs (" (nil)", file
);
1847 EXECUTE_IF_SET_IN_BITMAP (r
, 0, i
, bi
)
1849 fprintf (file
, " %d", i
);
1850 if (i
< FIRST_PSEUDO_REGISTER
)
1851 fprintf (file
, " [%s]", reg_names
[i
]);
1854 fprintf (file
, "\n");
1858 /* Write information about registers and basic blocks into FILE. The
1859 bitmap is in the form used by df_byte_lr. This is part of making a
1863 df_print_byte_regset (FILE *file
, bitmap r
)
1865 unsigned int max_reg
= max_reg_num ();
1869 fputs (" (nil)", file
);
1873 for (i
= 0; i
< max_reg
; i
++)
1875 unsigned int first
= df_byte_lr_get_regno_start (i
);
1876 unsigned int len
= df_byte_lr_get_regno_len (i
);
1883 EXECUTE_IF_SET_IN_BITMAP (r
, first
, j
, bi
)
1885 found
= j
< first
+ len
;
1890 const char * sep
= "";
1891 fprintf (file
, " %d", i
);
1892 if (i
< FIRST_PSEUDO_REGISTER
)
1893 fprintf (file
, " [%s]", reg_names
[i
]);
1894 fprintf (file
, "(");
1895 EXECUTE_IF_SET_IN_BITMAP (r
, first
, j
, bi
)
1897 if (j
> first
+ len
- 1)
1899 fprintf (file
, "%s%d", sep
, j
-first
);
1902 fprintf (file
, ")");
1907 if (bitmap_bit_p (r
, first
))
1909 fprintf (file
, " %d", i
);
1910 if (i
< FIRST_PSEUDO_REGISTER
)
1911 fprintf (file
, " [%s]", reg_names
[i
]);
1917 fprintf (file
, "\n");
1921 /* Dump dataflow info. */
1924 df_dump (FILE *file
)
1927 df_dump_start (file
);
1931 df_print_bb_index (bb
, file
);
1932 df_dump_top (bb
, file
);
1933 df_dump_bottom (bb
, file
);
1936 fprintf (file
, "\n");
1940 /* Dump dataflow info for df->blocks_to_analyze. */
1943 df_dump_region (FILE *file
)
1945 if (df
->blocks_to_analyze
)
1948 unsigned int bb_index
;
1950 fprintf (file
, "\n\nstarting region dump\n");
1951 df_dump_start (file
);
1953 EXECUTE_IF_SET_IN_BITMAP (df
->blocks_to_analyze
, 0, bb_index
, bi
)
1955 basic_block bb
= BASIC_BLOCK (bb_index
);
1957 df_print_bb_index (bb
, file
);
1958 df_dump_top (bb
, file
);
1959 df_dump_bottom (bb
, file
);
1961 fprintf (file
, "\n");
1968 /* Dump the introductory information for each problem defined. */
1971 df_dump_start (FILE *file
)
1978 fprintf (file
, "\n\n%s\n", current_function_name ());
1979 fprintf (file
, "\nDataflow summary:\n");
1980 if (df
->blocks_to_analyze
)
1981 fprintf (file
, "def_info->table_size = %d, use_info->table_size = %d\n",
1982 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1984 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1986 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1987 if (dflow
->computed
)
1989 df_dump_problem_function fun
= dflow
->problem
->dump_start_fun
;
1997 /* Dump the top of the block information for BB. */
2000 df_dump_top (basic_block bb
, FILE *file
)
2007 for (i
= 0; i
< df
->num_problems_defined
; i
++)
2009 struct dataflow
*dflow
= df
->problems_in_order
[i
];
2010 if (dflow
->computed
)
2012 df_dump_bb_problem_function bbfun
= dflow
->problem
->dump_top_fun
;
2020 /* Dump the bottom of the block information for BB. */
2023 df_dump_bottom (basic_block bb
, FILE *file
)
2030 for (i
= 0; i
< df
->num_problems_defined
; i
++)
2032 struct dataflow
*dflow
= df
->problems_in_order
[i
];
2033 if (dflow
->computed
)
2035 df_dump_bb_problem_function bbfun
= dflow
->problem
->dump_bottom_fun
;
2044 df_refs_chain_dump (df_ref
*ref_rec
, bool follow_chain
, FILE *file
)
2046 fprintf (file
, "{ ");
2049 df_ref ref
= *ref_rec
;
2050 fprintf (file
, "%c%d(%d)",
2051 DF_REF_REG_DEF_P (ref
) ? 'd' : (DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
2053 DF_REF_REGNO (ref
));
2055 df_chain_dump (DF_REF_CHAIN (ref
), file
);
2058 fprintf (file
, "}");
2062 /* Dump either a ref-def or reg-use chain. */
2065 df_regs_chain_dump (df_ref ref
, FILE *file
)
2067 fprintf (file
, "{ ");
2070 fprintf (file
, "%c%d(%d) ",
2071 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
2073 DF_REF_REGNO (ref
));
2074 ref
= DF_REF_NEXT_REG (ref
);
2076 fprintf (file
, "}");
2081 df_mws_dump (struct df_mw_hardreg
**mws
, FILE *file
)
2085 fprintf (file
, "mw %c r[%d..%d]\n",
2086 (DF_MWS_REG_DEF_P (*mws
)) ? 'd' : 'u',
2087 (*mws
)->start_regno
, (*mws
)->end_regno
);
2094 df_insn_uid_debug (unsigned int uid
,
2095 bool follow_chain
, FILE *file
)
2097 fprintf (file
, "insn %d luid %d",
2098 uid
, DF_INSN_UID_LUID (uid
));
2100 if (DF_INSN_UID_DEFS (uid
))
2102 fprintf (file
, " defs ");
2103 df_refs_chain_dump (DF_INSN_UID_DEFS (uid
), follow_chain
, file
);
2106 if (DF_INSN_UID_USES (uid
))
2108 fprintf (file
, " uses ");
2109 df_refs_chain_dump (DF_INSN_UID_USES (uid
), follow_chain
, file
);
2112 if (DF_INSN_UID_EQ_USES (uid
))
2114 fprintf (file
, " eq uses ");
2115 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid
), follow_chain
, file
);
2118 if (DF_INSN_UID_MWS (uid
))
2120 fprintf (file
, " mws ");
2121 df_mws_dump (DF_INSN_UID_MWS (uid
), file
);
2123 fprintf (file
, "\n");
2128 df_insn_debug (rtx insn
, bool follow_chain
, FILE *file
)
2130 df_insn_uid_debug (INSN_UID (insn
), follow_chain
, file
);
2134 df_insn_debug_regno (rtx insn
, FILE *file
)
2136 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2138 fprintf (file
, "insn %d bb %d luid %d defs ",
2139 INSN_UID (insn
), BLOCK_FOR_INSN (insn
)->index
,
2140 DF_INSN_INFO_LUID (insn_info
));
2141 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info
), false, file
);
2143 fprintf (file
, " uses ");
2144 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info
), false, file
);
2146 fprintf (file
, " eq_uses ");
2147 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info
), false, file
);
2148 fprintf (file
, "\n");
2152 df_regno_debug (unsigned int regno
, FILE *file
)
2154 fprintf (file
, "reg %d defs ", regno
);
2155 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno
), file
);
2156 fprintf (file
, " uses ");
2157 df_regs_chain_dump (DF_REG_USE_CHAIN (regno
), file
);
2158 fprintf (file
, " eq_uses ");
2159 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno
), file
);
2160 fprintf (file
, "\n");
2165 df_ref_debug (df_ref ref
, FILE *file
)
2167 fprintf (file
, "%c%d ",
2168 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
2170 fprintf (file
, "reg %d bb %d insn %d flag %#x type %#x ",
2173 DF_REF_IS_ARTIFICIAL (ref
) ? -1 : DF_REF_INSN_UID (ref
),
2176 if (DF_REF_LOC (ref
))
2178 if (flag_dump_noaddr
)
2179 fprintf (file
, "loc #(#) chain ");
2181 fprintf (file
, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref
),
2182 (void *)*DF_REF_LOC (ref
));
2185 fprintf (file
, "chain ");
2186 df_chain_dump (DF_REF_CHAIN (ref
), file
);
2187 fprintf (file
, "\n");
2190 /* Functions for debugging from GDB. */
2193 debug_df_insn (rtx insn
)
2195 df_insn_debug (insn
, true, stderr
);
2201 debug_df_reg (rtx reg
)
2203 df_regno_debug (REGNO (reg
), stderr
);
2208 debug_df_regno (unsigned int regno
)
2210 df_regno_debug (regno
, stderr
);
2215 debug_df_ref (df_ref ref
)
2217 df_ref_debug (ref
, stderr
);
2222 debug_df_defno (unsigned int defno
)
2224 df_ref_debug (DF_DEFS_GET (defno
), stderr
);
2229 debug_df_useno (unsigned int defno
)
2231 df_ref_debug (DF_USES_GET (defno
), stderr
);
2236 debug_df_chain (struct df_link
*link
)
2238 df_chain_dump (link
, stderr
);
2239 fputc ('\n', stderr
);