1 /* Allocation for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008, 2009, 2010, 2011 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"
388 #include "alloc-pool.h"
390 #include "hard-reg-set.h"
391 #include "basic-block.h"
396 #include "tree-pass.h"
399 static void *df_get_bb_info (struct dataflow
*, unsigned int);
400 static void df_set_bb_info (struct dataflow
*, unsigned int, void *);
401 static void df_clear_bb_info (struct dataflow
*, unsigned int);
403 static void df_set_clean_cfg (void);
406 /* The obstack on which regsets are allocated. */
407 struct bitmap_obstack reg_obstack
;
409 /* An obstack for bitmap not related to specific dataflow problems.
410 This obstack should e.g. be used for bitmaps with a short life time
411 such as temporary bitmaps. */
413 bitmap_obstack df_bitmap_obstack
;
416 /*----------------------------------------------------------------------------
417 Functions to create, destroy and manipulate an instance of df.
418 ----------------------------------------------------------------------------*/
422 /* Add PROBLEM (and any dependent problems) to the DF instance. */
425 df_add_problem (struct df_problem
*problem
)
427 struct dataflow
*dflow
;
430 /* First try to add the dependent problem. */
431 if (problem
->dependent_problem
)
432 df_add_problem (problem
->dependent_problem
);
434 /* Check to see if this problem has already been defined. If it
435 has, just return that instance, if not, add it to the end of the
437 dflow
= df
->problems_by_index
[problem
->id
];
441 /* Make a new one and add it to the end. */
442 dflow
= XCNEW (struct dataflow
);
443 dflow
->problem
= problem
;
444 dflow
->computed
= false;
445 dflow
->solutions_dirty
= true;
446 df
->problems_by_index
[dflow
->problem
->id
] = dflow
;
448 /* Keep the defined problems ordered by index. This solves the
449 problem that RI will use the information from UREC if UREC has
450 been defined, or from LIVE if LIVE is defined and otherwise LR.
451 However for this to work, the computation of RI must be pushed
452 after which ever of those problems is defined, but we do not
453 require any of those except for LR to have actually been
455 df
->num_problems_defined
++;
456 for (i
= df
->num_problems_defined
- 2; i
>= 0; i
--)
458 if (problem
->id
< df
->problems_in_order
[i
]->problem
->id
)
459 df
->problems_in_order
[i
+1] = df
->problems_in_order
[i
];
462 df
->problems_in_order
[i
+1] = dflow
;
466 df
->problems_in_order
[0] = dflow
;
470 /* Set the MASK flags in the DFLOW problem. The old flags are
471 returned. If a flag is not allowed to be changed this will fail if
472 checking is enabled. */
474 df_set_flags (int changeable_flags
)
476 int old_flags
= df
->changeable_flags
;
477 df
->changeable_flags
|= changeable_flags
;
482 /* Clear the MASK flags in the DFLOW problem. The old flags are
483 returned. If a flag is not allowed to be changed this will fail if
484 checking is enabled. */
486 df_clear_flags (int changeable_flags
)
488 int old_flags
= df
->changeable_flags
;
489 df
->changeable_flags
&= ~changeable_flags
;
494 /* Set the blocks that are to be considered for analysis. If this is
495 not called or is called with null, the entire function in
499 df_set_blocks (bitmap blocks
)
504 bitmap_print (dump_file
, blocks
, "setting blocks to analyze ", "\n");
505 if (df
->blocks_to_analyze
)
507 /* This block is called to change the focus from one subset
511 bitmap_initialize (&diff
, &df_bitmap_obstack
);
512 bitmap_and_compl (&diff
, df
->blocks_to_analyze
, blocks
);
513 for (p
= 0; p
< df
->num_problems_defined
; p
++)
515 struct dataflow
*dflow
= df
->problems_in_order
[p
];
516 if (dflow
->optional_p
&& dflow
->problem
->reset_fun
)
517 dflow
->problem
->reset_fun (df
->blocks_to_analyze
);
518 else if (dflow
->problem
->free_blocks_on_set_blocks
)
521 unsigned int bb_index
;
523 EXECUTE_IF_SET_IN_BITMAP (&diff
, 0, bb_index
, bi
)
525 basic_block bb
= BASIC_BLOCK (bb_index
);
528 void *bb_info
= df_get_bb_info (dflow
, bb_index
);
529 dflow
->problem
->free_bb_fun (bb
, bb_info
);
530 df_clear_bb_info (dflow
, bb_index
);
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_d
);
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 crtl
->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 */
763 TV_DF_SCAN
, /* tv_id */
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 */
790 TV_DF_SCAN
, /* tv_id */
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 ();
816 free (df
->postorder
);
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 ----------------------------------------------------------------------------*/
854 /* Return time BB when it was visited for last time. */
855 #define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
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.
863 AGE specify time when BB was visited last time.
864 AGE of 0 means we are visiting for first time and need to
865 compute transfer function to initialize datastructures.
866 Otherwise we re-do transfer function only if something change
867 while computing confluence functions.
868 We need to compute confluence only of basic block that are younger
869 then last visit of the BB.
871 Return true if BB info has changed. This is always the case
872 in the first visit. */
875 df_worklist_propagate_forward (struct dataflow
*dataflow
,
877 unsigned *bbindex_to_postorder
,
884 basic_block bb
= BASIC_BLOCK (bb_index
);
887 /* Calculate <conf_op> of incoming edges. */
888 if (EDGE_COUNT (bb
->preds
) > 0)
889 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
891 if (age
<= BB_LAST_CHANGE_AGE (e
->src
)
892 && TEST_BIT (considered
, e
->src
->index
))
893 changed
|= dataflow
->problem
->con_fun_n (e
);
895 else if (dataflow
->problem
->con_fun_0
)
896 dataflow
->problem
->con_fun_0 (bb
);
899 && dataflow
->problem
->trans_fun (bb_index
))
901 /* The out set of this block has changed.
902 Propagate to the outgoing blocks. */
903 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
905 unsigned ob_index
= e
->dest
->index
;
907 if (TEST_BIT (considered
, ob_index
))
908 bitmap_set_bit (pending
, bbindex_to_postorder
[ob_index
]);
916 /* Helper function for df_worklist_dataflow.
917 Propagate the dataflow backward. */
920 df_worklist_propagate_backward (struct dataflow
*dataflow
,
922 unsigned *bbindex_to_postorder
,
929 basic_block bb
= BASIC_BLOCK (bb_index
);
932 /* Calculate <conf_op> of incoming edges. */
933 if (EDGE_COUNT (bb
->succs
) > 0)
934 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
936 if (age
<= BB_LAST_CHANGE_AGE (e
->dest
)
937 && TEST_BIT (considered
, e
->dest
->index
))
938 changed
|= dataflow
->problem
->con_fun_n (e
);
940 else if (dataflow
->problem
->con_fun_0
)
941 dataflow
->problem
->con_fun_0 (bb
);
944 && dataflow
->problem
->trans_fun (bb_index
))
946 /* The out set of this block has changed.
947 Propagate to the outgoing blocks. */
948 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
950 unsigned ob_index
= e
->src
->index
;
952 if (TEST_BIT (considered
, ob_index
))
953 bitmap_set_bit (pending
, bbindex_to_postorder
[ob_index
]);
960 /* Main dataflow solver loop.
962 DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
964 BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
965 BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder possition.
966 PENDING will be freed.
968 The worklists are bitmaps indexed by postorder positions.
970 The function implements standard algorithm for dataflow solving with two
971 worklists (we are processing WORKLIST and storing new BBs to visit in
974 As an optimization we maintain ages when BB was changed (stored in bb->aux)
975 and when it was last visited (stored in last_visit_age). This avoids need
976 to re-do confluence function for edges to basic blocks whose source
977 did not change since destination was visited last time. */
980 df_worklist_dataflow_doublequeue (struct dataflow
*dataflow
,
983 int *blocks_in_postorder
,
984 unsigned *bbindex_to_postorder
,
987 enum df_flow_dir dir
= dataflow
->problem
->dir
;
989 bitmap worklist
= BITMAP_ALLOC (&df_bitmap_obstack
);
992 VEC(int, heap
) *last_visit_age
= NULL
;
997 VEC_safe_grow_cleared (int, heap
, last_visit_age
, n_blocks
);
999 /* Double-queueing. Worklist is for the current iteration,
1000 and pending is for the next. */
1001 while (!bitmap_empty_p (pending
))
1006 /* Swap pending and worklist. */
1007 bitmap temp
= worklist
;
1011 EXECUTE_IF_SET_IN_BITMAP (worklist
, 0, index
, bi
)
1016 bitmap_clear_bit (pending
, index
);
1017 bb_index
= blocks_in_postorder
[index
];
1018 bb
= BASIC_BLOCK (bb_index
);
1019 prev_age
= VEC_index (int, last_visit_age
, index
);
1020 if (dir
== DF_FORWARD
)
1021 changed
= df_worklist_propagate_forward (dataflow
, bb_index
,
1022 bbindex_to_postorder
,
1023 pending
, considered
,
1026 changed
= df_worklist_propagate_backward (dataflow
, bb_index
,
1027 bbindex_to_postorder
,
1028 pending
, considered
,
1030 VEC_replace (int, last_visit_age
, index
, ++age
);
1032 bb
->aux
= (void *)(ptrdiff_t)age
;
1034 bitmap_clear (worklist
);
1036 for (i
= 0; i
< n_blocks
; i
++)
1037 BASIC_BLOCK (blocks_in_postorder
[i
])->aux
= NULL
;
1039 BITMAP_FREE (worklist
);
1040 BITMAP_FREE (pending
);
1041 VEC_free (int, heap
, last_visit_age
);
1043 /* Dump statistics. */
1045 fprintf (dump_file
, "df_worklist_dataflow_doublequeue:"
1046 "n_basic_blocks %d n_edges %d"
1047 " count %d (%5.2g)\n",
1048 n_basic_blocks
, n_edges
,
1049 dcount
, dcount
/ (float)n_basic_blocks
);
1052 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
1053 with "n"-th bit representing the n-th block in the reverse-postorder order.
1054 The solver is a double-queue algorithm similar to the "double stack" solver
1055 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1056 The only significant difference is that the worklist in this implementation
1057 is always sorted in RPO of the CFG visiting direction. */
1060 df_worklist_dataflow (struct dataflow
*dataflow
,
1061 bitmap blocks_to_consider
,
1062 int *blocks_in_postorder
,
1065 bitmap pending
= BITMAP_ALLOC (&df_bitmap_obstack
);
1066 sbitmap considered
= sbitmap_alloc (last_basic_block
);
1068 unsigned int *bbindex_to_postorder
;
1071 enum df_flow_dir dir
= dataflow
->problem
->dir
;
1073 gcc_assert (dir
!= DF_NONE
);
1075 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
1076 bbindex_to_postorder
=
1077 (unsigned int *)xmalloc (last_basic_block
* sizeof (unsigned int));
1079 /* Initialize the array to an out-of-bound value. */
1080 for (i
= 0; i
< last_basic_block
; i
++)
1081 bbindex_to_postorder
[i
] = last_basic_block
;
1083 /* Initialize the considered map. */
1084 sbitmap_zero (considered
);
1085 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider
, 0, index
, bi
)
1087 SET_BIT (considered
, index
);
1090 /* Initialize the mapping of block index to postorder. */
1091 for (i
= 0; i
< n_blocks
; i
++)
1093 bbindex_to_postorder
[blocks_in_postorder
[i
]] = i
;
1094 /* Add all blocks to the worklist. */
1095 bitmap_set_bit (pending
, i
);
1098 /* Initialize the problem. */
1099 if (dataflow
->problem
->init_fun
)
1100 dataflow
->problem
->init_fun (blocks_to_consider
);
1103 df_worklist_dataflow_doublequeue (dataflow
, pending
, considered
,
1104 blocks_in_postorder
,
1105 bbindex_to_postorder
,
1107 sbitmap_free (considered
);
1108 free (bbindex_to_postorder
);
1112 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1113 the order of the remaining entries. Returns the length of the resulting
1117 df_prune_to_subcfg (int list
[], unsigned len
, bitmap blocks
)
1121 for (act
= 0, last
= 0; act
< len
; act
++)
1122 if (bitmap_bit_p (blocks
, list
[act
]))
1123 list
[last
++] = list
[act
];
1129 /* Execute dataflow analysis on a single dataflow problem.
1131 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1132 examined or will be computed. For calls from DF_ANALYZE, this is
1133 the set of blocks that has been passed to DF_SET_BLOCKS.
1137 df_analyze_problem (struct dataflow
*dflow
,
1138 bitmap blocks_to_consider
,
1139 int *postorder
, int n_blocks
)
1141 timevar_push (dflow
->problem
->tv_id
);
1143 /* (Re)Allocate the datastructures necessary to solve the problem. */
1144 if (dflow
->problem
->alloc_fun
)
1145 dflow
->problem
->alloc_fun (blocks_to_consider
);
1147 #ifdef ENABLE_DF_CHECKING
1148 if (dflow
->problem
->verify_start_fun
)
1149 dflow
->problem
->verify_start_fun ();
1152 /* Set up the problem and compute the local information. */
1153 if (dflow
->problem
->local_compute_fun
)
1154 dflow
->problem
->local_compute_fun (blocks_to_consider
);
1156 /* Solve the equations. */
1157 if (dflow
->problem
->dataflow_fun
)
1158 dflow
->problem
->dataflow_fun (dflow
, blocks_to_consider
,
1159 postorder
, n_blocks
);
1161 /* Massage the solution. */
1162 if (dflow
->problem
->finalize_fun
)
1163 dflow
->problem
->finalize_fun (blocks_to_consider
);
1165 #ifdef ENABLE_DF_CHECKING
1166 if (dflow
->problem
->verify_end_fun
)
1167 dflow
->problem
->verify_end_fun ();
1170 timevar_pop (dflow
->problem
->tv_id
);
1172 dflow
->computed
= true;
1176 /* Analyze dataflow info for the basic blocks specified by the bitmap
1177 BLOCKS, or for the whole CFG if BLOCKS is zero. */
1182 bitmap current_all_blocks
= BITMAP_ALLOC (&df_bitmap_obstack
);
1186 free (df
->postorder
);
1187 free (df
->postorder_inverted
);
1188 df
->postorder
= XNEWVEC (int, last_basic_block
);
1189 df
->postorder_inverted
= XNEWVEC (int, last_basic_block
);
1190 df
->n_blocks
= post_order_compute (df
->postorder
, true, true);
1191 df
->n_blocks_inverted
= inverted_post_order_compute (df
->postorder_inverted
);
1193 /* These should be the same. */
1194 gcc_assert (df
->n_blocks
== df
->n_blocks_inverted
);
1196 /* We need to do this before the df_verify_all because this is
1197 not kept incrementally up to date. */
1198 df_compute_regs_ever_live (false);
1199 df_process_deferred_rescans ();
1202 fprintf (dump_file
, "df_analyze called\n");
1204 #ifndef ENABLE_DF_CHECKING
1205 if (df
->changeable_flags
& DF_VERIFY_SCHEDULED
)
1209 for (i
= 0; i
< df
->n_blocks
; i
++)
1210 bitmap_set_bit (current_all_blocks
, df
->postorder
[i
]);
1212 #ifdef ENABLE_CHECKING
1213 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1215 for (i
= 0; i
< df
->n_blocks_inverted
; i
++)
1216 gcc_assert (bitmap_bit_p (current_all_blocks
, df
->postorder_inverted
[i
]));
1219 /* Make sure that we have pruned any unreachable blocks from these
1221 if (df
->analyze_subset
)
1224 bitmap_and_into (df
->blocks_to_analyze
, current_all_blocks
);
1225 df
->n_blocks
= df_prune_to_subcfg (df
->postorder
,
1226 df
->n_blocks
, df
->blocks_to_analyze
);
1227 df
->n_blocks_inverted
= df_prune_to_subcfg (df
->postorder_inverted
,
1228 df
->n_blocks_inverted
,
1229 df
->blocks_to_analyze
);
1230 BITMAP_FREE (current_all_blocks
);
1235 df
->blocks_to_analyze
= current_all_blocks
;
1236 current_all_blocks
= NULL
;
1239 /* Skip over the DF_SCAN problem. */
1240 for (i
= 1; i
< df
->num_problems_defined
; i
++)
1242 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1243 if (dflow
->solutions_dirty
)
1245 if (dflow
->problem
->dir
== DF_FORWARD
)
1246 df_analyze_problem (dflow
,
1247 df
->blocks_to_analyze
,
1248 df
->postorder_inverted
,
1249 df
->n_blocks_inverted
);
1251 df_analyze_problem (dflow
,
1252 df
->blocks_to_analyze
,
1260 BITMAP_FREE (df
->blocks_to_analyze
);
1261 df
->blocks_to_analyze
= NULL
;
1265 df_set_clean_cfg ();
1270 /* Return the number of basic blocks from the last call to df_analyze. */
1273 df_get_n_blocks (enum df_flow_dir dir
)
1275 gcc_assert (dir
!= DF_NONE
);
1277 if (dir
== DF_FORWARD
)
1279 gcc_assert (df
->postorder_inverted
);
1280 return df
->n_blocks_inverted
;
1283 gcc_assert (df
->postorder
);
1284 return df
->n_blocks
;
1288 /* Return a pointer to the array of basic blocks in the reverse postorder.
1289 Depending on the direction of the dataflow problem,
1290 it returns either the usual reverse postorder array
1291 or the reverse postorder of inverted traversal. */
1293 df_get_postorder (enum df_flow_dir dir
)
1295 gcc_assert (dir
!= DF_NONE
);
1297 if (dir
== DF_FORWARD
)
1299 gcc_assert (df
->postorder_inverted
);
1300 return df
->postorder_inverted
;
1302 gcc_assert (df
->postorder
);
1303 return df
->postorder
;
1306 static struct df_problem user_problem
;
1307 static struct dataflow user_dflow
;
1309 /* Interface for calling iterative dataflow with user defined
1310 confluence and transfer functions. All that is necessary is to
1311 supply DIR, a direction, CONF_FUN_0, a confluence function for
1312 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1313 confluence function, TRANS_FUN, the basic block transfer function,
1314 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1315 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1318 df_simple_dataflow (enum df_flow_dir dir
,
1319 df_init_function init_fun
,
1320 df_confluence_function_0 con_fun_0
,
1321 df_confluence_function_n con_fun_n
,
1322 df_transfer_function trans_fun
,
1323 bitmap blocks
, int * postorder
, int n_blocks
)
1325 memset (&user_problem
, 0, sizeof (struct df_problem
));
1326 user_problem
.dir
= dir
;
1327 user_problem
.init_fun
= init_fun
;
1328 user_problem
.con_fun_0
= con_fun_0
;
1329 user_problem
.con_fun_n
= con_fun_n
;
1330 user_problem
.trans_fun
= trans_fun
;
1331 user_dflow
.problem
= &user_problem
;
1332 df_worklist_dataflow (&user_dflow
, blocks
, postorder
, n_blocks
);
1337 /*----------------------------------------------------------------------------
1338 Functions to support limited incremental change.
1339 ----------------------------------------------------------------------------*/
1342 /* Get basic block info. */
1345 df_get_bb_info (struct dataflow
*dflow
, unsigned int index
)
1347 if (dflow
->block_info
== NULL
)
1349 if (index
>= dflow
->block_info_size
)
1351 return (void *)((char *)dflow
->block_info
1352 + index
* dflow
->problem
->block_info_elt_size
);
1356 /* Set basic block info. */
1359 df_set_bb_info (struct dataflow
*dflow
, unsigned int index
,
1362 gcc_assert (dflow
->block_info
);
1363 memcpy ((char *)dflow
->block_info
1364 + index
* dflow
->problem
->block_info_elt_size
,
1365 bb_info
, dflow
->problem
->block_info_elt_size
);
1369 /* Clear basic block info. */
1372 df_clear_bb_info (struct dataflow
*dflow
, unsigned int index
)
1374 gcc_assert (dflow
->block_info
);
1375 gcc_assert (dflow
->block_info_size
> index
);
1376 memset ((char *)dflow
->block_info
1377 + index
* dflow
->problem
->block_info_elt_size
,
1378 0, dflow
->problem
->block_info_elt_size
);
1382 /* Mark the solutions as being out of date. */
1385 df_mark_solutions_dirty (void)
1390 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1391 df
->problems_in_order
[p
]->solutions_dirty
= true;
1396 /* Return true if BB needs it's transfer functions recomputed. */
1399 df_get_bb_dirty (basic_block bb
)
1401 return bitmap_bit_p ((df_live
1402 ? df_live
: df_lr
)->out_of_date_transfer_functions
,
1407 /* Mark BB as needing it's transfer functions as being out of
1411 df_set_bb_dirty (basic_block bb
)
1413 bb
->flags
|= BB_MODIFIED
;
1417 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1419 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1420 if (dflow
->out_of_date_transfer_functions
)
1421 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, bb
->index
);
1423 df_mark_solutions_dirty ();
1428 /* Grow the bb_info array. */
1431 df_grow_bb_info (struct dataflow
*dflow
)
1433 unsigned int new_size
= last_basic_block
+ 1;
1434 if (dflow
->block_info_size
< new_size
)
1436 new_size
+= new_size
/ 4;
1438 = (void *)XRESIZEVEC (char, (char *)dflow
->block_info
,
1440 * dflow
->problem
->block_info_elt_size
);
1441 memset ((char *)dflow
->block_info
1442 + dflow
->block_info_size
1443 * dflow
->problem
->block_info_elt_size
,
1445 (new_size
- dflow
->block_info_size
)
1446 * dflow
->problem
->block_info_elt_size
);
1447 dflow
->block_info_size
= new_size
;
1452 /* Clear the dirty bits. This is called from places that delete
1455 df_clear_bb_dirty (basic_block bb
)
1458 for (p
= 1; p
< df
->num_problems_defined
; p
++)
1460 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1461 if (dflow
->out_of_date_transfer_functions
)
1462 bitmap_clear_bit (dflow
->out_of_date_transfer_functions
, bb
->index
);
1466 /* Called from the rtl_compact_blocks to reorganize the problems basic
1470 df_compact_blocks (void)
1474 void *problem_temps
;
1477 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
1478 for (p
= 0; p
< df
->num_problems_defined
; p
++)
1480 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1482 /* Need to reorganize the out_of_date_transfer_functions for the
1484 if (dflow
->out_of_date_transfer_functions
)
1486 bitmap_copy (&tmp
, dflow
->out_of_date_transfer_functions
);
1487 bitmap_clear (dflow
->out_of_date_transfer_functions
);
1488 if (bitmap_bit_p (&tmp
, ENTRY_BLOCK
))
1489 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
1490 if (bitmap_bit_p (&tmp
, EXIT_BLOCK
))
1491 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, EXIT_BLOCK
);
1493 i
= NUM_FIXED_BLOCKS
;
1496 if (bitmap_bit_p (&tmp
, bb
->index
))
1497 bitmap_set_bit (dflow
->out_of_date_transfer_functions
, i
);
1502 /* Now shuffle the block info for the problem. */
1503 if (dflow
->problem
->free_bb_fun
)
1505 int size
= last_basic_block
* dflow
->problem
->block_info_elt_size
;
1506 problem_temps
= XNEWVAR (char, size
);
1507 df_grow_bb_info (dflow
);
1508 memcpy (problem_temps
, dflow
->block_info
, size
);
1510 /* Copy the bb info from the problem tmps to the proper
1511 place in the block_info vector. Null out the copied
1512 item. The entry and exit blocks never move. */
1513 i
= NUM_FIXED_BLOCKS
;
1516 df_set_bb_info (dflow
, i
,
1517 (char *)problem_temps
1518 + bb
->index
* dflow
->problem
->block_info_elt_size
);
1521 memset ((char *)dflow
->block_info
1522 + i
* dflow
->problem
->block_info_elt_size
, 0,
1523 (last_basic_block
- i
)
1524 * dflow
->problem
->block_info_elt_size
);
1525 free (problem_temps
);
1529 /* Shuffle the bits in the basic_block indexed arrays. */
1531 if (df
->blocks_to_analyze
)
1533 if (bitmap_bit_p (&tmp
, ENTRY_BLOCK
))
1534 bitmap_set_bit (df
->blocks_to_analyze
, ENTRY_BLOCK
);
1535 if (bitmap_bit_p (&tmp
, EXIT_BLOCK
))
1536 bitmap_set_bit (df
->blocks_to_analyze
, EXIT_BLOCK
);
1537 bitmap_copy (&tmp
, df
->blocks_to_analyze
);
1538 bitmap_clear (df
->blocks_to_analyze
);
1539 i
= NUM_FIXED_BLOCKS
;
1542 if (bitmap_bit_p (&tmp
, bb
->index
))
1543 bitmap_set_bit (df
->blocks_to_analyze
, i
);
1548 bitmap_clear (&tmp
);
1550 i
= NUM_FIXED_BLOCKS
;
1553 SET_BASIC_BLOCK (i
, bb
);
1558 gcc_assert (i
== n_basic_blocks
);
1560 for (; i
< last_basic_block
; i
++)
1561 SET_BASIC_BLOCK (i
, NULL
);
1564 if (!df_lr
->solutions_dirty
)
1565 df_set_clean_cfg ();
1570 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1571 block. There is no excuse for people to do this kind of thing. */
1574 df_bb_replace (int old_index
, basic_block new_block
)
1576 int new_block_index
= new_block
->index
;
1580 fprintf (dump_file
, "shoving block %d into %d\n", new_block_index
, old_index
);
1583 gcc_assert (BASIC_BLOCK (old_index
) == NULL
);
1585 for (p
= 0; p
< df
->num_problems_defined
; p
++)
1587 struct dataflow
*dflow
= df
->problems_in_order
[p
];
1588 if (dflow
->block_info
)
1590 df_grow_bb_info (dflow
);
1591 df_set_bb_info (dflow
, old_index
,
1592 df_get_bb_info (dflow
, new_block_index
));
1596 df_clear_bb_dirty (new_block
);
1597 SET_BASIC_BLOCK (old_index
, new_block
);
1598 new_block
->index
= old_index
;
1599 df_set_bb_dirty (BASIC_BLOCK (old_index
));
1600 SET_BASIC_BLOCK (new_block_index
, NULL
);
1604 /* Free all of the per basic block dataflow from all of the problems.
1605 This is typically called before a basic block is deleted and the
1606 problem will be reanalyzed. */
1609 df_bb_delete (int bb_index
)
1611 basic_block bb
= BASIC_BLOCK (bb_index
);
1617 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1619 struct dataflow
*dflow
= df
->problems_in_order
[i
];
1620 if (dflow
->problem
->free_bb_fun
)
1622 void *bb_info
= df_get_bb_info (dflow
, bb_index
);
1625 dflow
->problem
->free_bb_fun (bb
, bb_info
);
1626 df_clear_bb_info (dflow
, bb_index
);
1630 df_clear_bb_dirty (bb
);
1631 df_mark_solutions_dirty ();
1635 /* Verify that there is a place for everything and everything is in
1636 its place. This is too expensive to run after every pass in the
1637 mainline. However this is an excellent debugging tool if the
1638 dataflow information is not being updated properly. You can just
1639 sprinkle calls in until you find the place that is changing an
1640 underlying structure without calling the proper updating
1647 #ifdef ENABLE_DF_CHECKING
1648 df_lr_verify_transfer_functions ();
1650 df_live_verify_transfer_functions ();
1656 /* Compute an array of ints that describes the cfg. This can be used
1657 to discover places where the cfg is modified by the appropriate
1658 calls have not been made to the keep df informed. The internals of
1659 this are unexciting, the key is that two instances of this can be
1660 compared to see if any changes have been made to the cfg. */
1663 df_compute_cfg_image (void)
1666 int size
= 2 + (2 * n_basic_blocks
);
1672 size
+= EDGE_COUNT (bb
->succs
);
1675 map
= XNEWVEC (int, size
);
1683 map
[i
++] = bb
->index
;
1684 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1685 map
[i
++] = e
->dest
->index
;
1692 static int *saved_cfg
= NULL
;
1695 /* This function compares the saved version of the cfg with the
1696 current cfg and aborts if the two are identical. The function
1697 silently returns if the cfg has been marked as dirty or the two are
1701 df_check_cfg_clean (void)
1708 if (df_lr
->solutions_dirty
)
1711 if (saved_cfg
== NULL
)
1714 new_map
= df_compute_cfg_image ();
1715 gcc_assert (memcmp (saved_cfg
, new_map
, saved_cfg
[0] * sizeof (int)) == 0);
1720 /* This function builds a cfg fingerprint and squirrels it away in
1724 df_set_clean_cfg (void)
1727 saved_cfg
= df_compute_cfg_image ();
1730 #endif /* DF_DEBUG_CFG */
1731 /*----------------------------------------------------------------------------
1732 PUBLIC INTERFACES TO QUERY INFORMATION.
1733 ----------------------------------------------------------------------------*/
1736 /* Return first def of REGNO within BB. */
1739 df_bb_regno_first_def_find (basic_block bb
, unsigned int regno
)
1745 FOR_BB_INSNS (bb
, insn
)
1750 uid
= INSN_UID (insn
);
1751 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1753 df_ref def
= *def_rec
;
1754 if (DF_REF_REGNO (def
) == regno
)
1762 /* Return last def of REGNO within BB. */
1765 df_bb_regno_last_def_find (basic_block bb
, unsigned int regno
)
1771 FOR_BB_INSNS_REVERSE (bb
, insn
)
1776 uid
= INSN_UID (insn
);
1777 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1779 df_ref def
= *def_rec
;
1780 if (DF_REF_REGNO (def
) == regno
)
1788 /* Finds the reference corresponding to the definition of REG in INSN.
1789 DF is the dataflow object. */
1792 df_find_def (rtx insn
, rtx reg
)
1797 if (GET_CODE (reg
) == SUBREG
)
1798 reg
= SUBREG_REG (reg
);
1799 gcc_assert (REG_P (reg
));
1801 uid
= INSN_UID (insn
);
1802 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1804 df_ref def
= *def_rec
;
1805 if (rtx_equal_p (DF_REF_REAL_REG (def
), reg
))
1813 /* Return true if REG is defined in INSN, zero otherwise. */
1816 df_reg_defined (rtx insn
, rtx reg
)
1818 return df_find_def (insn
, reg
) != NULL
;
1822 /* Finds the reference corresponding to the use of REG in INSN.
1823 DF is the dataflow object. */
1826 df_find_use (rtx insn
, rtx reg
)
1831 if (GET_CODE (reg
) == SUBREG
)
1832 reg
= SUBREG_REG (reg
);
1833 gcc_assert (REG_P (reg
));
1835 uid
= INSN_UID (insn
);
1836 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1838 df_ref use
= *use_rec
;
1839 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1842 if (df
->changeable_flags
& DF_EQ_NOTES
)
1843 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
1845 df_ref use
= *use_rec
;
1846 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1853 /* Return true if REG is referenced in INSN, zero otherwise. */
1856 df_reg_used (rtx insn
, rtx reg
)
1858 return df_find_use (insn
, reg
) != NULL
;
1862 /*----------------------------------------------------------------------------
1863 Debugging and printing functions.
1864 ----------------------------------------------------------------------------*/
1866 /* Write information about registers and basic blocks into FILE.
1867 This is part of making a debugging dump. */
1870 dump_regset (regset r
, FILE *outf
)
1873 reg_set_iterator rsi
;
1877 fputs (" (nil)", outf
);
1881 EXECUTE_IF_SET_IN_REG_SET (r
, 0, i
, rsi
)
1883 fprintf (outf
, " %d", i
);
1884 if (i
< FIRST_PSEUDO_REGISTER
)
1885 fprintf (outf
, " [%s]",
1890 /* Print a human-readable representation of R on the standard error
1891 stream. This function is designed to be used from within the
1893 extern void debug_regset (regset
);
1895 debug_regset (regset r
)
1897 dump_regset (r
, stderr
);
1898 putc ('\n', stderr
);
1901 /* Write information about registers and basic blocks into FILE.
1902 This is part of making a debugging dump. */
1905 df_print_regset (FILE *file
, bitmap r
)
1911 fputs (" (nil)", file
);
1914 EXECUTE_IF_SET_IN_BITMAP (r
, 0, i
, bi
)
1916 fprintf (file
, " %d", i
);
1917 if (i
< FIRST_PSEUDO_REGISTER
)
1918 fprintf (file
, " [%s]", reg_names
[i
]);
1921 fprintf (file
, "\n");
1925 /* Write information about registers and basic blocks into FILE. The
1926 bitmap is in the form used by df_byte_lr. This is part of making a
1930 df_print_word_regset (FILE *file
, bitmap r
)
1932 unsigned int max_reg
= max_reg_num ();
1935 fputs (" (nil)", file
);
1939 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_reg
; i
++)
1941 bool found
= (bitmap_bit_p (r
, 2 * i
)
1942 || bitmap_bit_p (r
, 2 * i
+ 1));
1946 const char * sep
= "";
1947 fprintf (file
, " %d", i
);
1948 fprintf (file
, "(");
1949 for (word
= 0; word
< 2; word
++)
1950 if (bitmap_bit_p (r
, 2 * i
+ word
))
1952 fprintf (file
, "%s%d", sep
, word
);
1955 fprintf (file
, ")");
1959 fprintf (file
, "\n");
1963 /* Dump dataflow info. */
1966 df_dump (FILE *file
)
1969 df_dump_start (file
);
1973 df_print_bb_index (bb
, file
);
1974 df_dump_top (bb
, file
);
1975 df_dump_bottom (bb
, file
);
1978 fprintf (file
, "\n");
1982 /* Dump dataflow info for df->blocks_to_analyze. */
1985 df_dump_region (FILE *file
)
1987 if (df
->blocks_to_analyze
)
1990 unsigned int bb_index
;
1992 fprintf (file
, "\n\nstarting region dump\n");
1993 df_dump_start (file
);
1995 EXECUTE_IF_SET_IN_BITMAP (df
->blocks_to_analyze
, 0, bb_index
, bi
)
1997 basic_block bb
= BASIC_BLOCK (bb_index
);
1999 df_print_bb_index (bb
, file
);
2000 df_dump_top (bb
, file
);
2001 df_dump_bottom (bb
, file
);
2003 fprintf (file
, "\n");
2010 /* Dump the introductory information for each problem defined. */
2013 df_dump_start (FILE *file
)
2020 fprintf (file
, "\n\n%s\n", current_function_name ());
2021 fprintf (file
, "\nDataflow summary:\n");
2022 if (df
->blocks_to_analyze
)
2023 fprintf (file
, "def_info->table_size = %d, use_info->table_size = %d\n",
2024 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
2026 for (i
= 0; i
< df
->num_problems_defined
; i
++)
2028 struct dataflow
*dflow
= df
->problems_in_order
[i
];
2029 if (dflow
->computed
)
2031 df_dump_problem_function fun
= dflow
->problem
->dump_start_fun
;
2039 /* Dump the top of the block information for BB. */
2042 df_dump_top (basic_block bb
, FILE *file
)
2049 for (i
= 0; i
< df
->num_problems_defined
; i
++)
2051 struct dataflow
*dflow
= df
->problems_in_order
[i
];
2052 if (dflow
->computed
)
2054 df_dump_bb_problem_function bbfun
= dflow
->problem
->dump_top_fun
;
2062 /* Dump the bottom of the block information for BB. */
2065 df_dump_bottom (basic_block bb
, FILE *file
)
2072 for (i
= 0; i
< df
->num_problems_defined
; i
++)
2074 struct dataflow
*dflow
= df
->problems_in_order
[i
];
2075 if (dflow
->computed
)
2077 df_dump_bb_problem_function bbfun
= dflow
->problem
->dump_bottom_fun
;
2086 df_ref_dump (df_ref ref
, FILE *file
)
2088 fprintf (file
, "%c%d(%d)",
2089 DF_REF_REG_DEF_P (ref
)
2091 : (DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
2093 DF_REF_REGNO (ref
));
2097 df_refs_chain_dump (df_ref
*ref_rec
, bool follow_chain
, FILE *file
)
2099 fprintf (file
, "{ ");
2102 df_ref ref
= *ref_rec
;
2103 df_ref_dump (ref
, file
);
2105 df_chain_dump (DF_REF_CHAIN (ref
), file
);
2108 fprintf (file
, "}");
2112 /* Dump either a ref-def or reg-use chain. */
2115 df_regs_chain_dump (df_ref ref
, FILE *file
)
2117 fprintf (file
, "{ ");
2120 df_ref_dump (ref
, file
);
2121 ref
= DF_REF_NEXT_REG (ref
);
2123 fprintf (file
, "}");
2128 df_mws_dump (struct df_mw_hardreg
**mws
, FILE *file
)
2132 fprintf (file
, "mw %c r[%d..%d]\n",
2133 (DF_MWS_REG_DEF_P (*mws
)) ? 'd' : 'u',
2134 (*mws
)->start_regno
, (*mws
)->end_regno
);
2141 df_insn_uid_debug (unsigned int uid
,
2142 bool follow_chain
, FILE *file
)
2144 fprintf (file
, "insn %d luid %d",
2145 uid
, DF_INSN_UID_LUID (uid
));
2147 if (DF_INSN_UID_DEFS (uid
))
2149 fprintf (file
, " defs ");
2150 df_refs_chain_dump (DF_INSN_UID_DEFS (uid
), follow_chain
, file
);
2153 if (DF_INSN_UID_USES (uid
))
2155 fprintf (file
, " uses ");
2156 df_refs_chain_dump (DF_INSN_UID_USES (uid
), follow_chain
, file
);
2159 if (DF_INSN_UID_EQ_USES (uid
))
2161 fprintf (file
, " eq uses ");
2162 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid
), follow_chain
, file
);
2165 if (DF_INSN_UID_MWS (uid
))
2167 fprintf (file
, " mws ");
2168 df_mws_dump (DF_INSN_UID_MWS (uid
), file
);
2170 fprintf (file
, "\n");
2175 df_insn_debug (rtx insn
, bool follow_chain
, FILE *file
)
2177 df_insn_uid_debug (INSN_UID (insn
), follow_chain
, file
);
2181 df_insn_debug_regno (rtx insn
, FILE *file
)
2183 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2185 fprintf (file
, "insn %d bb %d luid %d defs ",
2186 INSN_UID (insn
), BLOCK_FOR_INSN (insn
)->index
,
2187 DF_INSN_INFO_LUID (insn_info
));
2188 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info
), false, file
);
2190 fprintf (file
, " uses ");
2191 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info
), false, file
);
2193 fprintf (file
, " eq_uses ");
2194 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info
), false, file
);
2195 fprintf (file
, "\n");
2199 df_regno_debug (unsigned int regno
, FILE *file
)
2201 fprintf (file
, "reg %d defs ", regno
);
2202 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno
), file
);
2203 fprintf (file
, " uses ");
2204 df_regs_chain_dump (DF_REG_USE_CHAIN (regno
), file
);
2205 fprintf (file
, " eq_uses ");
2206 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno
), file
);
2207 fprintf (file
, "\n");
2212 df_ref_debug (df_ref ref
, FILE *file
)
2214 fprintf (file
, "%c%d ",
2215 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
2217 fprintf (file
, "reg %d bb %d insn %d flag %#x type %#x ",
2220 DF_REF_IS_ARTIFICIAL (ref
) ? -1 : DF_REF_INSN_UID (ref
),
2223 if (DF_REF_LOC (ref
))
2225 if (flag_dump_noaddr
)
2226 fprintf (file
, "loc #(#) chain ");
2228 fprintf (file
, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref
),
2229 (void *)*DF_REF_LOC (ref
));
2232 fprintf (file
, "chain ");
2233 df_chain_dump (DF_REF_CHAIN (ref
), file
);
2234 fprintf (file
, "\n");
2237 /* Functions for debugging from GDB. */
2240 debug_df_insn (rtx insn
)
2242 df_insn_debug (insn
, true, stderr
);
2248 debug_df_reg (rtx reg
)
2250 df_regno_debug (REGNO (reg
), stderr
);
2255 debug_df_regno (unsigned int regno
)
2257 df_regno_debug (regno
, stderr
);
2262 debug_df_ref (df_ref ref
)
2264 df_ref_debug (ref
, stderr
);
2269 debug_df_defno (unsigned int defno
)
2271 df_ref_debug (DF_DEFS_GET (defno
), stderr
);
2276 debug_df_useno (unsigned int defno
)
2278 df_ref_debug (DF_USES_GET (defno
), stderr
);
2283 debug_df_chain (struct df_link
*link
)
2285 df_chain_dump (link
, stderr
);
2286 fputc ('\n', stderr
);