2010-11-27 François Dumont <francois.cppdevs@free.fr>
[official-gcc.git] / gcc / df-core.c
blob06ff854b57b91140a68d145b95e023da27c51592
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
14 version.
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
19 for more details.
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/>. */
26 OVERVIEW:
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
57 section.
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.
70 USAGE:
72 Here is an example of using the dataflow routines.
74 df_[chain,live,note,rd]_add_problem (flags);
76 df_set_blocks (blocks);
78 df_analyze ();
80 df_dump (stderr);
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.
134 INCREMENTAL SCANNING
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
142 to be rescanned.
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
155 cause problems.
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
191 be rescanned.
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.
205 DATA STRUCTURES
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
213 chains.
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.
222 PHILOSOPHY:
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.
248 DATA STRUCTURES:
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
257 register.
259 Note that the reg-def and reg-use chains are generally short for
260 pseudos and long for the hard registers.
262 ACCESSING INSNS:
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.
288 ACCESSING REFS:
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
313 them.
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
340 chains.
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.
356 NOTES:
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
371 read/write.
373 Paradoxical subreg writes do not leave a trace of the old content, so they
374 are write-only operations.
378 #include "config.h"
379 #include "system.h"
380 #include "coretypes.h"
381 #include "tm.h"
382 #include "rtl.h"
383 #include "tm_p.h"
384 #include "insn-config.h"
385 #include "recog.h"
386 #include "function.h"
387 #include "regs.h"
388 #include "output.h"
389 #include "alloc-pool.h"
390 #include "flags.h"
391 #include "hard-reg-set.h"
392 #include "basic-block.h"
393 #include "sbitmap.h"
394 #include "bitmap.h"
395 #include "timevar.h"
396 #include "df.h"
397 #include "tree-pass.h"
398 #include "params.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);
403 #ifdef DF_DEBUG_CFG
404 static void df_set_clean_cfg (void);
405 #endif
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 ----------------------------------------------------------------------------*/
418 struct df_d *df;
420 /* Add PROBLEM (and any dependent problems) to the DF instance. */
422 void
423 df_add_problem (struct df_problem *problem)
425 struct dataflow *dflow;
426 int i;
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
434 vector. */
435 dflow = df->problems_by_index[problem->id];
436 if (dflow)
437 return;
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
452 defined. */
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];
458 else
460 df->problems_in_order[i+1] = dflow;
461 return;
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;
476 return old_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;
488 return old_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
494 analyzed. */
496 void
497 df_set_blocks (bitmap blocks)
499 if (blocks)
501 if (dump_file)
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
506 to another. */
507 int p;
508 bitmap_head diff;
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)
518 bitmap_iterator bi;
519 unsigned int bb_index;
521 EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
523 basic_block bb = BASIC_BLOCK (bb_index);
524 if (bb)
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);
536 else
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;
542 int p;
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)
548 if (!initialized)
550 basic_block bb;
551 bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack);
552 FOR_ALL_BB(bb)
554 bitmap_set_bit (&blocks_to_reset, bb->index);
557 dflow->problem->reset_fun (&blocks_to_reset);
560 if (initialized)
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;
568 else
570 /* This block is executed to reset the focus to the entire
571 function. */
572 if (dump_file)
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
591 problem). */
593 void
594 df_remove_problem (struct dataflow *dflow)
596 struct df_problem *problem;
597 int i;
599 if (!dflow)
600 return;
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)
614 int j;
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--;
619 break;
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. */
631 void
632 df_finish_pass (bool verify ATTRIBUTE_UNUSED)
634 int i;
635 int removed = 0;
637 #ifdef ENABLE_DF_CHECKING
638 int saved_flags;
639 #endif
641 if (!df)
642 return;
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;
649 #endif
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;
662 removed++;
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 ();
685 if (df_live)
686 df_live_verify_transfer_functions ();
689 #ifdef DF_DEBUG_CFG
690 df_set_clean_cfg ();
691 #endif
692 #endif
694 #ifdef ENABLE_CHECKING
695 if (verify)
696 df->changeable_flags |= DF_VERIFY_SCHEDULED;
697 #endif
701 /* Set up the dataflow instance for the entire back end. */
703 static unsigned int
704 rest_of_handle_df_initialize (void)
706 gcc_assert (!df);
707 df = XCNEW (struct df_d);
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
713 correctly later. */
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 ();
721 if (optimize > 1)
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);
734 df_hard_reg_init ();
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);
738 df_scan_blocks ();
739 df_compute_regs_ever_live (false);
740 return 0;
744 static bool
745 gate_opt (void)
747 return optimize > 0;
751 struct rtl_opt_pass pass_df_initialize_opt =
754 RTL_PASS,
755 "dfinit", /* name */
756 gate_opt, /* gate */
757 rest_of_handle_df_initialize, /* execute */
758 NULL, /* sub */
759 NULL, /* next */
760 0, /* static_pass_number */
761 TV_DF_SCAN, /* tv_id */
762 0, /* properties_required */
763 0, /* properties_provided */
764 0, /* properties_destroyed */
765 0, /* todo_flags_start */
766 0 /* todo_flags_finish */
771 static bool
772 gate_no_opt (void)
774 return optimize == 0;
778 struct rtl_opt_pass pass_df_initialize_no_opt =
781 RTL_PASS,
782 "no-opt dfinit", /* name */
783 gate_no_opt, /* gate */
784 rest_of_handle_df_initialize, /* execute */
785 NULL, /* sub */
786 NULL, /* next */
787 0, /* static_pass_number */
788 TV_DF_SCAN, /* tv_id */
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. */
801 static unsigned int
802 rest_of_handle_df_finish (void)
804 int i;
806 gcc_assert (df);
808 for (i = 0; i < df->num_problems_defined; i++)
810 struct dataflow *dflow = df->problems_in_order[i];
811 dflow->problem->free_fun ();
814 if (df->postorder)
815 free (df->postorder);
816 if (df->postorder_inverted)
817 free (df->postorder_inverted);
818 free (df->hard_regs_live_count);
819 free (df);
820 df = NULL;
822 bitmap_obstack_release (&df_bitmap_obstack);
823 return 0;
827 struct rtl_opt_pass pass_df_finish =
830 RTL_PASS,
831 "dfinish", /* name */
832 NULL, /* gate */
833 rest_of_handle_df_finish, /* execute */
834 NULL, /* sub */
835 NULL, /* next */
836 0, /* static_pass_number */
837 TV_NONE, /* tv_id */
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. */
874 static bool
875 df_worklist_propagate_forward (struct dataflow *dataflow,
876 unsigned bb_index,
877 unsigned *bbindex_to_postorder,
878 bitmap pending,
879 sbitmap considered,
880 ptrdiff_t age)
882 edge e;
883 edge_iterator ei;
884 basic_block bb = BASIC_BLOCK (bb_index);
885 bool changed = !age;
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);
898 if (changed
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]);
910 return true;
912 return false;
916 /* Helper function for df_worklist_dataflow.
917 Propagate the dataflow backward. */
919 static bool
920 df_worklist_propagate_backward (struct dataflow *dataflow,
921 unsigned bb_index,
922 unsigned *bbindex_to_postorder,
923 bitmap pending,
924 sbitmap considered,
925 ptrdiff_t age)
927 edge e;
928 edge_iterator ei;
929 basic_block bb = BASIC_BLOCK (bb_index);
930 bool changed = !age;
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);
943 if (changed
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]);
955 return true;
957 return false;
960 /* Main dataflow solver loop.
962 DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
963 need to visit.
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
972 PENDING).
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. */
979 static void
980 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
981 bitmap pending,
982 sbitmap considered,
983 int *blocks_in_postorder,
984 unsigned *bbindex_to_postorder,
985 int n_blocks)
987 enum df_flow_dir dir = dataflow->problem->dir;
988 int dcount = 0;
989 bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
990 int age = 0;
991 bool changed;
992 VEC(int, heap) *last_visit_age = NULL;
993 int prev_age;
994 basic_block bb;
995 int i;
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))
1003 bitmap_iterator bi;
1004 unsigned int index;
1006 /* Swap pending and worklist. */
1007 bitmap temp = worklist;
1008 worklist = pending;
1009 pending = temp;
1011 EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
1013 unsigned bb_index;
1014 dcount++;
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,
1024 prev_age);
1025 else
1026 changed = df_worklist_propagate_backward (dataflow, bb_index,
1027 bbindex_to_postorder,
1028 pending, considered,
1029 prev_age);
1030 VEC_replace (int, last_visit_age, index, ++age);
1031 if (changed)
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. */
1044 if (dump_file)
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. */
1059 void
1060 df_worklist_dataflow (struct dataflow *dataflow,
1061 bitmap blocks_to_consider,
1062 int *blocks_in_postorder,
1063 int n_blocks)
1065 bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1066 sbitmap considered = sbitmap_alloc (last_basic_block);
1067 bitmap_iterator bi;
1068 unsigned int *bbindex_to_postorder;
1069 int i;
1070 unsigned int index;
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);
1102 /* Solve it. */
1103 df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1104 blocks_in_postorder,
1105 bbindex_to_postorder,
1106 n_blocks);
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
1114 list. */
1116 static unsigned
1117 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1119 unsigned act, last;
1121 for (act = 0, last = 0; act < len; act++)
1122 if (bitmap_bit_p (blocks, list[act]))
1123 list[last++] = list[act];
1125 return last;
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.
1136 void
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 ();
1150 #endif
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 ();
1168 #endif
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. */
1179 void
1180 df_analyze (void)
1182 bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1183 bool everything;
1184 int i;
1186 if (df->postorder)
1187 free (df->postorder);
1188 if (df->postorder_inverted)
1189 free (df->postorder_inverted);
1190 df->postorder = XNEWVEC (int, last_basic_block);
1191 df->postorder_inverted = XNEWVEC (int, last_basic_block);
1192 df->n_blocks = post_order_compute (df->postorder, true, true);
1193 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1195 /* These should be the same. */
1196 gcc_assert (df->n_blocks == df->n_blocks_inverted);
1198 /* We need to do this before the df_verify_all because this is
1199 not kept incrementally up to date. */
1200 df_compute_regs_ever_live (false);
1201 df_process_deferred_rescans ();
1203 if (dump_file)
1204 fprintf (dump_file, "df_analyze called\n");
1206 #ifndef ENABLE_DF_CHECKING
1207 if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1208 #endif
1209 df_verify ();
1211 for (i = 0; i < df->n_blocks; i++)
1212 bitmap_set_bit (current_all_blocks, df->postorder[i]);
1214 #ifdef ENABLE_CHECKING
1215 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1216 the ENTRY block. */
1217 for (i = 0; i < df->n_blocks_inverted; i++)
1218 gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1219 #endif
1221 /* Make sure that we have pruned any unreachable blocks from these
1222 sets. */
1223 if (df->analyze_subset)
1225 everything = false;
1226 bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1227 df->n_blocks = df_prune_to_subcfg (df->postorder,
1228 df->n_blocks, df->blocks_to_analyze);
1229 df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1230 df->n_blocks_inverted,
1231 df->blocks_to_analyze);
1232 BITMAP_FREE (current_all_blocks);
1234 else
1236 everything = true;
1237 df->blocks_to_analyze = current_all_blocks;
1238 current_all_blocks = NULL;
1241 /* Skip over the DF_SCAN problem. */
1242 for (i = 1; i < df->num_problems_defined; i++)
1244 struct dataflow *dflow = df->problems_in_order[i];
1245 if (dflow->solutions_dirty)
1247 if (dflow->problem->dir == DF_FORWARD)
1248 df_analyze_problem (dflow,
1249 df->blocks_to_analyze,
1250 df->postorder_inverted,
1251 df->n_blocks_inverted);
1252 else
1253 df_analyze_problem (dflow,
1254 df->blocks_to_analyze,
1255 df->postorder,
1256 df->n_blocks);
1260 if (everything)
1262 BITMAP_FREE (df->blocks_to_analyze);
1263 df->blocks_to_analyze = NULL;
1266 #ifdef DF_DEBUG_CFG
1267 df_set_clean_cfg ();
1268 #endif
1272 /* Return the number of basic blocks from the last call to df_analyze. */
1275 df_get_n_blocks (enum df_flow_dir dir)
1277 gcc_assert (dir != DF_NONE);
1279 if (dir == DF_FORWARD)
1281 gcc_assert (df->postorder_inverted);
1282 return df->n_blocks_inverted;
1285 gcc_assert (df->postorder);
1286 return df->n_blocks;
1290 /* Return a pointer to the array of basic blocks in the reverse postorder.
1291 Depending on the direction of the dataflow problem,
1292 it returns either the usual reverse postorder array
1293 or the reverse postorder of inverted traversal. */
1294 int *
1295 df_get_postorder (enum df_flow_dir dir)
1297 gcc_assert (dir != DF_NONE);
1299 if (dir == DF_FORWARD)
1301 gcc_assert (df->postorder_inverted);
1302 return df->postorder_inverted;
1304 gcc_assert (df->postorder);
1305 return df->postorder;
1308 static struct df_problem user_problem;
1309 static struct dataflow user_dflow;
1311 /* Interface for calling iterative dataflow with user defined
1312 confluence and transfer functions. All that is necessary is to
1313 supply DIR, a direction, CONF_FUN_0, a confluence function for
1314 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1315 confluence function, TRANS_FUN, the basic block transfer function,
1316 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1317 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1319 void
1320 df_simple_dataflow (enum df_flow_dir dir,
1321 df_init_function init_fun,
1322 df_confluence_function_0 con_fun_0,
1323 df_confluence_function_n con_fun_n,
1324 df_transfer_function trans_fun,
1325 bitmap blocks, int * postorder, int n_blocks)
1327 memset (&user_problem, 0, sizeof (struct df_problem));
1328 user_problem.dir = dir;
1329 user_problem.init_fun = init_fun;
1330 user_problem.con_fun_0 = con_fun_0;
1331 user_problem.con_fun_n = con_fun_n;
1332 user_problem.trans_fun = trans_fun;
1333 user_dflow.problem = &user_problem;
1334 df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1339 /*----------------------------------------------------------------------------
1340 Functions to support limited incremental change.
1341 ----------------------------------------------------------------------------*/
1344 /* Get basic block info. */
1346 static void *
1347 df_get_bb_info (struct dataflow *dflow, unsigned int index)
1349 if (dflow->block_info == NULL)
1350 return NULL;
1351 if (index >= dflow->block_info_size)
1352 return NULL;
1353 return (void *)((char *)dflow->block_info
1354 + index * dflow->problem->block_info_elt_size);
1358 /* Set basic block info. */
1360 static void
1361 df_set_bb_info (struct dataflow *dflow, unsigned int index,
1362 void *bb_info)
1364 gcc_assert (dflow->block_info);
1365 memcpy ((char *)dflow->block_info
1366 + index * dflow->problem->block_info_elt_size,
1367 bb_info, dflow->problem->block_info_elt_size);
1371 /* Clear basic block info. */
1373 static void
1374 df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1376 gcc_assert (dflow->block_info);
1377 gcc_assert (dflow->block_info_size > index);
1378 memset ((char *)dflow->block_info
1379 + index * dflow->problem->block_info_elt_size,
1380 0, dflow->problem->block_info_elt_size);
1384 /* Mark the solutions as being out of date. */
1386 void
1387 df_mark_solutions_dirty (void)
1389 if (df)
1391 int p;
1392 for (p = 1; p < df->num_problems_defined; p++)
1393 df->problems_in_order[p]->solutions_dirty = true;
1398 /* Return true if BB needs it's transfer functions recomputed. */
1400 bool
1401 df_get_bb_dirty (basic_block bb)
1403 if (df && df_live)
1404 return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
1405 else
1406 return false;
1410 /* Mark BB as needing it's transfer functions as being out of
1411 date. */
1413 void
1414 df_set_bb_dirty (basic_block bb)
1416 if (df)
1418 int p;
1419 for (p = 1; p < df->num_problems_defined; p++)
1421 struct dataflow *dflow = df->problems_in_order[p];
1422 if (dflow->out_of_date_transfer_functions)
1423 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1425 df_mark_solutions_dirty ();
1430 /* Grow the bb_info array. */
1432 void
1433 df_grow_bb_info (struct dataflow *dflow)
1435 unsigned int new_size = last_basic_block + 1;
1436 if (dflow->block_info_size < new_size)
1438 new_size += new_size / 4;
1439 dflow->block_info
1440 = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1441 new_size
1442 * dflow->problem->block_info_elt_size);
1443 memset ((char *)dflow->block_info
1444 + dflow->block_info_size
1445 * dflow->problem->block_info_elt_size,
1447 (new_size - dflow->block_info_size)
1448 * dflow->problem->block_info_elt_size);
1449 dflow->block_info_size = new_size;
1454 /* Clear the dirty bits. This is called from places that delete
1455 blocks. */
1456 static void
1457 df_clear_bb_dirty (basic_block bb)
1459 int p;
1460 for (p = 1; p < df->num_problems_defined; p++)
1462 struct dataflow *dflow = df->problems_in_order[p];
1463 if (dflow->out_of_date_transfer_functions)
1464 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1468 /* Called from the rtl_compact_blocks to reorganize the problems basic
1469 block info. */
1471 void
1472 df_compact_blocks (void)
1474 int i, p;
1475 basic_block bb;
1476 void *problem_temps;
1477 bitmap_head tmp;
1479 bitmap_initialize (&tmp, &df_bitmap_obstack);
1480 for (p = 0; p < df->num_problems_defined; p++)
1482 struct dataflow *dflow = df->problems_in_order[p];
1484 /* Need to reorganize the out_of_date_transfer_functions for the
1485 dflow problem. */
1486 if (dflow->out_of_date_transfer_functions)
1488 bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
1489 bitmap_clear (dflow->out_of_date_transfer_functions);
1490 if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1491 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1492 if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1493 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1495 i = NUM_FIXED_BLOCKS;
1496 FOR_EACH_BB (bb)
1498 if (bitmap_bit_p (&tmp, bb->index))
1499 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1500 i++;
1504 /* Now shuffle the block info for the problem. */
1505 if (dflow->problem->free_bb_fun)
1507 int size = last_basic_block * dflow->problem->block_info_elt_size;
1508 problem_temps = XNEWVAR (char, size);
1509 df_grow_bb_info (dflow);
1510 memcpy (problem_temps, dflow->block_info, size);
1512 /* Copy the bb info from the problem tmps to the proper
1513 place in the block_info vector. Null out the copied
1514 item. The entry and exit blocks never move. */
1515 i = NUM_FIXED_BLOCKS;
1516 FOR_EACH_BB (bb)
1518 df_set_bb_info (dflow, i,
1519 (char *)problem_temps
1520 + bb->index * dflow->problem->block_info_elt_size);
1521 i++;
1523 memset ((char *)dflow->block_info
1524 + i * dflow->problem->block_info_elt_size, 0,
1525 (last_basic_block - i)
1526 * dflow->problem->block_info_elt_size);
1527 free (problem_temps);
1531 /* Shuffle the bits in the basic_block indexed arrays. */
1533 if (df->blocks_to_analyze)
1535 if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1536 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1537 if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1538 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1539 bitmap_copy (&tmp, df->blocks_to_analyze);
1540 bitmap_clear (df->blocks_to_analyze);
1541 i = NUM_FIXED_BLOCKS;
1542 FOR_EACH_BB (bb)
1544 if (bitmap_bit_p (&tmp, bb->index))
1545 bitmap_set_bit (df->blocks_to_analyze, i);
1546 i++;
1550 bitmap_clear (&tmp);
1552 i = NUM_FIXED_BLOCKS;
1553 FOR_EACH_BB (bb)
1555 SET_BASIC_BLOCK (i, bb);
1556 bb->index = i;
1557 i++;
1560 gcc_assert (i == n_basic_blocks);
1562 for (; i < last_basic_block; i++)
1563 SET_BASIC_BLOCK (i, NULL);
1565 #ifdef DF_DEBUG_CFG
1566 if (!df_lr->solutions_dirty)
1567 df_set_clean_cfg ();
1568 #endif
1572 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1573 block. There is no excuse for people to do this kind of thing. */
1575 void
1576 df_bb_replace (int old_index, basic_block new_block)
1578 int new_block_index = new_block->index;
1579 int p;
1581 if (dump_file)
1582 fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1584 gcc_assert (df);
1585 gcc_assert (BASIC_BLOCK (old_index) == NULL);
1587 for (p = 0; p < df->num_problems_defined; p++)
1589 struct dataflow *dflow = df->problems_in_order[p];
1590 if (dflow->block_info)
1592 df_grow_bb_info (dflow);
1593 df_set_bb_info (dflow, old_index,
1594 df_get_bb_info (dflow, new_block_index));
1598 df_clear_bb_dirty (new_block);
1599 SET_BASIC_BLOCK (old_index, new_block);
1600 new_block->index = old_index;
1601 df_set_bb_dirty (BASIC_BLOCK (old_index));
1602 SET_BASIC_BLOCK (new_block_index, NULL);
1606 /* Free all of the per basic block dataflow from all of the problems.
1607 This is typically called before a basic block is deleted and the
1608 problem will be reanalyzed. */
1610 void
1611 df_bb_delete (int bb_index)
1613 basic_block bb = BASIC_BLOCK (bb_index);
1614 int i;
1616 if (!df)
1617 return;
1619 for (i = 0; i < df->num_problems_defined; i++)
1621 struct dataflow *dflow = df->problems_in_order[i];
1622 if (dflow->problem->free_bb_fun)
1624 void *bb_info = df_get_bb_info (dflow, bb_index);
1625 if (bb_info)
1627 dflow->problem->free_bb_fun (bb, bb_info);
1628 df_clear_bb_info (dflow, bb_index);
1632 df_clear_bb_dirty (bb);
1633 df_mark_solutions_dirty ();
1637 /* Verify that there is a place for everything and everything is in
1638 its place. This is too expensive to run after every pass in the
1639 mainline. However this is an excellent debugging tool if the
1640 dataflow information is not being updated properly. You can just
1641 sprinkle calls in until you find the place that is changing an
1642 underlying structure without calling the proper updating
1643 routine. */
1645 void
1646 df_verify (void)
1648 df_scan_verify ();
1649 #ifdef ENABLE_DF_CHECKING
1650 df_lr_verify_transfer_functions ();
1651 if (df_live)
1652 df_live_verify_transfer_functions ();
1653 #endif
1656 #ifdef DF_DEBUG_CFG
1658 /* Compute an array of ints that describes the cfg. This can be used
1659 to discover places where the cfg is modified by the appropriate
1660 calls have not been made to the keep df informed. The internals of
1661 this are unexciting, the key is that two instances of this can be
1662 compared to see if any changes have been made to the cfg. */
1664 static int *
1665 df_compute_cfg_image (void)
1667 basic_block bb;
1668 int size = 2 + (2 * n_basic_blocks);
1669 int i;
1670 int * map;
1672 FOR_ALL_BB (bb)
1674 size += EDGE_COUNT (bb->succs);
1677 map = XNEWVEC (int, size);
1678 map[0] = size;
1679 i = 1;
1680 FOR_ALL_BB (bb)
1682 edge_iterator ei;
1683 edge e;
1685 map[i++] = bb->index;
1686 FOR_EACH_EDGE (e, ei, bb->succs)
1687 map[i++] = e->dest->index;
1688 map[i++] = -1;
1690 map[i] = -1;
1691 return map;
1694 static int *saved_cfg = NULL;
1697 /* This function compares the saved version of the cfg with the
1698 current cfg and aborts if the two are identical. The function
1699 silently returns if the cfg has been marked as dirty or the two are
1700 the same. */
1702 void
1703 df_check_cfg_clean (void)
1705 int *new_map;
1707 if (!df)
1708 return;
1710 if (df_lr->solutions_dirty)
1711 return;
1713 if (saved_cfg == NULL)
1714 return;
1716 new_map = df_compute_cfg_image ();
1717 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1718 free (new_map);
1722 /* This function builds a cfg fingerprint and squirrels it away in
1723 saved_cfg. */
1725 static void
1726 df_set_clean_cfg (void)
1728 if (saved_cfg)
1729 free (saved_cfg);
1730 saved_cfg = df_compute_cfg_image ();
1733 #endif /* DF_DEBUG_CFG */
1734 /*----------------------------------------------------------------------------
1735 PUBLIC INTERFACES TO QUERY INFORMATION.
1736 ----------------------------------------------------------------------------*/
1739 /* Return first def of REGNO within BB. */
1741 df_ref
1742 df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1744 rtx insn;
1745 df_ref *def_rec;
1746 unsigned int uid;
1748 FOR_BB_INSNS (bb, insn)
1750 if (!INSN_P (insn))
1751 continue;
1753 uid = INSN_UID (insn);
1754 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1756 df_ref def = *def_rec;
1757 if (DF_REF_REGNO (def) == regno)
1758 return def;
1761 return NULL;
1765 /* Return last def of REGNO within BB. */
1767 df_ref
1768 df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1770 rtx insn;
1771 df_ref *def_rec;
1772 unsigned int uid;
1774 FOR_BB_INSNS_REVERSE (bb, insn)
1776 if (!INSN_P (insn))
1777 continue;
1779 uid = INSN_UID (insn);
1780 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1782 df_ref def = *def_rec;
1783 if (DF_REF_REGNO (def) == regno)
1784 return def;
1788 return NULL;
1791 /* Finds the reference corresponding to the definition of REG in INSN.
1792 DF is the dataflow object. */
1794 df_ref
1795 df_find_def (rtx insn, rtx reg)
1797 unsigned int uid;
1798 df_ref *def_rec;
1800 if (GET_CODE (reg) == SUBREG)
1801 reg = SUBREG_REG (reg);
1802 gcc_assert (REG_P (reg));
1804 uid = INSN_UID (insn);
1805 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1807 df_ref def = *def_rec;
1808 if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1809 return def;
1812 return NULL;
1816 /* Return true if REG is defined in INSN, zero otherwise. */
1818 bool
1819 df_reg_defined (rtx insn, rtx reg)
1821 return df_find_def (insn, reg) != NULL;
1825 /* Finds the reference corresponding to the use of REG in INSN.
1826 DF is the dataflow object. */
1828 df_ref
1829 df_find_use (rtx insn, rtx reg)
1831 unsigned int uid;
1832 df_ref *use_rec;
1834 if (GET_CODE (reg) == SUBREG)
1835 reg = SUBREG_REG (reg);
1836 gcc_assert (REG_P (reg));
1838 uid = INSN_UID (insn);
1839 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1841 df_ref use = *use_rec;
1842 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1843 return use;
1845 if (df->changeable_flags & DF_EQ_NOTES)
1846 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1848 df_ref use = *use_rec;
1849 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1850 return use;
1852 return NULL;
1856 /* Return true if REG is referenced in INSN, zero otherwise. */
1858 bool
1859 df_reg_used (rtx insn, rtx reg)
1861 return df_find_use (insn, reg) != NULL;
1865 /*----------------------------------------------------------------------------
1866 Debugging and printing functions.
1867 ----------------------------------------------------------------------------*/
1870 /* Write information about registers and basic blocks into FILE.
1871 This is part of making a debugging dump. */
1873 void
1874 df_print_regset (FILE *file, bitmap r)
1876 unsigned int i;
1877 bitmap_iterator bi;
1879 if (r == NULL)
1880 fputs (" (nil)", file);
1881 else
1883 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1885 fprintf (file, " %d", i);
1886 if (i < FIRST_PSEUDO_REGISTER)
1887 fprintf (file, " [%s]", reg_names[i]);
1890 fprintf (file, "\n");
1894 /* Write information about registers and basic blocks into FILE. The
1895 bitmap is in the form used by df_byte_lr. This is part of making a
1896 debugging dump. */
1898 void
1899 df_print_word_regset (FILE *file, bitmap r)
1901 unsigned int max_reg = max_reg_num ();
1903 if (r == NULL)
1904 fputs (" (nil)", file);
1905 else
1907 unsigned int i;
1908 for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
1910 bool found = (bitmap_bit_p (r, 2 * i)
1911 || bitmap_bit_p (r, 2 * i + 1));
1912 if (found)
1914 int word;
1915 const char * sep = "";
1916 fprintf (file, " %d", i);
1917 fprintf (file, "(");
1918 for (word = 0; word < 2; word++)
1919 if (bitmap_bit_p (r, 2 * i + word))
1921 fprintf (file, "%s%d", sep, word);
1922 sep = ", ";
1924 fprintf (file, ")");
1928 fprintf (file, "\n");
1932 /* Dump dataflow info. */
1934 void
1935 df_dump (FILE *file)
1937 basic_block bb;
1938 df_dump_start (file);
1940 FOR_ALL_BB (bb)
1942 df_print_bb_index (bb, file);
1943 df_dump_top (bb, file);
1944 df_dump_bottom (bb, file);
1947 fprintf (file, "\n");
1951 /* Dump dataflow info for df->blocks_to_analyze. */
1953 void
1954 df_dump_region (FILE *file)
1956 if (df->blocks_to_analyze)
1958 bitmap_iterator bi;
1959 unsigned int bb_index;
1961 fprintf (file, "\n\nstarting region dump\n");
1962 df_dump_start (file);
1964 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1966 basic_block bb = BASIC_BLOCK (bb_index);
1968 df_print_bb_index (bb, file);
1969 df_dump_top (bb, file);
1970 df_dump_bottom (bb, file);
1972 fprintf (file, "\n");
1974 else
1975 df_dump (file);
1979 /* Dump the introductory information for each problem defined. */
1981 void
1982 df_dump_start (FILE *file)
1984 int i;
1986 if (!df || !file)
1987 return;
1989 fprintf (file, "\n\n%s\n", current_function_name ());
1990 fprintf (file, "\nDataflow summary:\n");
1991 if (df->blocks_to_analyze)
1992 fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
1993 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1995 for (i = 0; i < df->num_problems_defined; i++)
1997 struct dataflow *dflow = df->problems_in_order[i];
1998 if (dflow->computed)
2000 df_dump_problem_function fun = dflow->problem->dump_start_fun;
2001 if (fun)
2002 fun(file);
2008 /* Dump the top of the block information for BB. */
2010 void
2011 df_dump_top (basic_block bb, FILE *file)
2013 int i;
2015 if (!df || !file)
2016 return;
2018 for (i = 0; i < df->num_problems_defined; i++)
2020 struct dataflow *dflow = df->problems_in_order[i];
2021 if (dflow->computed)
2023 df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
2024 if (bbfun)
2025 bbfun (bb, file);
2031 /* Dump the bottom of the block information for BB. */
2033 void
2034 df_dump_bottom (basic_block bb, FILE *file)
2036 int i;
2038 if (!df || !file)
2039 return;
2041 for (i = 0; i < df->num_problems_defined; i++)
2043 struct dataflow *dflow = df->problems_in_order[i];
2044 if (dflow->computed)
2046 df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
2047 if (bbfun)
2048 bbfun (bb, file);
2054 static void
2055 df_ref_dump (df_ref ref, FILE *file)
2057 fprintf (file, "%c%d(%d)",
2058 DF_REF_REG_DEF_P (ref)
2059 ? 'd'
2060 : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2061 DF_REF_ID (ref),
2062 DF_REF_REGNO (ref));
2065 void
2066 df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
2068 fprintf (file, "{ ");
2069 while (*ref_rec)
2071 df_ref ref = *ref_rec;
2072 df_ref_dump (ref, file);
2073 if (follow_chain)
2074 df_chain_dump (DF_REF_CHAIN (ref), file);
2075 ref_rec++;
2077 fprintf (file, "}");
2081 /* Dump either a ref-def or reg-use chain. */
2083 void
2084 df_regs_chain_dump (df_ref ref, FILE *file)
2086 fprintf (file, "{ ");
2087 while (ref)
2089 df_ref_dump (ref, file);
2090 ref = DF_REF_NEXT_REG (ref);
2092 fprintf (file, "}");
2096 static void
2097 df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
2099 while (*mws)
2101 fprintf (file, "mw %c r[%d..%d]\n",
2102 (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
2103 (*mws)->start_regno, (*mws)->end_regno);
2104 mws++;
2109 static void
2110 df_insn_uid_debug (unsigned int uid,
2111 bool follow_chain, FILE *file)
2113 fprintf (file, "insn %d luid %d",
2114 uid, DF_INSN_UID_LUID (uid));
2116 if (DF_INSN_UID_DEFS (uid))
2118 fprintf (file, " defs ");
2119 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2122 if (DF_INSN_UID_USES (uid))
2124 fprintf (file, " uses ");
2125 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2128 if (DF_INSN_UID_EQ_USES (uid))
2130 fprintf (file, " eq uses ");
2131 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2134 if (DF_INSN_UID_MWS (uid))
2136 fprintf (file, " mws ");
2137 df_mws_dump (DF_INSN_UID_MWS (uid), file);
2139 fprintf (file, "\n");
2143 DEBUG_FUNCTION void
2144 df_insn_debug (rtx insn, bool follow_chain, FILE *file)
2146 df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2149 DEBUG_FUNCTION void
2150 df_insn_debug_regno (rtx insn, FILE *file)
2152 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2154 fprintf (file, "insn %d bb %d luid %d defs ",
2155 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2156 DF_INSN_INFO_LUID (insn_info));
2157 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2159 fprintf (file, " uses ");
2160 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2162 fprintf (file, " eq_uses ");
2163 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2164 fprintf (file, "\n");
2167 DEBUG_FUNCTION void
2168 df_regno_debug (unsigned int regno, FILE *file)
2170 fprintf (file, "reg %d defs ", regno);
2171 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2172 fprintf (file, " uses ");
2173 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2174 fprintf (file, " eq_uses ");
2175 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2176 fprintf (file, "\n");
2180 DEBUG_FUNCTION void
2181 df_ref_debug (df_ref ref, FILE *file)
2183 fprintf (file, "%c%d ",
2184 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2185 DF_REF_ID (ref));
2186 fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ",
2187 DF_REF_REGNO (ref),
2188 DF_REF_BBNO (ref),
2189 DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2190 DF_REF_FLAGS (ref),
2191 DF_REF_TYPE (ref));
2192 if (DF_REF_LOC (ref))
2194 if (flag_dump_noaddr)
2195 fprintf (file, "loc #(#) chain ");
2196 else
2197 fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2198 (void *)*DF_REF_LOC (ref));
2200 else
2201 fprintf (file, "chain ");
2202 df_chain_dump (DF_REF_CHAIN (ref), file);
2203 fprintf (file, "\n");
2206 /* Functions for debugging from GDB. */
2208 DEBUG_FUNCTION void
2209 debug_df_insn (rtx insn)
2211 df_insn_debug (insn, true, stderr);
2212 debug_rtx (insn);
2216 DEBUG_FUNCTION void
2217 debug_df_reg (rtx reg)
2219 df_regno_debug (REGNO (reg), stderr);
2223 DEBUG_FUNCTION void
2224 debug_df_regno (unsigned int regno)
2226 df_regno_debug (regno, stderr);
2230 DEBUG_FUNCTION void
2231 debug_df_ref (df_ref ref)
2233 df_ref_debug (ref, stderr);
2237 DEBUG_FUNCTION void
2238 debug_df_defno (unsigned int defno)
2240 df_ref_debug (DF_DEFS_GET (defno), stderr);
2244 DEBUG_FUNCTION void
2245 debug_df_useno (unsigned int defno)
2247 df_ref_debug (DF_USES_GET (defno), stderr);
2251 DEBUG_FUNCTION void
2252 debug_df_chain (struct df_link *link)
2254 df_chain_dump (link, stderr);
2255 fputc ('\n', stderr);