Daily bump.
[official-gcc.git] / gcc / df-core.c
blob67040a10d3983ce3dc73f1f06e99d2a10f18ee73
1 /* Allocation for dataflow support routines.
2 Copyright (C) 1999-2015 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
25 OVERVIEW:
27 The files in this collection (df*.c,df.h) provide a general framework
28 for solving dataflow problems. The global dataflow is performed using
29 a good implementation of iterative dataflow analysis.
31 The file df-problems.c provides problem instance for the most common
32 dataflow problems: reaching defs, upward exposed uses, live variables,
33 uninitialized variables, def-use chains, and use-def chains. However,
34 the interface allows other dataflow problems to be defined as well.
36 Dataflow analysis is available in most of the rtl backend (the parts
37 between pass_df_initialize and pass_df_finish). It is quite likely
38 that these boundaries will be expanded in the future. The only
39 requirement is that there be a correct control flow graph.
41 There are three variations of the live variable problem that are
42 available whenever dataflow is available. The LR problem finds the
43 areas that can reach a use of a variable, the UR problems finds the
44 areas that can be reached from a definition of a variable. The LIVE
45 problem finds the intersection of these two areas.
47 There are several optional problems. These can be enabled when they
48 are needed and disabled when they are not needed.
50 Dataflow problems are generally solved in three layers. The bottom
51 layer is called scanning where a data structure is built for each rtl
52 insn that describes the set of defs and uses of that insn. Scanning
53 is generally kept up to date, i.e. as the insns changes, the scanned
54 version of that insn changes also. There are various mechanisms for
55 making this happen and are described in the INCREMENTAL SCANNING
56 section.
58 In the middle layer, basic blocks are scanned to produce transfer
59 functions which describe the effects of that block on the global
60 dataflow solution. The transfer functions are only rebuilt if the
61 some instruction within the block has changed.
63 The top layer is the dataflow solution itself. The dataflow solution
64 is computed by using an efficient iterative solver and the transfer
65 functions. The dataflow solution must be recomputed whenever the
66 control changes or if one of the transfer function changes.
69 USAGE:
71 Here is an example of using the dataflow routines.
73 df_[chain,live,note,rd]_add_problem (flags);
75 df_set_blocks (blocks);
77 df_analyze ();
79 df_dump (stderr);
81 df_finish_pass (false);
83 DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an
84 instance to struct df_problem, to the set of problems solved in this
85 instance of df. All calls to add a problem for a given instance of df
86 must occur before the first call to DF_ANALYZE.
88 Problems can be dependent on other problems. For instance, solving
89 def-use or use-def chains is dependent on solving reaching
90 definitions. As long as these dependencies are listed in the problem
91 definition, the order of adding the problems is not material.
92 Otherwise, the problems will be solved in the order of calls to
93 df_add_problem. Note that it is not necessary to have a problem. In
94 that case, df will just be used to do the scanning.
98 DF_SET_BLOCKS is an optional call used to define a region of the
99 function on which the analysis will be performed. The normal case is
100 to analyze the entire function and no call to df_set_blocks is made.
101 DF_SET_BLOCKS only effects the blocks that are effected when computing
102 the transfer functions and final solution. The insn level information
103 is always kept up to date.
105 When a subset is given, the analysis behaves as if the function only
106 contains those blocks and any edges that occur directly between the
107 blocks in the set. Care should be taken to call df_set_blocks right
108 before the call to analyze in order to eliminate the possibility that
109 optimizations that reorder blocks invalidate the bitvector.
111 DF_ANALYZE causes all of the defined problems to be (re)solved. When
112 DF_ANALYZE is completes, the IN and OUT sets for each basic block
113 contain the computer information. The DF_*_BB_INFO macros can be used
114 to access these bitvectors. All deferred rescannings are down before
115 the transfer functions are recomputed.
117 DF_DUMP can then be called to dump the information produce to some
118 file. This calls DF_DUMP_START, to print the information that is not
119 basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM
120 for each block to print the basic specific information. These parts
121 can all be called separately as part of a larger dump function.
124 DF_FINISH_PASS causes df_remove_problem to be called on all of the
125 optional problems. It also causes any insns whose scanning has been
126 deferred to be rescanned as well as clears all of the changeable flags.
127 Setting the pass manager TODO_df_finish flag causes this function to
128 be run. However, the pass manager will call df_finish_pass AFTER the
129 pass dumping has been done, so if you want to see the results of the
130 optional problems in the pass dumps, use the TODO flag rather than
131 calling the function yourself.
133 INCREMENTAL SCANNING
135 There are four ways of doing the incremental scanning:
137 1) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,
138 df_bb_delete, df_insn_change_bb have been added to most of
139 the low level service functions that maintain the cfg and change
140 rtl. Calling and of these routines many cause some number of insns
141 to be rescanned.
143 For most modern rtl passes, this is certainly the easiest way to
144 manage rescanning the insns. This technique also has the advantage
145 that the scanning information is always correct and can be relied
146 upon even after changes have been made to the instructions. This
147 technique is contra indicated in several cases:
149 a) If def-use chains OR use-def chains (but not both) are built,
150 using this is SIMPLY WRONG. The problem is that when a ref is
151 deleted that is the target of an edge, there is not enough
152 information to efficiently find the source of the edge and
153 delete the edge. This leaves a dangling reference that may
154 cause problems.
156 b) If def-use chains AND use-def chains are built, this may
157 produce unexpected results. The problem is that the incremental
158 scanning of an insn does not know how to repair the chains that
159 point into an insn when the insn changes. So the incremental
160 scanning just deletes the chains that enter and exit the insn
161 being changed. The dangling reference issue in (a) is not a
162 problem here, but if the pass is depending on the chains being
163 maintained after insns have been modified, this technique will
164 not do the correct thing.
166 c) If the pass modifies insns several times, this incremental
167 updating may be expensive.
169 d) If the pass modifies all of the insns, as does register
170 allocation, it is simply better to rescan the entire function.
172 2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
173 df_insn_delete do not immediately change the insn but instead make
174 a note that the insn needs to be rescanned. The next call to
175 df_analyze, df_finish_pass, or df_process_deferred_rescans will
176 cause all of the pending rescans to be processed.
178 This is the technique of choice if either 1a, 1b, or 1c are issues
179 in the pass. In the case of 1a or 1b, a call to df_finish_pass
180 (either manually or via TODO_df_finish) should be made before the
181 next call to df_analyze or df_process_deferred_rescans.
183 This mode is also used by a few passes that still rely on note_uses,
184 note_stores and rtx iterators instead of using the DF data. This
185 can be said to fall under case 1c.
187 To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
188 (This mode can be cleared by calling df_clear_flags
189 (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
190 be rescanned.
192 3) Total rescanning - In this mode the rescanning is disabled.
193 Only when insns are deleted is the df information associated with
194 it also deleted. At the end of the pass, a call must be made to
195 df_insn_rescan_all. This method is used by the register allocator
196 since it generally changes each insn multiple times (once for each ref)
197 and does not need to make use of the updated scanning information.
199 4) Do it yourself - In this mechanism, the pass updates the insns
200 itself using the low level df primitives. Currently no pass does
201 this, but it has the advantage that it is quite efficient given
202 that the pass generally has exact knowledge of what it is changing.
204 DATA STRUCTURES
206 Scanning produces a `struct df_ref' data structure (ref) is allocated
207 for every register reference (def or use) and this records the insn
208 and bb the ref is found within. The refs are linked together in
209 chains of uses and defs for each insn and for each register. Each ref
210 also has a chain field that links all the use refs for a def or all
211 the def refs for a use. This is used to create use-def or def-use
212 chains.
214 Different optimizations have different needs. Ultimately, only
215 register allocation and schedulers should be using the bitmaps
216 produced for the live register and uninitialized register problems.
217 The rest of the backend should be upgraded to using and maintaining
218 the linked information such as def use or use def chains.
221 PHILOSOPHY:
223 While incremental bitmaps are not worthwhile to maintain, incremental
224 chains may be perfectly reasonable. The fastest way to build chains
225 from scratch or after significant modifications is to build reaching
226 definitions (RD) and build the chains from this.
228 However, general algorithms for maintaining use-def or def-use chains
229 are not practical. The amount of work to recompute the chain any
230 chain after an arbitrary change is large. However, with a modest
231 amount of work it is generally possible to have the application that
232 uses the chains keep them up to date. The high level knowledge of
233 what is really happening is essential to crafting efficient
234 incremental algorithms.
236 As for the bit vector problems, there is no interface to give a set of
237 blocks over with to resolve the iteration. In general, restarting a
238 dataflow iteration is difficult and expensive. Again, the best way to
239 keep the dataflow information up to data (if this is really what is
240 needed) it to formulate a problem specific solution.
242 There are fine grained calls for creating and deleting references from
243 instructions in df-scan.c. However, these are not currently connected
244 to the engine that resolves the dataflow equations.
247 DATA STRUCTURES:
249 The basic object is a DF_REF (reference) and this may either be a
250 DEF (definition) or a USE of a register.
252 These are linked into a variety of lists; namely reg-def, reg-use,
253 insn-def, insn-use, def-use, and use-def lists. For example, the
254 reg-def lists contain all the locations that define a given register
255 while the insn-use lists contain all the locations that use a
256 register.
258 Note that the reg-def and reg-use chains are generally short for
259 pseudos and long for the hard registers.
261 ACCESSING INSNS:
263 1) The df insn information is kept in an array of DF_INSN_INFO objects.
264 The array is indexed by insn uid, and every DF_REF points to the
265 DF_INSN_INFO object of the insn that contains the reference.
267 2) Each insn has three sets of refs, which are linked into one of three
268 lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS,
269 DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list
270 (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or
271 DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the
272 DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
273 The latter list are the list of references in REG_EQUAL or REG_EQUIV
274 notes. These macros produce a ref (or NULL), the rest of the list
275 can be obtained by traversal of the NEXT_REF field (accessed by the
276 DF_REF_NEXT_REF macro.) There is no significance to the ordering of
277 the uses or refs in an instruction.
279 3) Each insn has a logical uid field (LUID) which is stored in the
280 DF_INSN_INFO object for the insn. The LUID field is accessed by
281 the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros.
282 When properly set, the LUID is an integer that numbers each insn in
283 the basic block, in order from the start of the block.
284 The numbers are only correct after a call to df_analyze. They will
285 rot after insns are added deleted or moved round.
287 ACCESSING REFS:
289 There are 4 ways to obtain access to refs:
291 1) References are divided into two categories, REAL and ARTIFICIAL.
293 REAL refs are associated with instructions.
295 ARTIFICIAL refs are associated with basic blocks. The heads of
296 these lists can be accessed by calling df_get_artificial_defs or
297 df_get_artificial_uses for the particular basic block.
299 Artificial defs and uses occur both at the beginning and ends of blocks.
301 For blocks that area at the destination of eh edges, the
302 artificial uses and defs occur at the beginning. The defs relate
303 to the registers specified in EH_RETURN_DATA_REGNO and the uses
304 relate to the registers specified in ED_USES. Logically these
305 defs and uses should really occur along the eh edge, but there is
306 no convenient way to do this. Artificial edges that occur at the
307 beginning of the block have the DF_REF_AT_TOP flag set.
309 Artificial uses occur at the end of all blocks. These arise from
310 the hard registers that are always live, such as the stack
311 register and are put there to keep the code from forgetting about
312 them.
314 Artificial defs occur at the end of the entry block. These arise
315 from registers that are live at entry to the function.
317 2) There are three types of refs: defs, uses and eq_uses. (Eq_uses are
318 uses that appear inside a REG_EQUAL or REG_EQUIV note.)
320 All of the eq_uses, uses and defs associated with each pseudo or
321 hard register may be linked in a bidirectional chain. These are
322 called reg-use or reg_def chains. If the changeable flag
323 DF_EQ_NOTES is set when the chains are built, the eq_uses will be
324 treated like uses. If it is not set they are ignored.
326 The first use, eq_use or def for a register can be obtained using
327 the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN
328 macros. Subsequent uses for the same regno can be obtained by
329 following the next_reg field of the ref. The number of elements in
330 each of the chains can be found by using the DF_REG_USE_COUNT,
331 DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.
333 In previous versions of this code, these chains were ordered. It
334 has not been practical to continue this practice.
336 3) If def-use or use-def chains are built, these can be traversed to
337 get to other refs. If the flag DF_EQ_NOTES has been set, the chains
338 include the eq_uses. Otherwise these are ignored when building the
339 chains.
341 4) An array of all of the uses (and an array of all of the defs) can
342 be built. These arrays are indexed by the value in the id
343 structure. These arrays are only lazily kept up to date, and that
344 process can be expensive. To have these arrays built, call
345 df_reorganize_defs or df_reorganize_uses. If the flag DF_EQ_NOTES
346 has been set the array will contain the eq_uses. Otherwise these
347 are ignored when building the array and assigning the ids. Note
348 that the values in the id field of a ref may change across calls to
349 df_analyze or df_reorganize_defs or df_reorganize_uses.
351 If the only use of this array is to find all of the refs, it is
352 better to traverse all of the registers and then traverse all of
353 reg-use or reg-def chains.
355 NOTES:
357 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
358 both a use and a def. These are both marked read/write to show that they
359 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
360 will generate a use of reg 42 followed by a def of reg 42 (both marked
361 read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
362 generates a use of reg 41 then a def of reg 41 (both marked read/write),
363 even though reg 41 is decremented before it is used for the memory
364 address in this second example.
366 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
367 for which the number of word_mode units covered by the outer mode is
368 smaller than that covered by the inner mode, invokes a read-modify-write
369 operation. We generate both a use and a def and again mark them
370 read/write.
372 Paradoxical subreg writes do not leave a trace of the old content, so they
373 are write-only operations.
377 #include "config.h"
378 #include "system.h"
379 #include "coretypes.h"
380 #include "tm.h"
381 #include "rtl.h"
382 #include "tm_p.h"
383 #include "insn-config.h"
384 #include "recog.h"
385 #include "hashtab.h"
386 #include "hash-set.h"
387 #include "vec.h"
388 #include "machmode.h"
389 #include "hard-reg-set.h"
390 #include "input.h"
391 #include "function.h"
392 #include "regs.h"
393 #include "alloc-pool.h"
394 #include "flags.h"
395 #include "predict.h"
396 #include "dominance.h"
397 #include "cfg.h"
398 #include "cfganal.h"
399 #include "basic-block.h"
400 #include "sbitmap.h"
401 #include "bitmap.h"
402 #include "df.h"
403 #include "tree-pass.h"
404 #include "params.h"
405 #include "cfgloop.h"
407 static void *df_get_bb_info (struct dataflow *, unsigned int);
408 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
409 static void df_clear_bb_info (struct dataflow *, unsigned int);
410 #ifdef DF_DEBUG_CFG
411 static void df_set_clean_cfg (void);
412 #endif
414 /* The obstack on which regsets are allocated. */
415 struct bitmap_obstack reg_obstack;
417 /* An obstack for bitmap not related to specific dataflow problems.
418 This obstack should e.g. be used for bitmaps with a short life time
419 such as temporary bitmaps. */
421 bitmap_obstack df_bitmap_obstack;
424 /*----------------------------------------------------------------------------
425 Functions to create, destroy and manipulate an instance of df.
426 ----------------------------------------------------------------------------*/
428 struct df_d *df;
430 /* Add PROBLEM (and any dependent problems) to the DF instance. */
432 void
433 df_add_problem (struct df_problem *problem)
435 struct dataflow *dflow;
436 int i;
438 /* First try to add the dependent problem. */
439 if (problem->dependent_problem)
440 df_add_problem (problem->dependent_problem);
442 /* Check to see if this problem has already been defined. If it
443 has, just return that instance, if not, add it to the end of the
444 vector. */
445 dflow = df->problems_by_index[problem->id];
446 if (dflow)
447 return;
449 /* Make a new one and add it to the end. */
450 dflow = XCNEW (struct dataflow);
451 dflow->problem = problem;
452 dflow->computed = false;
453 dflow->solutions_dirty = true;
454 df->problems_by_index[dflow->problem->id] = dflow;
456 /* Keep the defined problems ordered by index. This solves the
457 problem that RI will use the information from UREC if UREC has
458 been defined, or from LIVE if LIVE is defined and otherwise LR.
459 However for this to work, the computation of RI must be pushed
460 after which ever of those problems is defined, but we do not
461 require any of those except for LR to have actually been
462 defined. */
463 df->num_problems_defined++;
464 for (i = df->num_problems_defined - 2; i >= 0; i--)
466 if (problem->id < df->problems_in_order[i]->problem->id)
467 df->problems_in_order[i+1] = df->problems_in_order[i];
468 else
470 df->problems_in_order[i+1] = dflow;
471 return;
474 df->problems_in_order[0] = dflow;
478 /* Set the MASK flags in the DFLOW problem. The old flags are
479 returned. If a flag is not allowed to be changed this will fail if
480 checking is enabled. */
482 df_set_flags (int changeable_flags)
484 int old_flags = df->changeable_flags;
485 df->changeable_flags |= changeable_flags;
486 return old_flags;
490 /* Clear the MASK flags in the DFLOW problem. The old flags are
491 returned. If a flag is not allowed to be changed this will fail if
492 checking is enabled. */
494 df_clear_flags (int changeable_flags)
496 int old_flags = df->changeable_flags;
497 df->changeable_flags &= ~changeable_flags;
498 return old_flags;
502 /* Set the blocks that are to be considered for analysis. If this is
503 not called or is called with null, the entire function in
504 analyzed. */
506 void
507 df_set_blocks (bitmap blocks)
509 if (blocks)
511 if (dump_file)
512 bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
513 if (df->blocks_to_analyze)
515 /* This block is called to change the focus from one subset
516 to another. */
517 int p;
518 bitmap_head diff;
519 bitmap_initialize (&diff, &df_bitmap_obstack);
520 bitmap_and_compl (&diff, df->blocks_to_analyze, blocks);
521 for (p = 0; p < df->num_problems_defined; p++)
523 struct dataflow *dflow = df->problems_in_order[p];
524 if (dflow->optional_p && dflow->problem->reset_fun)
525 dflow->problem->reset_fun (df->blocks_to_analyze);
526 else if (dflow->problem->free_blocks_on_set_blocks)
528 bitmap_iterator bi;
529 unsigned int bb_index;
531 EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
533 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
534 if (bb)
536 void *bb_info = df_get_bb_info (dflow, bb_index);
537 dflow->problem->free_bb_fun (bb, bb_info);
538 df_clear_bb_info (dflow, bb_index);
544 bitmap_clear (&diff);
546 else
548 /* This block of code is executed to change the focus from
549 the entire function to a subset. */
550 bitmap_head blocks_to_reset;
551 bool initialized = false;
552 int p;
553 for (p = 0; p < df->num_problems_defined; p++)
555 struct dataflow *dflow = df->problems_in_order[p];
556 if (dflow->optional_p && dflow->problem->reset_fun)
558 if (!initialized)
560 basic_block bb;
561 bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack);
562 FOR_ALL_BB_FN (bb, cfun)
564 bitmap_set_bit (&blocks_to_reset, bb->index);
567 dflow->problem->reset_fun (&blocks_to_reset);
570 if (initialized)
571 bitmap_clear (&blocks_to_reset);
573 df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
575 bitmap_copy (df->blocks_to_analyze, blocks);
576 df->analyze_subset = true;
578 else
580 /* This block is executed to reset the focus to the entire
581 function. */
582 if (dump_file)
583 fprintf (dump_file, "clearing blocks_to_analyze\n");
584 if (df->blocks_to_analyze)
586 BITMAP_FREE (df->blocks_to_analyze);
587 df->blocks_to_analyze = NULL;
589 df->analyze_subset = false;
592 /* Setting the blocks causes the refs to be unorganized since only
593 the refs in the blocks are seen. */
594 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
595 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
596 df_mark_solutions_dirty ();
600 /* Delete a DFLOW problem (and any problems that depend on this
601 problem). */
603 void
604 df_remove_problem (struct dataflow *dflow)
606 struct df_problem *problem;
607 int i;
609 if (!dflow)
610 return;
612 problem = dflow->problem;
613 gcc_assert (problem->remove_problem_fun);
615 /* Delete any problems that depended on this problem first. */
616 for (i = 0; i < df->num_problems_defined; i++)
617 if (df->problems_in_order[i]->problem->dependent_problem == problem)
618 df_remove_problem (df->problems_in_order[i]);
620 /* Now remove this problem. */
621 for (i = 0; i < df->num_problems_defined; i++)
622 if (df->problems_in_order[i] == dflow)
624 int j;
625 for (j = i + 1; j < df->num_problems_defined; j++)
626 df->problems_in_order[j-1] = df->problems_in_order[j];
627 df->problems_in_order[j-1] = NULL;
628 df->num_problems_defined--;
629 break;
632 (problem->remove_problem_fun) ();
633 df->problems_by_index[problem->id] = NULL;
637 /* Remove all of the problems that are not permanent. Scanning, LR
638 and (at -O2 or higher) LIVE are permanent, the rest are removable.
639 Also clear all of the changeable_flags. */
641 void
642 df_finish_pass (bool verify ATTRIBUTE_UNUSED)
644 int i;
646 #ifdef ENABLE_DF_CHECKING
647 int saved_flags;
648 #endif
650 if (!df)
651 return;
653 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
654 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
656 #ifdef ENABLE_DF_CHECKING
657 saved_flags = df->changeable_flags;
658 #endif
660 /* We iterate over problems by index as each problem removed will
661 lead to problems_in_order to be reordered. */
662 for (i = 0; i < DF_LAST_PROBLEM_PLUS1; i++)
664 struct dataflow *dflow = df->problems_by_index[i];
666 if (dflow && dflow->optional_p)
667 df_remove_problem (dflow);
670 /* Clear all of the flags. */
671 df->changeable_flags = 0;
672 df_process_deferred_rescans ();
674 /* Set the focus back to the whole function. */
675 if (df->blocks_to_analyze)
677 BITMAP_FREE (df->blocks_to_analyze);
678 df->blocks_to_analyze = NULL;
679 df_mark_solutions_dirty ();
680 df->analyze_subset = false;
683 #ifdef ENABLE_DF_CHECKING
684 /* Verification will fail in DF_NO_INSN_RESCAN. */
685 if (!(saved_flags & DF_NO_INSN_RESCAN))
687 df_lr_verify_transfer_functions ();
688 if (df_live)
689 df_live_verify_transfer_functions ();
692 #ifdef DF_DEBUG_CFG
693 df_set_clean_cfg ();
694 #endif
695 #endif
697 #ifdef ENABLE_CHECKING
698 if (verify)
699 df->changeable_flags |= DF_VERIFY_SCHEDULED;
700 #endif
704 /* Set up the dataflow instance for the entire back end. */
706 static unsigned int
707 rest_of_handle_df_initialize (void)
709 gcc_assert (!df);
710 df = XCNEW (struct df_d);
711 df->changeable_flags = 0;
713 bitmap_obstack_initialize (&df_bitmap_obstack);
715 /* Set this to a conservative value. Stack_ptr_mod will compute it
716 correctly later. */
717 crtl->sp_is_unchanging = 0;
719 df_scan_add_problem ();
720 df_scan_alloc (NULL);
722 /* These three problems are permanent. */
723 df_lr_add_problem ();
724 if (optimize > 1)
725 df_live_add_problem ();
727 df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
728 df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun));
729 df->n_blocks = post_order_compute (df->postorder, true, true);
730 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
731 gcc_assert (df->n_blocks == df->n_blocks_inverted);
733 df->hard_regs_live_count = XCNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
735 df_hard_reg_init ();
736 /* After reload, some ports add certain bits to regs_ever_live so
737 this cannot be reset. */
738 df_compute_regs_ever_live (true);
739 df_scan_blocks ();
740 df_compute_regs_ever_live (false);
741 return 0;
745 namespace {
747 const pass_data pass_data_df_initialize_opt =
749 RTL_PASS, /* type */
750 "dfinit", /* name */
751 OPTGROUP_NONE, /* optinfo_flags */
752 TV_DF_SCAN, /* tv_id */
753 0, /* properties_required */
754 0, /* properties_provided */
755 0, /* properties_destroyed */
756 0, /* todo_flags_start */
757 0, /* todo_flags_finish */
760 class pass_df_initialize_opt : public rtl_opt_pass
762 public:
763 pass_df_initialize_opt (gcc::context *ctxt)
764 : rtl_opt_pass (pass_data_df_initialize_opt, ctxt)
767 /* opt_pass methods: */
768 virtual bool gate (function *) { return optimize > 0; }
769 virtual unsigned int execute (function *)
771 return rest_of_handle_df_initialize ();
774 }; // class pass_df_initialize_opt
776 } // anon namespace
778 rtl_opt_pass *
779 make_pass_df_initialize_opt (gcc::context *ctxt)
781 return new pass_df_initialize_opt (ctxt);
785 namespace {
787 const pass_data pass_data_df_initialize_no_opt =
789 RTL_PASS, /* type */
790 "no-opt dfinit", /* name */
791 OPTGROUP_NONE, /* optinfo_flags */
792 TV_DF_SCAN, /* tv_id */
793 0, /* properties_required */
794 0, /* properties_provided */
795 0, /* properties_destroyed */
796 0, /* todo_flags_start */
797 0, /* todo_flags_finish */
800 class pass_df_initialize_no_opt : public rtl_opt_pass
802 public:
803 pass_df_initialize_no_opt (gcc::context *ctxt)
804 : rtl_opt_pass (pass_data_df_initialize_no_opt, ctxt)
807 /* opt_pass methods: */
808 virtual bool gate (function *) { return optimize == 0; }
809 virtual unsigned int execute (function *)
811 return rest_of_handle_df_initialize ();
814 }; // class pass_df_initialize_no_opt
816 } // anon namespace
818 rtl_opt_pass *
819 make_pass_df_initialize_no_opt (gcc::context *ctxt)
821 return new pass_df_initialize_no_opt (ctxt);
825 /* Free all the dataflow info and the DF structure. This should be
826 called from the df_finish macro which also NULLs the parm. */
828 static unsigned int
829 rest_of_handle_df_finish (void)
831 int i;
833 gcc_assert (df);
835 for (i = 0; i < df->num_problems_defined; i++)
837 struct dataflow *dflow = df->problems_in_order[i];
838 dflow->problem->free_fun ();
841 free (df->postorder);
842 free (df->postorder_inverted);
843 free (df->hard_regs_live_count);
844 free (df);
845 df = NULL;
847 bitmap_obstack_release (&df_bitmap_obstack);
848 return 0;
852 namespace {
854 const pass_data pass_data_df_finish =
856 RTL_PASS, /* type */
857 "dfinish", /* name */
858 OPTGROUP_NONE, /* optinfo_flags */
859 TV_NONE, /* tv_id */
860 0, /* properties_required */
861 0, /* properties_provided */
862 0, /* properties_destroyed */
863 0, /* todo_flags_start */
864 0, /* todo_flags_finish */
867 class pass_df_finish : public rtl_opt_pass
869 public:
870 pass_df_finish (gcc::context *ctxt)
871 : rtl_opt_pass (pass_data_df_finish, ctxt)
874 /* opt_pass methods: */
875 virtual unsigned int execute (function *)
877 return rest_of_handle_df_finish ();
880 }; // class pass_df_finish
882 } // anon namespace
884 rtl_opt_pass *
885 make_pass_df_finish (gcc::context *ctxt)
887 return new pass_df_finish (ctxt);
894 /*----------------------------------------------------------------------------
895 The general data flow analysis engine.
896 ----------------------------------------------------------------------------*/
898 /* Return time BB when it was visited for last time. */
899 #define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
901 /* Helper function for df_worklist_dataflow.
902 Propagate the dataflow forward.
903 Given a BB_INDEX, do the dataflow propagation
904 and set bits on for successors in PENDING
905 if the out set of the dataflow has changed.
907 AGE specify time when BB was visited last time.
908 AGE of 0 means we are visiting for first time and need to
909 compute transfer function to initialize datastructures.
910 Otherwise we re-do transfer function only if something change
911 while computing confluence functions.
912 We need to compute confluence only of basic block that are younger
913 then last visit of the BB.
915 Return true if BB info has changed. This is always the case
916 in the first visit. */
918 static bool
919 df_worklist_propagate_forward (struct dataflow *dataflow,
920 unsigned bb_index,
921 unsigned *bbindex_to_postorder,
922 bitmap pending,
923 sbitmap considered,
924 ptrdiff_t age)
926 edge e;
927 edge_iterator ei;
928 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
929 bool changed = !age;
931 /* Calculate <conf_op> of incoming edges. */
932 if (EDGE_COUNT (bb->preds) > 0)
933 FOR_EACH_EDGE (e, ei, bb->preds)
935 if (age <= BB_LAST_CHANGE_AGE (e->src)
936 && bitmap_bit_p (considered, e->src->index))
937 changed |= dataflow->problem->con_fun_n (e);
939 else if (dataflow->problem->con_fun_0)
940 dataflow->problem->con_fun_0 (bb);
942 if (changed
943 && dataflow->problem->trans_fun (bb_index))
945 /* The out set of this block has changed.
946 Propagate to the outgoing blocks. */
947 FOR_EACH_EDGE (e, ei, bb->succs)
949 unsigned ob_index = e->dest->index;
951 if (bitmap_bit_p (considered, ob_index))
952 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
954 return true;
956 return false;
960 /* Helper function for df_worklist_dataflow.
961 Propagate the dataflow backward. */
963 static bool
964 df_worklist_propagate_backward (struct dataflow *dataflow,
965 unsigned bb_index,
966 unsigned *bbindex_to_postorder,
967 bitmap pending,
968 sbitmap considered,
969 ptrdiff_t age)
971 edge e;
972 edge_iterator ei;
973 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
974 bool changed = !age;
976 /* Calculate <conf_op> of incoming edges. */
977 if (EDGE_COUNT (bb->succs) > 0)
978 FOR_EACH_EDGE (e, ei, bb->succs)
980 if (age <= BB_LAST_CHANGE_AGE (e->dest)
981 && bitmap_bit_p (considered, e->dest->index))
982 changed |= dataflow->problem->con_fun_n (e);
984 else if (dataflow->problem->con_fun_0)
985 dataflow->problem->con_fun_0 (bb);
987 if (changed
988 && dataflow->problem->trans_fun (bb_index))
990 /* The out set of this block has changed.
991 Propagate to the outgoing blocks. */
992 FOR_EACH_EDGE (e, ei, bb->preds)
994 unsigned ob_index = e->src->index;
996 if (bitmap_bit_p (considered, ob_index))
997 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
999 return true;
1001 return false;
1004 /* Main dataflow solver loop.
1006 DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
1007 need to visit.
1008 BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
1009 BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder position.
1010 PENDING will be freed.
1012 The worklists are bitmaps indexed by postorder positions.
1014 The function implements standard algorithm for dataflow solving with two
1015 worklists (we are processing WORKLIST and storing new BBs to visit in
1016 PENDING).
1018 As an optimization we maintain ages when BB was changed (stored in bb->aux)
1019 and when it was last visited (stored in last_visit_age). This avoids need
1020 to re-do confluence function for edges to basic blocks whose source
1021 did not change since destination was visited last time. */
1023 static void
1024 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
1025 bitmap pending,
1026 sbitmap considered,
1027 int *blocks_in_postorder,
1028 unsigned *bbindex_to_postorder,
1029 int n_blocks)
1031 enum df_flow_dir dir = dataflow->problem->dir;
1032 int dcount = 0;
1033 bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
1034 int age = 0;
1035 bool changed;
1036 vec<int> last_visit_age = vNULL;
1037 int prev_age;
1038 basic_block bb;
1039 int i;
1041 last_visit_age.safe_grow_cleared (n_blocks);
1043 /* Double-queueing. Worklist is for the current iteration,
1044 and pending is for the next. */
1045 while (!bitmap_empty_p (pending))
1047 bitmap_iterator bi;
1048 unsigned int index;
1050 /* Swap pending and worklist. */
1051 bitmap temp = worklist;
1052 worklist = pending;
1053 pending = temp;
1055 EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
1057 unsigned bb_index;
1058 dcount++;
1060 bitmap_clear_bit (pending, index);
1061 bb_index = blocks_in_postorder[index];
1062 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1063 prev_age = last_visit_age[index];
1064 if (dir == DF_FORWARD)
1065 changed = df_worklist_propagate_forward (dataflow, bb_index,
1066 bbindex_to_postorder,
1067 pending, considered,
1068 prev_age);
1069 else
1070 changed = df_worklist_propagate_backward (dataflow, bb_index,
1071 bbindex_to_postorder,
1072 pending, considered,
1073 prev_age);
1074 last_visit_age[index] = ++age;
1075 if (changed)
1076 bb->aux = (void *)(ptrdiff_t)age;
1078 bitmap_clear (worklist);
1080 for (i = 0; i < n_blocks; i++)
1081 BASIC_BLOCK_FOR_FN (cfun, blocks_in_postorder[i])->aux = NULL;
1083 BITMAP_FREE (worklist);
1084 BITMAP_FREE (pending);
1085 last_visit_age.release ();
1087 /* Dump statistics. */
1088 if (dump_file)
1089 fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
1090 "n_basic_blocks %d n_edges %d"
1091 " count %d (%5.2g)\n",
1092 n_basic_blocks_for_fn (cfun), n_edges_for_fn (cfun),
1093 dcount, dcount / (float)n_basic_blocks_for_fn (cfun));
1096 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
1097 with "n"-th bit representing the n-th block in the reverse-postorder order.
1098 The solver is a double-queue algorithm similar to the "double stack" solver
1099 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1100 The only significant difference is that the worklist in this implementation
1101 is always sorted in RPO of the CFG visiting direction. */
1103 void
1104 df_worklist_dataflow (struct dataflow *dataflow,
1105 bitmap blocks_to_consider,
1106 int *blocks_in_postorder,
1107 int n_blocks)
1109 bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1110 sbitmap considered = sbitmap_alloc (last_basic_block_for_fn (cfun));
1111 bitmap_iterator bi;
1112 unsigned int *bbindex_to_postorder;
1113 int i;
1114 unsigned int index;
1115 enum df_flow_dir dir = dataflow->problem->dir;
1117 gcc_assert (dir != DF_NONE);
1119 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
1120 bbindex_to_postorder = XNEWVEC (unsigned int,
1121 last_basic_block_for_fn (cfun));
1123 /* Initialize the array to an out-of-bound value. */
1124 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1125 bbindex_to_postorder[i] = last_basic_block_for_fn (cfun);
1127 /* Initialize the considered map. */
1128 bitmap_clear (considered);
1129 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1131 bitmap_set_bit (considered, index);
1134 /* Initialize the mapping of block index to postorder. */
1135 for (i = 0; i < n_blocks; i++)
1137 bbindex_to_postorder[blocks_in_postorder[i]] = i;
1138 /* Add all blocks to the worklist. */
1139 bitmap_set_bit (pending, i);
1142 /* Initialize the problem. */
1143 if (dataflow->problem->init_fun)
1144 dataflow->problem->init_fun (blocks_to_consider);
1146 /* Solve it. */
1147 df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1148 blocks_in_postorder,
1149 bbindex_to_postorder,
1150 n_blocks);
1151 sbitmap_free (considered);
1152 free (bbindex_to_postorder);
1156 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1157 the order of the remaining entries. Returns the length of the resulting
1158 list. */
1160 static unsigned
1161 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1163 unsigned act, last;
1165 for (act = 0, last = 0; act < len; act++)
1166 if (bitmap_bit_p (blocks, list[act]))
1167 list[last++] = list[act];
1169 return last;
1173 /* Execute dataflow analysis on a single dataflow problem.
1175 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1176 examined or will be computed. For calls from DF_ANALYZE, this is
1177 the set of blocks that has been passed to DF_SET_BLOCKS.
1180 void
1181 df_analyze_problem (struct dataflow *dflow,
1182 bitmap blocks_to_consider,
1183 int *postorder, int n_blocks)
1185 timevar_push (dflow->problem->tv_id);
1187 /* (Re)Allocate the datastructures necessary to solve the problem. */
1188 if (dflow->problem->alloc_fun)
1189 dflow->problem->alloc_fun (blocks_to_consider);
1191 #ifdef ENABLE_DF_CHECKING
1192 if (dflow->problem->verify_start_fun)
1193 dflow->problem->verify_start_fun ();
1194 #endif
1196 /* Set up the problem and compute the local information. */
1197 if (dflow->problem->local_compute_fun)
1198 dflow->problem->local_compute_fun (blocks_to_consider);
1200 /* Solve the equations. */
1201 if (dflow->problem->dataflow_fun)
1202 dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1203 postorder, n_blocks);
1205 /* Massage the solution. */
1206 if (dflow->problem->finalize_fun)
1207 dflow->problem->finalize_fun (blocks_to_consider);
1209 #ifdef ENABLE_DF_CHECKING
1210 if (dflow->problem->verify_end_fun)
1211 dflow->problem->verify_end_fun ();
1212 #endif
1214 timevar_pop (dflow->problem->tv_id);
1216 dflow->computed = true;
1220 /* Analyze dataflow info. */
1222 static void
1223 df_analyze_1 (void)
1225 int i;
1227 /* These should be the same. */
1228 gcc_assert (df->n_blocks == df->n_blocks_inverted);
1230 /* We need to do this before the df_verify_all because this is
1231 not kept incrementally up to date. */
1232 df_compute_regs_ever_live (false);
1233 df_process_deferred_rescans ();
1235 if (dump_file)
1236 fprintf (dump_file, "df_analyze called\n");
1238 #ifndef ENABLE_DF_CHECKING
1239 if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1240 #endif
1241 df_verify ();
1243 /* Skip over the DF_SCAN problem. */
1244 for (i = 1; i < df->num_problems_defined; i++)
1246 struct dataflow *dflow = df->problems_in_order[i];
1247 if (dflow->solutions_dirty)
1249 if (dflow->problem->dir == DF_FORWARD)
1250 df_analyze_problem (dflow,
1251 df->blocks_to_analyze,
1252 df->postorder_inverted,
1253 df->n_blocks_inverted);
1254 else
1255 df_analyze_problem (dflow,
1256 df->blocks_to_analyze,
1257 df->postorder,
1258 df->n_blocks);
1262 if (!df->analyze_subset)
1264 BITMAP_FREE (df->blocks_to_analyze);
1265 df->blocks_to_analyze = NULL;
1268 #ifdef DF_DEBUG_CFG
1269 df_set_clean_cfg ();
1270 #endif
1273 /* Analyze dataflow info. */
1275 void
1276 df_analyze (void)
1278 bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1279 int i;
1281 free (df->postorder);
1282 free (df->postorder_inverted);
1283 df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
1284 df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun));
1285 df->n_blocks = post_order_compute (df->postorder, true, true);
1286 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1288 for (i = 0; i < df->n_blocks; i++)
1289 bitmap_set_bit (current_all_blocks, df->postorder[i]);
1291 #ifdef ENABLE_CHECKING
1292 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1293 the ENTRY block. */
1294 for (i = 0; i < df->n_blocks_inverted; i++)
1295 gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1296 #endif
1298 /* Make sure that we have pruned any unreachable blocks from these
1299 sets. */
1300 if (df->analyze_subset)
1302 bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1303 df->n_blocks = df_prune_to_subcfg (df->postorder,
1304 df->n_blocks, df->blocks_to_analyze);
1305 df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1306 df->n_blocks_inverted,
1307 df->blocks_to_analyze);
1308 BITMAP_FREE (current_all_blocks);
1310 else
1312 df->blocks_to_analyze = current_all_blocks;
1313 current_all_blocks = NULL;
1316 df_analyze_1 ();
1319 /* Compute the reverse top sort order of the sub-CFG specified by LOOP.
1320 Returns the number of blocks which is always loop->num_nodes. */
1322 static int
1323 loop_post_order_compute (int *post_order, struct loop *loop)
1325 edge_iterator *stack;
1326 int sp;
1327 int post_order_num = 0;
1328 bitmap visited;
1330 /* Allocate stack for back-tracking up CFG. */
1331 stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
1332 sp = 0;
1334 /* Allocate bitmap to track nodes that have been visited. */
1335 visited = BITMAP_ALLOC (NULL);
1337 /* Push the first edge on to the stack. */
1338 stack[sp++] = ei_start (loop_preheader_edge (loop)->src->succs);
1340 while (sp)
1342 edge_iterator ei;
1343 basic_block src;
1344 basic_block dest;
1346 /* Look at the edge on the top of the stack. */
1347 ei = stack[sp - 1];
1348 src = ei_edge (ei)->src;
1349 dest = ei_edge (ei)->dest;
1351 /* Check if the edge destination has been visited yet and mark it
1352 if not so. */
1353 if (flow_bb_inside_loop_p (loop, dest)
1354 && bitmap_set_bit (visited, dest->index))
1356 if (EDGE_COUNT (dest->succs) > 0)
1357 /* Since the DEST node has been visited for the first
1358 time, check its successors. */
1359 stack[sp++] = ei_start (dest->succs);
1360 else
1361 post_order[post_order_num++] = dest->index;
1363 else
1365 if (ei_one_before_end_p (ei)
1366 && src != loop_preheader_edge (loop)->src)
1367 post_order[post_order_num++] = src->index;
1369 if (!ei_one_before_end_p (ei))
1370 ei_next (&stack[sp - 1]);
1371 else
1372 sp--;
1376 free (stack);
1377 BITMAP_FREE (visited);
1379 return post_order_num;
1382 /* Compute the reverse top sort order of the inverted sub-CFG specified
1383 by LOOP. Returns the number of blocks which is always loop->num_nodes. */
1385 static int
1386 loop_inverted_post_order_compute (int *post_order, struct loop *loop)
1388 basic_block bb;
1389 edge_iterator *stack;
1390 int sp;
1391 int post_order_num = 0;
1392 bitmap visited;
1394 /* Allocate stack for back-tracking up CFG. */
1395 stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
1396 sp = 0;
1398 /* Allocate bitmap to track nodes that have been visited. */
1399 visited = BITMAP_ALLOC (NULL);
1401 /* Put all latches into the initial work list. In theory we'd want
1402 to start from loop exits but then we'd have the special case of
1403 endless loops. It doesn't really matter for DF iteration order and
1404 handling latches last is probably even better. */
1405 stack[sp++] = ei_start (loop->header->preds);
1406 bitmap_set_bit (visited, loop->header->index);
1408 /* The inverted traversal loop. */
1409 while (sp)
1411 edge_iterator ei;
1412 basic_block pred;
1414 /* Look at the edge on the top of the stack. */
1415 ei = stack[sp - 1];
1416 bb = ei_edge (ei)->dest;
1417 pred = ei_edge (ei)->src;
1419 /* Check if the predecessor has been visited yet and mark it
1420 if not so. */
1421 if (flow_bb_inside_loop_p (loop, pred)
1422 && bitmap_set_bit (visited, pred->index))
1424 if (EDGE_COUNT (pred->preds) > 0)
1425 /* Since the predecessor node has been visited for the first
1426 time, check its predecessors. */
1427 stack[sp++] = ei_start (pred->preds);
1428 else
1429 post_order[post_order_num++] = pred->index;
1431 else
1433 if (flow_bb_inside_loop_p (loop, bb)
1434 && ei_one_before_end_p (ei))
1435 post_order[post_order_num++] = bb->index;
1437 if (!ei_one_before_end_p (ei))
1438 ei_next (&stack[sp - 1]);
1439 else
1440 sp--;
1444 free (stack);
1445 BITMAP_FREE (visited);
1446 return post_order_num;
1450 /* Analyze dataflow info for the basic blocks contained in LOOP. */
1452 void
1453 df_analyze_loop (struct loop *loop)
1455 free (df->postorder);
1456 free (df->postorder_inverted);
1458 df->postorder = XNEWVEC (int, loop->num_nodes);
1459 df->postorder_inverted = XNEWVEC (int, loop->num_nodes);
1460 df->n_blocks = loop_post_order_compute (df->postorder, loop);
1461 df->n_blocks_inverted
1462 = loop_inverted_post_order_compute (df->postorder_inverted, loop);
1463 gcc_assert ((unsigned) df->n_blocks == loop->num_nodes);
1464 gcc_assert ((unsigned) df->n_blocks_inverted == loop->num_nodes);
1466 bitmap blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1467 for (int i = 0; i < df->n_blocks; ++i)
1468 bitmap_set_bit (blocks, df->postorder[i]);
1469 df_set_blocks (blocks);
1470 BITMAP_FREE (blocks);
1472 df_analyze_1 ();
1476 /* Return the number of basic blocks from the last call to df_analyze. */
1479 df_get_n_blocks (enum df_flow_dir dir)
1481 gcc_assert (dir != DF_NONE);
1483 if (dir == DF_FORWARD)
1485 gcc_assert (df->postorder_inverted);
1486 return df->n_blocks_inverted;
1489 gcc_assert (df->postorder);
1490 return df->n_blocks;
1494 /* Return a pointer to the array of basic blocks in the reverse postorder.
1495 Depending on the direction of the dataflow problem,
1496 it returns either the usual reverse postorder array
1497 or the reverse postorder of inverted traversal. */
1498 int *
1499 df_get_postorder (enum df_flow_dir dir)
1501 gcc_assert (dir != DF_NONE);
1503 if (dir == DF_FORWARD)
1505 gcc_assert (df->postorder_inverted);
1506 return df->postorder_inverted;
1508 gcc_assert (df->postorder);
1509 return df->postorder;
1512 static struct df_problem user_problem;
1513 static struct dataflow user_dflow;
1515 /* Interface for calling iterative dataflow with user defined
1516 confluence and transfer functions. All that is necessary is to
1517 supply DIR, a direction, CONF_FUN_0, a confluence function for
1518 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1519 confluence function, TRANS_FUN, the basic block transfer function,
1520 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1521 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1523 void
1524 df_simple_dataflow (enum df_flow_dir dir,
1525 df_init_function init_fun,
1526 df_confluence_function_0 con_fun_0,
1527 df_confluence_function_n con_fun_n,
1528 df_transfer_function trans_fun,
1529 bitmap blocks, int * postorder, int n_blocks)
1531 memset (&user_problem, 0, sizeof (struct df_problem));
1532 user_problem.dir = dir;
1533 user_problem.init_fun = init_fun;
1534 user_problem.con_fun_0 = con_fun_0;
1535 user_problem.con_fun_n = con_fun_n;
1536 user_problem.trans_fun = trans_fun;
1537 user_dflow.problem = &user_problem;
1538 df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1543 /*----------------------------------------------------------------------------
1544 Functions to support limited incremental change.
1545 ----------------------------------------------------------------------------*/
1548 /* Get basic block info. */
1550 static void *
1551 df_get_bb_info (struct dataflow *dflow, unsigned int index)
1553 if (dflow->block_info == NULL)
1554 return NULL;
1555 if (index >= dflow->block_info_size)
1556 return NULL;
1557 return (void *)((char *)dflow->block_info
1558 + index * dflow->problem->block_info_elt_size);
1562 /* Set basic block info. */
1564 static void
1565 df_set_bb_info (struct dataflow *dflow, unsigned int index,
1566 void *bb_info)
1568 gcc_assert (dflow->block_info);
1569 memcpy ((char *)dflow->block_info
1570 + index * dflow->problem->block_info_elt_size,
1571 bb_info, dflow->problem->block_info_elt_size);
1575 /* Clear basic block info. */
1577 static void
1578 df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1580 gcc_assert (dflow->block_info);
1581 gcc_assert (dflow->block_info_size > index);
1582 memset ((char *)dflow->block_info
1583 + index * dflow->problem->block_info_elt_size,
1584 0, dflow->problem->block_info_elt_size);
1588 /* Mark the solutions as being out of date. */
1590 void
1591 df_mark_solutions_dirty (void)
1593 if (df)
1595 int p;
1596 for (p = 1; p < df->num_problems_defined; p++)
1597 df->problems_in_order[p]->solutions_dirty = true;
1602 /* Return true if BB needs it's transfer functions recomputed. */
1604 bool
1605 df_get_bb_dirty (basic_block bb)
1607 return bitmap_bit_p ((df_live
1608 ? df_live : df_lr)->out_of_date_transfer_functions,
1609 bb->index);
1613 /* Mark BB as needing it's transfer functions as being out of
1614 date. */
1616 void
1617 df_set_bb_dirty (basic_block bb)
1619 bb->flags |= BB_MODIFIED;
1620 if (df)
1622 int p;
1623 for (p = 1; p < df->num_problems_defined; p++)
1625 struct dataflow *dflow = df->problems_in_order[p];
1626 if (dflow->out_of_date_transfer_functions)
1627 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1629 df_mark_solutions_dirty ();
1634 /* Grow the bb_info array. */
1636 void
1637 df_grow_bb_info (struct dataflow *dflow)
1639 unsigned int new_size = last_basic_block_for_fn (cfun) + 1;
1640 if (dflow->block_info_size < new_size)
1642 new_size += new_size / 4;
1643 dflow->block_info
1644 = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1645 new_size
1646 * dflow->problem->block_info_elt_size);
1647 memset ((char *)dflow->block_info
1648 + dflow->block_info_size
1649 * dflow->problem->block_info_elt_size,
1651 (new_size - dflow->block_info_size)
1652 * dflow->problem->block_info_elt_size);
1653 dflow->block_info_size = new_size;
1658 /* Clear the dirty bits. This is called from places that delete
1659 blocks. */
1660 static void
1661 df_clear_bb_dirty (basic_block bb)
1663 int p;
1664 for (p = 1; p < df->num_problems_defined; p++)
1666 struct dataflow *dflow = df->problems_in_order[p];
1667 if (dflow->out_of_date_transfer_functions)
1668 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1672 /* Called from the rtl_compact_blocks to reorganize the problems basic
1673 block info. */
1675 void
1676 df_compact_blocks (void)
1678 int i, p;
1679 basic_block bb;
1680 void *problem_temps;
1681 bitmap_head tmp;
1683 bitmap_initialize (&tmp, &df_bitmap_obstack);
1684 for (p = 0; p < df->num_problems_defined; p++)
1686 struct dataflow *dflow = df->problems_in_order[p];
1688 /* Need to reorganize the out_of_date_transfer_functions for the
1689 dflow problem. */
1690 if (dflow->out_of_date_transfer_functions)
1692 bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
1693 bitmap_clear (dflow->out_of_date_transfer_functions);
1694 if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1695 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1696 if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1697 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1699 i = NUM_FIXED_BLOCKS;
1700 FOR_EACH_BB_FN (bb, cfun)
1702 if (bitmap_bit_p (&tmp, bb->index))
1703 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1704 i++;
1708 /* Now shuffle the block info for the problem. */
1709 if (dflow->problem->free_bb_fun)
1711 int size = (last_basic_block_for_fn (cfun)
1712 * dflow->problem->block_info_elt_size);
1713 problem_temps = XNEWVAR (char, size);
1714 df_grow_bb_info (dflow);
1715 memcpy (problem_temps, dflow->block_info, size);
1717 /* Copy the bb info from the problem tmps to the proper
1718 place in the block_info vector. Null out the copied
1719 item. The entry and exit blocks never move. */
1720 i = NUM_FIXED_BLOCKS;
1721 FOR_EACH_BB_FN (bb, cfun)
1723 df_set_bb_info (dflow, i,
1724 (char *)problem_temps
1725 + bb->index * dflow->problem->block_info_elt_size);
1726 i++;
1728 memset ((char *)dflow->block_info
1729 + i * dflow->problem->block_info_elt_size, 0,
1730 (last_basic_block_for_fn (cfun) - i)
1731 * dflow->problem->block_info_elt_size);
1732 free (problem_temps);
1736 /* Shuffle the bits in the basic_block indexed arrays. */
1738 if (df->blocks_to_analyze)
1740 if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1741 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1742 if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1743 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1744 bitmap_copy (&tmp, df->blocks_to_analyze);
1745 bitmap_clear (df->blocks_to_analyze);
1746 i = NUM_FIXED_BLOCKS;
1747 FOR_EACH_BB_FN (bb, cfun)
1749 if (bitmap_bit_p (&tmp, bb->index))
1750 bitmap_set_bit (df->blocks_to_analyze, i);
1751 i++;
1755 bitmap_clear (&tmp);
1757 i = NUM_FIXED_BLOCKS;
1758 FOR_EACH_BB_FN (bb, cfun)
1760 SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
1761 bb->index = i;
1762 i++;
1765 gcc_assert (i == n_basic_blocks_for_fn (cfun));
1767 for (; i < last_basic_block_for_fn (cfun); i++)
1768 SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
1770 #ifdef DF_DEBUG_CFG
1771 if (!df_lr->solutions_dirty)
1772 df_set_clean_cfg ();
1773 #endif
1777 /* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1778 block. There is no excuse for people to do this kind of thing. */
1780 void
1781 df_bb_replace (int old_index, basic_block new_block)
1783 int new_block_index = new_block->index;
1784 int p;
1786 if (dump_file)
1787 fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1789 gcc_assert (df);
1790 gcc_assert (BASIC_BLOCK_FOR_FN (cfun, old_index) == NULL);
1792 for (p = 0; p < df->num_problems_defined; p++)
1794 struct dataflow *dflow = df->problems_in_order[p];
1795 if (dflow->block_info)
1797 df_grow_bb_info (dflow);
1798 df_set_bb_info (dflow, old_index,
1799 df_get_bb_info (dflow, new_block_index));
1803 df_clear_bb_dirty (new_block);
1804 SET_BASIC_BLOCK_FOR_FN (cfun, old_index, new_block);
1805 new_block->index = old_index;
1806 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, old_index));
1807 SET_BASIC_BLOCK_FOR_FN (cfun, new_block_index, NULL);
1811 /* Free all of the per basic block dataflow from all of the problems.
1812 This is typically called before a basic block is deleted and the
1813 problem will be reanalyzed. */
1815 void
1816 df_bb_delete (int bb_index)
1818 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1819 int i;
1821 if (!df)
1822 return;
1824 for (i = 0; i < df->num_problems_defined; i++)
1826 struct dataflow *dflow = df->problems_in_order[i];
1827 if (dflow->problem->free_bb_fun)
1829 void *bb_info = df_get_bb_info (dflow, bb_index);
1830 if (bb_info)
1832 dflow->problem->free_bb_fun (bb, bb_info);
1833 df_clear_bb_info (dflow, bb_index);
1837 df_clear_bb_dirty (bb);
1838 df_mark_solutions_dirty ();
1842 /* Verify that there is a place for everything and everything is in
1843 its place. This is too expensive to run after every pass in the
1844 mainline. However this is an excellent debugging tool if the
1845 dataflow information is not being updated properly. You can just
1846 sprinkle calls in until you find the place that is changing an
1847 underlying structure without calling the proper updating
1848 routine. */
1850 void
1851 df_verify (void)
1853 df_scan_verify ();
1854 #ifdef ENABLE_DF_CHECKING
1855 df_lr_verify_transfer_functions ();
1856 if (df_live)
1857 df_live_verify_transfer_functions ();
1858 #endif
1861 #ifdef DF_DEBUG_CFG
1863 /* Compute an array of ints that describes the cfg. This can be used
1864 to discover places where the cfg is modified by the appropriate
1865 calls have not been made to the keep df informed. The internals of
1866 this are unexciting, the key is that two instances of this can be
1867 compared to see if any changes have been made to the cfg. */
1869 static int *
1870 df_compute_cfg_image (void)
1872 basic_block bb;
1873 int size = 2 + (2 * n_basic_blocks_for_fn (cfun));
1874 int i;
1875 int * map;
1877 FOR_ALL_BB_FN (bb, cfun)
1879 size += EDGE_COUNT (bb->succs);
1882 map = XNEWVEC (int, size);
1883 map[0] = size;
1884 i = 1;
1885 FOR_ALL_BB_FN (bb, cfun)
1887 edge_iterator ei;
1888 edge e;
1890 map[i++] = bb->index;
1891 FOR_EACH_EDGE (e, ei, bb->succs)
1892 map[i++] = e->dest->index;
1893 map[i++] = -1;
1895 map[i] = -1;
1896 return map;
1899 static int *saved_cfg = NULL;
1902 /* This function compares the saved version of the cfg with the
1903 current cfg and aborts if the two are identical. The function
1904 silently returns if the cfg has been marked as dirty or the two are
1905 the same. */
1907 void
1908 df_check_cfg_clean (void)
1910 int *new_map;
1912 if (!df)
1913 return;
1915 if (df_lr->solutions_dirty)
1916 return;
1918 if (saved_cfg == NULL)
1919 return;
1921 new_map = df_compute_cfg_image ();
1922 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1923 free (new_map);
1927 /* This function builds a cfg fingerprint and squirrels it away in
1928 saved_cfg. */
1930 static void
1931 df_set_clean_cfg (void)
1933 free (saved_cfg);
1934 saved_cfg = df_compute_cfg_image ();
1937 #endif /* DF_DEBUG_CFG */
1938 /*----------------------------------------------------------------------------
1939 PUBLIC INTERFACES TO QUERY INFORMATION.
1940 ----------------------------------------------------------------------------*/
1943 /* Return first def of REGNO within BB. */
1945 df_ref
1946 df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1948 rtx_insn *insn;
1949 df_ref def;
1951 FOR_BB_INSNS (bb, insn)
1953 if (!INSN_P (insn))
1954 continue;
1956 FOR_EACH_INSN_DEF (def, insn)
1957 if (DF_REF_REGNO (def) == regno)
1958 return def;
1960 return NULL;
1964 /* Return last def of REGNO within BB. */
1966 df_ref
1967 df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1969 rtx_insn *insn;
1970 df_ref def;
1972 FOR_BB_INSNS_REVERSE (bb, insn)
1974 if (!INSN_P (insn))
1975 continue;
1977 FOR_EACH_INSN_DEF (def, insn)
1978 if (DF_REF_REGNO (def) == regno)
1979 return def;
1982 return NULL;
1985 /* Finds the reference corresponding to the definition of REG in INSN.
1986 DF is the dataflow object. */
1988 df_ref
1989 df_find_def (rtx_insn *insn, rtx reg)
1991 df_ref def;
1993 if (GET_CODE (reg) == SUBREG)
1994 reg = SUBREG_REG (reg);
1995 gcc_assert (REG_P (reg));
1997 FOR_EACH_INSN_DEF (def, insn)
1998 if (DF_REF_REGNO (def) == REGNO (reg))
1999 return def;
2001 return NULL;
2005 /* Return true if REG is defined in INSN, zero otherwise. */
2007 bool
2008 df_reg_defined (rtx_insn *insn, rtx reg)
2010 return df_find_def (insn, reg) != NULL;
2014 /* Finds the reference corresponding to the use of REG in INSN.
2015 DF is the dataflow object. */
2017 df_ref
2018 df_find_use (rtx_insn *insn, rtx reg)
2020 df_ref use;
2022 if (GET_CODE (reg) == SUBREG)
2023 reg = SUBREG_REG (reg);
2024 gcc_assert (REG_P (reg));
2026 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2027 FOR_EACH_INSN_INFO_USE (use, insn_info)
2028 if (DF_REF_REGNO (use) == REGNO (reg))
2029 return use;
2030 if (df->changeable_flags & DF_EQ_NOTES)
2031 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2032 if (DF_REF_REGNO (use) == REGNO (reg))
2033 return use;
2034 return NULL;
2038 /* Return true if REG is referenced in INSN, zero otherwise. */
2040 bool
2041 df_reg_used (rtx_insn *insn, rtx reg)
2043 return df_find_use (insn, reg) != NULL;
2047 /*----------------------------------------------------------------------------
2048 Debugging and printing functions.
2049 ----------------------------------------------------------------------------*/
2051 /* Write information about registers and basic blocks into FILE.
2052 This is part of making a debugging dump. */
2054 void
2055 dump_regset (regset r, FILE *outf)
2057 unsigned i;
2058 reg_set_iterator rsi;
2060 if (r == NULL)
2062 fputs (" (nil)", outf);
2063 return;
2066 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
2068 fprintf (outf, " %d", i);
2069 if (i < FIRST_PSEUDO_REGISTER)
2070 fprintf (outf, " [%s]",
2071 reg_names[i]);
2075 /* Print a human-readable representation of R on the standard error
2076 stream. This function is designed to be used from within the
2077 debugger. */
2078 extern void debug_regset (regset);
2079 DEBUG_FUNCTION void
2080 debug_regset (regset r)
2082 dump_regset (r, stderr);
2083 putc ('\n', stderr);
2086 /* Write information about registers and basic blocks into FILE.
2087 This is part of making a debugging dump. */
2089 void
2090 df_print_regset (FILE *file, bitmap r)
2092 unsigned int i;
2093 bitmap_iterator bi;
2095 if (r == NULL)
2096 fputs (" (nil)", file);
2097 else
2099 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
2101 fprintf (file, " %d", i);
2102 if (i < FIRST_PSEUDO_REGISTER)
2103 fprintf (file, " [%s]", reg_names[i]);
2106 fprintf (file, "\n");
2110 /* Write information about registers and basic blocks into FILE. The
2111 bitmap is in the form used by df_byte_lr. This is part of making a
2112 debugging dump. */
2114 void
2115 df_print_word_regset (FILE *file, bitmap r)
2117 unsigned int max_reg = max_reg_num ();
2119 if (r == NULL)
2120 fputs (" (nil)", file);
2121 else
2123 unsigned int i;
2124 for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
2126 bool found = (bitmap_bit_p (r, 2 * i)
2127 || bitmap_bit_p (r, 2 * i + 1));
2128 if (found)
2130 int word;
2131 const char * sep = "";
2132 fprintf (file, " %d", i);
2133 fprintf (file, "(");
2134 for (word = 0; word < 2; word++)
2135 if (bitmap_bit_p (r, 2 * i + word))
2137 fprintf (file, "%s%d", sep, word);
2138 sep = ", ";
2140 fprintf (file, ")");
2144 fprintf (file, "\n");
2148 /* Dump dataflow info. */
2150 void
2151 df_dump (FILE *file)
2153 basic_block bb;
2154 df_dump_start (file);
2156 FOR_ALL_BB_FN (bb, cfun)
2158 df_print_bb_index (bb, file);
2159 df_dump_top (bb, file);
2160 df_dump_bottom (bb, file);
2163 fprintf (file, "\n");
2167 /* Dump dataflow info for df->blocks_to_analyze. */
2169 void
2170 df_dump_region (FILE *file)
2172 if (df->blocks_to_analyze)
2174 bitmap_iterator bi;
2175 unsigned int bb_index;
2177 fprintf (file, "\n\nstarting region dump\n");
2178 df_dump_start (file);
2180 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
2182 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2183 dump_bb (file, bb, 0, TDF_DETAILS);
2185 fprintf (file, "\n");
2187 else
2188 df_dump (file);
2192 /* Dump the introductory information for each problem defined. */
2194 void
2195 df_dump_start (FILE *file)
2197 int i;
2199 if (!df || !file)
2200 return;
2202 fprintf (file, "\n\n%s\n", current_function_name ());
2203 fprintf (file, "\nDataflow summary:\n");
2204 if (df->blocks_to_analyze)
2205 fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
2206 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
2208 for (i = 0; i < df->num_problems_defined; i++)
2210 struct dataflow *dflow = df->problems_in_order[i];
2211 if (dflow->computed)
2213 df_dump_problem_function fun = dflow->problem->dump_start_fun;
2214 if (fun)
2215 fun (file);
2221 /* Dump the top or bottom of the block information for BB. */
2222 static void
2223 df_dump_bb_problem_data (basic_block bb, FILE *file, bool top)
2225 int i;
2227 if (!df || !file)
2228 return;
2230 for (i = 0; i < df->num_problems_defined; i++)
2232 struct dataflow *dflow = df->problems_in_order[i];
2233 if (dflow->computed)
2235 df_dump_bb_problem_function bbfun;
2237 if (top)
2238 bbfun = dflow->problem->dump_top_fun;
2239 else
2240 bbfun = dflow->problem->dump_bottom_fun;
2242 if (bbfun)
2243 bbfun (bb, file);
2248 /* Dump the top of the block information for BB. */
2250 void
2251 df_dump_top (basic_block bb, FILE *file)
2253 df_dump_bb_problem_data (bb, file, /*top=*/true);
2256 /* Dump the bottom of the block information for BB. */
2258 void
2259 df_dump_bottom (basic_block bb, FILE *file)
2261 df_dump_bb_problem_data (bb, file, /*top=*/false);
2265 /* Dump information about INSN just before or after dumping INSN itself. */
2266 static void
2267 df_dump_insn_problem_data (const rtx_insn *insn, FILE *file, bool top)
2269 int i;
2271 if (!df || !file)
2272 return;
2274 for (i = 0; i < df->num_problems_defined; i++)
2276 struct dataflow *dflow = df->problems_in_order[i];
2277 if (dflow->computed)
2279 df_dump_insn_problem_function insnfun;
2281 if (top)
2282 insnfun = dflow->problem->dump_insn_top_fun;
2283 else
2284 insnfun = dflow->problem->dump_insn_bottom_fun;
2286 if (insnfun)
2287 insnfun (insn, file);
2292 /* Dump information about INSN before dumping INSN itself. */
2294 void
2295 df_dump_insn_top (const rtx_insn *insn, FILE *file)
2297 df_dump_insn_problem_data (insn, file, /*top=*/true);
2300 /* Dump information about INSN after dumping INSN itself. */
2302 void
2303 df_dump_insn_bottom (const rtx_insn *insn, FILE *file)
2305 df_dump_insn_problem_data (insn, file, /*top=*/false);
2309 static void
2310 df_ref_dump (df_ref ref, FILE *file)
2312 fprintf (file, "%c%d(%d)",
2313 DF_REF_REG_DEF_P (ref)
2314 ? 'd'
2315 : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2316 DF_REF_ID (ref),
2317 DF_REF_REGNO (ref));
2320 void
2321 df_refs_chain_dump (df_ref ref, bool follow_chain, FILE *file)
2323 fprintf (file, "{ ");
2324 for (; ref; ref = DF_REF_NEXT_LOC (ref))
2326 df_ref_dump (ref, file);
2327 if (follow_chain)
2328 df_chain_dump (DF_REF_CHAIN (ref), file);
2330 fprintf (file, "}");
2334 /* Dump either a ref-def or reg-use chain. */
2336 void
2337 df_regs_chain_dump (df_ref ref, FILE *file)
2339 fprintf (file, "{ ");
2340 while (ref)
2342 df_ref_dump (ref, file);
2343 ref = DF_REF_NEXT_REG (ref);
2345 fprintf (file, "}");
2349 static void
2350 df_mws_dump (struct df_mw_hardreg *mws, FILE *file)
2352 for (; mws; mws = DF_MWS_NEXT (mws))
2353 fprintf (file, "mw %c r[%d..%d]\n",
2354 DF_MWS_REG_DEF_P (mws) ? 'd' : 'u',
2355 mws->start_regno, mws->end_regno);
2359 static void
2360 df_insn_uid_debug (unsigned int uid,
2361 bool follow_chain, FILE *file)
2363 fprintf (file, "insn %d luid %d",
2364 uid, DF_INSN_UID_LUID (uid));
2366 if (DF_INSN_UID_DEFS (uid))
2368 fprintf (file, " defs ");
2369 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2372 if (DF_INSN_UID_USES (uid))
2374 fprintf (file, " uses ");
2375 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2378 if (DF_INSN_UID_EQ_USES (uid))
2380 fprintf (file, " eq uses ");
2381 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2384 if (DF_INSN_UID_MWS (uid))
2386 fprintf (file, " mws ");
2387 df_mws_dump (DF_INSN_UID_MWS (uid), file);
2389 fprintf (file, "\n");
2393 DEBUG_FUNCTION void
2394 df_insn_debug (rtx_insn *insn, bool follow_chain, FILE *file)
2396 df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2399 DEBUG_FUNCTION void
2400 df_insn_debug_regno (rtx_insn *insn, FILE *file)
2402 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2404 fprintf (file, "insn %d bb %d luid %d defs ",
2405 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2406 DF_INSN_INFO_LUID (insn_info));
2407 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2409 fprintf (file, " uses ");
2410 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2412 fprintf (file, " eq_uses ");
2413 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2414 fprintf (file, "\n");
2417 DEBUG_FUNCTION void
2418 df_regno_debug (unsigned int regno, FILE *file)
2420 fprintf (file, "reg %d defs ", regno);
2421 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2422 fprintf (file, " uses ");
2423 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2424 fprintf (file, " eq_uses ");
2425 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2426 fprintf (file, "\n");
2430 DEBUG_FUNCTION void
2431 df_ref_debug (df_ref ref, FILE *file)
2433 fprintf (file, "%c%d ",
2434 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2435 DF_REF_ID (ref));
2436 fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ",
2437 DF_REF_REGNO (ref),
2438 DF_REF_BBNO (ref),
2439 DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2440 DF_REF_FLAGS (ref),
2441 DF_REF_TYPE (ref));
2442 if (DF_REF_LOC (ref))
2444 if (flag_dump_noaddr)
2445 fprintf (file, "loc #(#) chain ");
2446 else
2447 fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2448 (void *)*DF_REF_LOC (ref));
2450 else
2451 fprintf (file, "chain ");
2452 df_chain_dump (DF_REF_CHAIN (ref), file);
2453 fprintf (file, "\n");
2456 /* Functions for debugging from GDB. */
2458 DEBUG_FUNCTION void
2459 debug_df_insn (rtx_insn *insn)
2461 df_insn_debug (insn, true, stderr);
2462 debug_rtx (insn);
2466 DEBUG_FUNCTION void
2467 debug_df_reg (rtx reg)
2469 df_regno_debug (REGNO (reg), stderr);
2473 DEBUG_FUNCTION void
2474 debug_df_regno (unsigned int regno)
2476 df_regno_debug (regno, stderr);
2480 DEBUG_FUNCTION void
2481 debug_df_ref (df_ref ref)
2483 df_ref_debug (ref, stderr);
2487 DEBUG_FUNCTION void
2488 debug_df_defno (unsigned int defno)
2490 df_ref_debug (DF_DEFS_GET (defno), stderr);
2494 DEBUG_FUNCTION void
2495 debug_df_useno (unsigned int defno)
2497 df_ref_debug (DF_USES_GET (defno), stderr);
2501 DEBUG_FUNCTION void
2502 debug_df_chain (struct df_link *link)
2504 df_chain_dump (link, stderr);
2505 fputc ('\n', stderr);