1 /* Allocation for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
3 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 2, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
30 The files in this collection (df*.c,df.h) provide a general framework
31 for solving dataflow problems. The global dataflow is performed using
32 a good implementation of iterative dataflow analysis.
34 The file df-problems.c provides problem instance for the most common
35 dataflow problems: reaching defs, upward exposed uses, live variables,
36 uninitialized variables, def-use chains, and use-def chains. However,
37 the interface allows other dataflow problems to be defined as well.
42 Here is an example of using the dataflow routines.
46 df = df_init (init_flags);
48 df_add_problem (df, problem);
50 df_set_blocks (df, blocks);
52 df_rescan_blocks (df, blocks);
62 DF_INIT simply creates a poor man's object (df) that needs to be
63 passed to all the dataflow routines. df_finish destroys this object
64 and frees up any allocated memory.
66 There are two flags that can be passed to df_init:
68 DF_NO_SCAN means that no scanning of the rtl code is performed. This
69 is used if the problem instance is to do it's own scanning.
71 DF_HARD_REGS means that the scanning is to build information about
72 both pseudo registers and hardware registers. Without this
73 information, the problems will be solved only on pseudo registers.
77 DF_ADD_PROBLEM adds a problem, defined by an instance to struct
78 df_problem, to the set of problems solved in this instance of df. All
79 calls to add a problem for a given instance of df must occur before
80 the first call to DF_RESCAN_BLOCKS or DF_ANALYZE.
82 For all of the problems defined in df-problems.c, there are
83 convienence functions named DF_*_ADD_PROBLEM.
86 Problems can be dependent on other problems. For instance, solving
87 def-use or use-def chains is dependant on solving reaching
88 definitions. As long as these dependancies are listed in the problem
89 definition, the order of adding the problems is not material.
90 Otherwise, the problems will be solved in the order of calls to
91 df_add_problem. Note that it is not necessary to have a problem. In
92 that case, df will just be used to do the scanning.
96 DF_SET_BLOCKS is an optional call used to define a region of the
97 function on which the analysis will be performed. The normal case is
98 to analyze the entire function and no call to df_set_blocks is made.
100 When a subset is given, the analysis behaves as if the function only
101 contains those blocks and any edges that occur directly between the
102 blocks in the set. Care should be taken to call df_set_blocks right
103 before the call to analyze in order to eliminate the possiblity that
104 optimizations that reorder blocks invalidate the bitvector.
108 DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
109 (re)run over the set of blocks passed in. If blocks is NULL, the entire
110 function (or all of the blocks defined in df_set_blocks) is rescanned.
111 If blocks contains blocks that were not defined in the call to
112 df_set_blocks, these blocks are added to the set of blocks.
115 DF_ANALYZE causes all of the defined problems to be (re)solved. It
116 does not cause blocks to be (re)scanned at the rtl level unless no
117 prior call is made to df_rescan_blocks.
120 DF_DUMP can then be called to dump the information produce to some
125 DF_FINISH causes all of the datastructures to be cleaned up and freed.
126 The df_instance is also freed and its pointer should be NULLed.
131 Scanning produces a `struct df_ref' data structure (ref) is allocated
132 for every register reference (def or use) and this records the insn
133 and bb the ref is found within. The refs are linked together in
134 chains of uses and defs for each insn and for each register. Each ref
135 also has a chain field that links all the use refs for a def or all
136 the def refs for a use. This is used to create use-def or def-use
139 Different optimizations have different needs. Ultimately, only
140 register allocation and schedulers should be using the bitmaps
141 produced for the live register and uninitialized register problems.
142 The rest of the backend should be upgraded to using and maintaining
143 the linked information such as def use or use def chains.
149 While incremental bitmaps are not worthwhile to maintain, incremental
150 chains may be perfectly reasonable. The fastest way to build chains
151 from scratch or after significant modifications is to build reaching
152 definitions (RD) and build the chains from this.
154 However, general algorithms for maintaining use-def or def-use chains
155 are not practical. The amount of work to recompute the chain any
156 chain after an arbitrary change is large. However, with a modest
157 amount of work it is generally possible to have the application that
158 uses the chains keep them up to date. The high level knowledge of
159 what is really happening is essential to crafting efficient
160 incremental algorithms.
162 As for the bit vector problems, there is no interface to give a set of
163 blocks over with to resolve the iteration. In general, restarting a
164 dataflow iteration is difficult and expensive. Again, the best way to
165 keep the dataflow infomation up to data (if this is really what is
166 needed) it to formulate a problem specific solution.
168 There are fine grained calls for creating and deleting references from
169 instructions in df-scan.c. However, these are not currently connected
170 to the engine that resolves the dataflow equations.
175 The basic object is a DF_REF (reference) and this may either be a
176 DEF (definition) or a USE of a register.
178 These are linked into a variety of lists; namely reg-def, reg-use,
179 insn-def, insn-use, def-use, and use-def lists. For example, the
180 reg-def lists contain all the locations that define a given register
181 while the insn-use lists contain all the locations that use a
184 Note that the reg-def and reg-use chains are generally short for
185 pseudos and long for the hard registers.
189 There are 4 ways to obtain access to refs:
191 1) References are divided into two categories, REAL and ARTIFICIAL.
193 REAL refs are associated with instructions. They are linked into
194 either in the insn's defs list (accessed by the DF_INSN_DEFS or
195 DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the
196 DF_INSN_USES or DF_INSN_UID_USES macros). These macros produce a
197 ref (or NULL), the rest of the list can be obtained by traversal of
198 the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.) There
199 is no significance to the ordering of the uses or refs in an
202 ARTIFICIAL refs are associated with basic blocks. The heads of
203 these lists can be accessed by calling get_artificial_defs or
204 get_artificial_uses for the particular basic block. Artificial
205 defs and uses are only there if DF_HARD_REGS was specified when the
206 df instance was created.
208 Artificial defs and uses occur at the beginning blocks that are the
209 destination of eh edges. The defs come from the registers
210 specified in EH_RETURN_DATA_REGNO and the uses come from the
211 registers specified in ED_USES. Logically these defs and uses
212 should really occur along the eh edge, but there is no convienent
213 way to do this. Artificial edges that occur at the beginning of
214 the block have the DF_REF_AT_TOP flag set.
216 Artificial uses also occur at the end of all blocks. These arise
217 from the hard registers that are always live, such as the stack
218 register and are put there to keep the code from forgetting about
221 2) All of the uses and defs associated with each pseudo or hard
222 register are linked in a bidirectional chain. These are called
223 reg-use or reg_def chains.
225 The first use (or def) for a register can be obtained using the
226 DF_REG_USE_GET macro (or DF_REG_DEF_GET macro). Subsequent uses
227 for the same regno can be obtained by following the next_reg field
230 In previous versions of this code, these chains were ordered. It
231 has not been practical to continue this practice.
233 3) If def-use or use-def chains are built, these can be traversed to
236 4) An array of all of the uses (and an array of all of the defs) can
237 be built. These arrays are indexed by the value in the id
238 structure. These arrays are only lazily kept up to date, and that
239 process can be expensive. To have these arrays built, call
240 df_reorganize_refs. Note that the values in the id field of a ref
241 may change across calls to df_analyze or df_reorganize refs.
243 If the only use of this array is to find all of the refs, it is
244 better to traverse all of the registers and then traverse all of
245 reg-use or reg-def chains.
251 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
252 both a use and a def. These are both marked read/write to show that they
253 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
254 will generate a use of reg 42 followed by a def of reg 42 (both marked
255 read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
256 generates a use of reg 41 then a def of reg 41 (both marked read/write),
257 even though reg 41 is decremented before it is used for the memory
258 address in this second example.
260 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
261 for which the number of word_mode units covered by the outer mode is
262 smaller than that covered by the inner mode, invokes a read-modify-write.
263 operation. We generate both a use and a def and again mark them
266 Paradoxical subreg writes do not leave a trace of the old content, so they
267 are write-only operations.
273 #include "coretypes.h"
277 #include "insn-config.h"
279 #include "function.h"
282 #include "alloc-pool.h"
284 #include "hard-reg-set.h"
285 #include "basic-block.h"
290 #include "tree-pass.h"
292 static struct df *ddf = NULL;
293 struct df *shared_df = NULL;
295 /*----------------------------------------------------------------------------
296 Functions to create, destroy and manipulate an instance of df.
297 ----------------------------------------------------------------------------*/
300 /* Initialize dataflow analysis and allocate and initialize dataflow
306 struct df *df = xcalloc (1, sizeof (struct df));
309 /* This is executed once per compilation to initialize platform
310 specific data structures. */
313 /* All df instance must define the scanning problem. */
314 df_scan_add_problem (df);
319 /* Add PROBLEM to the DF instance. */
322 df_add_problem (struct df *df, struct df_problem *problem)
324 struct dataflow *dflow;
326 /* First try to add the dependent problem. */
327 if (problem->dependent_problem)
328 df_add_problem (df, problem->dependent_problem);
330 /* Check to see if this problem has already been defined. If it
331 has, just return that instance, if not, add it to the end of the
333 dflow = df->problems_by_index[problem->id];
337 /* Make a new one and add it to the end. */
338 dflow = xcalloc (1, sizeof (struct dataflow));
340 dflow->problem = problem;
341 df->problems_in_order[df->num_problems_defined++] = dflow;
342 df->problems_by_index[dflow->problem->id] = dflow;
348 /* Set the blocks that are to be considered for analysis. If this is
349 not called or is called with null, the entire function in
353 df_set_blocks (struct df *df, bitmap blocks)
357 if (df->blocks_to_analyze)
360 bitmap diff = BITMAP_ALLOC (NULL);
361 bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
362 for (p = 0; p < df->num_problems_defined; p++)
364 struct dataflow *dflow = df->problems_in_order[p];
365 if (*dflow->problem->free_bb_fun)
368 unsigned int bb_index;
370 EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
372 basic_block bb = BASIC_BLOCK (bb_index);
373 (*dflow->problem->free_bb_fun) (dflow, bb, diff);
381 df->blocks_to_analyze = BITMAP_ALLOC (NULL);
382 bitmap_copy (df->blocks_to_analyze, blocks);
386 if (df->blocks_to_analyze)
388 BITMAP_FREE (df->blocks_to_analyze);
389 df->blocks_to_analyze = NULL;
395 /* Free all the dataflow info and the DF structure. This should be
396 called from the df_finish macro which also NULLs the parm. */
399 df_finish1 (struct df *df)
403 for (i = 0; i < df->num_problems_defined; i++)
404 (*df->problems_in_order[i]->problem->free_fun) (df->problems_in_order[i]);
410 /*----------------------------------------------------------------------------
411 The general data flow analysis engine.
412 ----------------------------------------------------------------------------*/
415 /* Hybrid search algorithm from "Implementation Techniques for
416 Efficient Data-Flow Analysis of Large Programs". */
419 df_hybrid_search_forward (basic_block bb,
420 struct dataflow *dataflow,
428 SET_BIT (dataflow->visited, bb->index);
429 gcc_assert (TEST_BIT (dataflow->pending, bb->index));
430 RESET_BIT (dataflow->pending, i);
432 /* Calculate <conf_op> of predecessor_outs. */
433 if (EDGE_COUNT (bb->preds) > 0)
434 FOR_EACH_EDGE (e, ei, bb->preds)
436 if (!TEST_BIT (dataflow->considered, e->src->index))
439 (*dataflow->problem->con_fun_n) (dataflow, e);
441 else if (*dataflow->problem->con_fun_0)
442 (*dataflow->problem->con_fun_0) (dataflow, bb);
444 result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
446 if (!result_changed || single_pass)
449 FOR_EACH_EDGE (e, ei, bb->succs)
451 if (e->dest->index == i)
453 if (!TEST_BIT (dataflow->considered, e->dest->index))
455 SET_BIT (dataflow->pending, e->dest->index);
458 FOR_EACH_EDGE (e, ei, bb->succs)
460 if (e->dest->index == i)
463 if (!TEST_BIT (dataflow->considered, e->dest->index))
465 if (!TEST_BIT (dataflow->visited, e->dest->index))
466 df_hybrid_search_forward (e->dest, dataflow, single_pass);
471 df_hybrid_search_backward (basic_block bb,
472 struct dataflow *dataflow,
480 SET_BIT (dataflow->visited, bb->index);
481 gcc_assert (TEST_BIT (dataflow->pending, bb->index));
482 RESET_BIT (dataflow->pending, i);
484 /* Calculate <conf_op> of predecessor_outs. */
485 if (EDGE_COUNT (bb->succs) > 0)
486 FOR_EACH_EDGE (e, ei, bb->succs)
488 if (!TEST_BIT (dataflow->considered, e->dest->index))
491 (*dataflow->problem->con_fun_n) (dataflow, e);
493 else if (*dataflow->problem->con_fun_0)
494 (*dataflow->problem->con_fun_0) (dataflow, bb);
496 result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
498 if (!result_changed || single_pass)
501 FOR_EACH_EDGE (e, ei, bb->preds)
503 if (e->src->index == i)
506 if (!TEST_BIT (dataflow->considered, e->src->index))
509 SET_BIT (dataflow->pending, e->src->index);
512 FOR_EACH_EDGE (e, ei, bb->preds)
514 if (e->src->index == i)
517 if (!TEST_BIT (dataflow->considered, e->src->index))
520 if (!TEST_BIT (dataflow->visited, e->src->index))
521 df_hybrid_search_backward (e->src, dataflow, single_pass);
526 /* This function will perform iterative bitvector dataflow described
527 by DATAFLOW, producing the in and out sets. Only the part of the
528 cfg induced by blocks in DATAFLOW->order is taken into account.
530 SINGLE_PASS is true if you just want to make one pass over the
534 df_iterative_dataflow (struct dataflow *dataflow,
535 bitmap blocks_to_consider, bitmap blocks_to_init,
536 int *blocks_in_postorder, int n_blocks,
541 sbitmap visited = sbitmap_alloc (last_basic_block);
542 sbitmap pending = sbitmap_alloc (last_basic_block);
543 sbitmap considered = sbitmap_alloc (last_basic_block);
546 dataflow->visited = visited;
547 dataflow->pending = pending;
548 dataflow->considered = considered;
550 sbitmap_zero (visited);
551 sbitmap_zero (pending);
552 sbitmap_zero (considered);
554 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
556 SET_BIT (considered, idx);
559 for (i = 0; i < n_blocks; i++)
561 idx = blocks_in_postorder[i];
562 SET_BIT (pending, idx);
565 (*dataflow->problem->init_fun) (dataflow, blocks_to_init);
570 /* For forward problems, you want to pass in reverse postorder
571 and for backward problems you want postorder. This has been
572 shown to be as good as you can do by several people, the
573 first being Mathew Hecht in his phd dissertation.
575 The nodes are passed into this function in postorder. */
577 if (dataflow->problem->dir == DF_FORWARD)
579 for (i = n_blocks - 1 ; i >= 0 ; i--)
581 idx = blocks_in_postorder[i];
583 if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
584 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
589 for (i = 0; i < n_blocks; i++)
591 idx = blocks_in_postorder[i];
593 if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
594 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
598 if (sbitmap_first_set_bit (pending) == -1)
601 sbitmap_zero (visited);
604 sbitmap_free (pending);
605 sbitmap_free (visited);
606 sbitmap_free (considered);
610 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
611 the order of the remaining entries. Returns the length of the resulting
615 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
619 for (act = 0, last = 0; act < len; act++)
620 if (bitmap_bit_p (blocks, list[act]))
621 list[last++] = list[act];
627 /* Execute dataflow analysis on a single dataflow problem.
629 There are three sets of blocks passed in:
631 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
632 examined or will be computed. For calls from DF_ANALYZE, this is
633 the set of blocks that has been passed to DF_SET_BLOCKS. For calls
634 from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
635 blocks in the fringe (the set of blocks passed in plus the set of
636 immed preds and succs of those blocks).
638 BLOCKS_TO_INIT are the blocks whose solution will be changed by
639 this iteration. For calls from DF_ANALYZE, this is the set of
640 blocks that has been passed to DF_SET_BLOCKS. For calls from
641 DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
644 BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
645 For calls from DF_ANALYZE, this is the accumulated set of blocks
646 that has been passed to DF_RESCAN_BLOCKS since the last call to
647 DF_ANALYZE. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
648 this is the set of blocks passed in.
650 blocks_to_consider blocks_to_init blocks_to_scan
651 full redo all all all
652 partial redo all all sub
653 small fixup fringe sub sub
657 df_analyze_problem (struct dataflow *dflow,
658 bitmap blocks_to_consider,
659 bitmap blocks_to_init,
660 bitmap blocks_to_scan,
661 int *postorder, int n_blocks, bool single_pass)
663 /* (Re)Allocate the datastructures necessary to solve the problem. */
664 if (*dflow->problem->alloc_fun)
665 (*dflow->problem->alloc_fun) (dflow, blocks_to_scan);
667 /* Set up the problem and compute the local information. This
668 function is passed both the blocks_to_consider and the
669 blocks_to_scan because the RD and RU problems require the entire
670 function to be rescanned if they are going to be updated. */
671 if (*dflow->problem->local_compute_fun)
672 (*dflow->problem->local_compute_fun) (dflow, blocks_to_consider, blocks_to_scan);
674 /* Solve the equations. */
675 if (*dflow->problem->dataflow_fun)
676 (*dflow->problem->dataflow_fun) (dflow, blocks_to_consider, blocks_to_init,
677 postorder, n_blocks, single_pass);
679 /* Massage the solution. */
680 if (*dflow->problem->finalize_fun)
681 (*dflow->problem->finalize_fun) (dflow, blocks_to_consider);
685 /* Analyze dataflow info for the basic blocks specified by the bitmap
686 BLOCKS, or for the whole CFG if BLOCKS is zero. */
689 df_analyze (struct df *df)
691 int *postorder = xmalloc (sizeof (int) *last_basic_block);
692 bitmap current_all_blocks = BITMAP_ALLOC (NULL);
697 n_blocks = post_order_compute (postorder, true);
699 if (n_blocks != n_basic_blocks)
700 delete_unreachable_blocks ();
702 for (i = 0; i < n_blocks; i++)
703 bitmap_set_bit (current_all_blocks, postorder[i]);
705 /* No one called df_rescan_blocks, so do it. */
706 if (!df->blocks_to_scan)
707 df_rescan_blocks (df, NULL);
709 /* Make sure that we have pruned any unreachable blocks from these
711 bitmap_and_into (df->blocks_to_scan, current_all_blocks);
713 if (df->blocks_to_analyze)
716 bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
717 n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
718 BITMAP_FREE (current_all_blocks);
723 df->blocks_to_analyze = current_all_blocks;
724 current_all_blocks = NULL;
727 /* Skip over the DF_SCAN problem. */
728 for (i = 1; i < df->num_problems_defined; i++)
729 df_analyze_problem (df->problems_in_order[i],
730 df->blocks_to_analyze, df->blocks_to_analyze,
732 postorder, n_blocks, false);
736 BITMAP_FREE (df->blocks_to_analyze);
737 df->blocks_to_analyze = NULL;
740 BITMAP_FREE (df->blocks_to_scan);
741 df->blocks_to_scan = NULL;
746 /*----------------------------------------------------------------------------
747 Functions to support limited incremental change.
748 ----------------------------------------------------------------------------*/
751 /* Get basic block info. */
754 df_get_bb_info (struct dataflow *dflow, unsigned int index)
756 return (struct df_scan_bb_info *) dflow->block_info[index];
760 /* Set basic block info. */
763 df_set_bb_info (struct dataflow *dflow, unsigned int index,
766 dflow->block_info[index] = bb_info;
770 /* Called from the rtl_compact_blocks to reorganize the problems basic
774 df_compact_blocks (struct df *df)
778 void **problem_temps;
779 int size = last_basic_block *sizeof (void *);
780 problem_temps = xmalloc (size);
782 for (p = 0; p < df->num_problems_defined; p++)
784 struct dataflow *dflow = df->problems_in_order[p];
785 if (*dflow->problem->free_bb_fun)
787 df_grow_bb_info (dflow);
788 memcpy (problem_temps, dflow->block_info, size);
790 /* Copy the bb info from the problem tmps to the proper
791 place in the block_info vector. Null out the copied
793 i = NUM_FIXED_BLOCKS;
796 df_set_bb_info (dflow, i, problem_temps[bb->index]);
797 problem_temps[bb->index] = NULL;
800 memset (dflow->block_info + i, 0,
801 (last_basic_block - i) *sizeof (void *));
803 /* Free any block infos that were not copied (and NULLed).
804 These are from orphaned blocks. */
805 for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
807 basic_block bb = BASIC_BLOCK (i);
808 if (problem_temps[i] && bb)
809 (*dflow->problem->free_bb_fun)
810 (dflow, bb, problem_temps[i]);
815 free (problem_temps);
817 i = NUM_FIXED_BLOCKS;
820 SET_BASIC_BLOCK (i, bb);
825 gcc_assert (i == n_basic_blocks);
827 for (; i < last_basic_block; i++)
828 SET_BASIC_BLOCK (i, NULL);
832 /* Shove NEW_BLOCK in at OLD_INDEX. Called from if-cvt to hack a
833 block. There is no excuse for people to do this kind of thing. */
836 df_bb_replace (struct df *df, int old_index, basic_block new_block)
840 for (p = 0; p < df->num_problems_defined; p++)
842 struct dataflow *dflow = df->problems_in_order[p];
843 if (dflow->block_info)
847 df_grow_bb_info (dflow);
849 /* The old switcheroo. */
851 temp = df_get_bb_info (dflow, old_index);
852 df_set_bb_info (dflow, old_index,
853 df_get_bb_info (dflow, new_block->index));
854 df_set_bb_info (dflow, new_block->index, temp);
858 SET_BASIC_BLOCK (old_index, new_block);
859 new_block->index = old_index;
862 /*----------------------------------------------------------------------------
863 PUBLIC INTERFACES TO QUERY INFORMATION.
864 ----------------------------------------------------------------------------*/
867 /* Return last use of REGNO within BB. */
870 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
875 FOR_BB_INSNS_REVERSE (bb, insn)
877 unsigned int uid = INSN_UID (insn);
878 for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
879 if (DF_REF_REGNO (use) == regno)
886 /* Return first def of REGNO within BB. */
889 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
894 FOR_BB_INSNS (bb, insn)
896 unsigned int uid = INSN_UID (insn);
897 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
898 if (DF_REF_REGNO (def) == regno)
905 /* Return last def of REGNO within BB. */
908 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
913 FOR_BB_INSNS_REVERSE (bb, insn)
915 unsigned int uid = INSN_UID (insn);
917 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
918 if (DF_REF_REGNO (def) == regno)
925 /* Return true if INSN defines REGNO. */
928 df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
933 uid = INSN_UID (insn);
934 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
935 if (DF_REF_REGNO (def) == regno)
942 /* Finds the reference corresponding to the definition of REG in INSN.
943 DF is the dataflow object. */
946 df_find_def (struct df *df, rtx insn, rtx reg)
951 if (GET_CODE (reg) == SUBREG)
952 reg = SUBREG_REG (reg);
953 gcc_assert (REG_P (reg));
955 uid = INSN_UID (insn);
956 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
957 if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
964 /* Return true if REG is defined in INSN, zero otherwise. */
967 df_reg_defined (struct df *df, rtx insn, rtx reg)
969 return df_find_def (df, insn, reg) != NULL;
973 /* Finds the reference corresponding to the use of REG in INSN.
974 DF is the dataflow object. */
977 df_find_use (struct df *df, rtx insn, rtx reg)
982 if (GET_CODE (reg) == SUBREG)
983 reg = SUBREG_REG (reg);
984 gcc_assert (REG_P (reg));
986 uid = INSN_UID (insn);
987 for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
988 if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
995 /* Return true if REG is referenced in INSN, zero otherwise. */
998 df_reg_used (struct df *df, rtx insn, rtx reg)
1000 return df_find_use (df, insn, reg) != NULL;
1004 /*----------------------------------------------------------------------------
1005 Debugging and printing functions.
1006 ----------------------------------------------------------------------------*/
1008 /* Dump dataflow info. */
1010 df_dump (struct df *df, FILE *file)
1017 fprintf (file, "\n\n%s\n", current_function_name ());
1018 fprintf (file, "\nDataflow summary:\n");
1019 fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
1020 df->def_info.bitmap_size, df->use_info.bitmap_size);
1022 for (i = 0; i < df->num_problems_defined; i++)
1023 (*df->problems_in_order[i]->problem->dump_fun) (df->problems_in_order[i], file);
1025 fprintf (file, "\n");
1030 df_refs_chain_dump (struct df *df, struct df_ref *ref,
1031 bool follow_chain, FILE *file)
1033 fprintf (file, "{ ");
1036 fprintf (file, "%c%d(%d) ",
1037 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1039 DF_REF_REGNO (ref));
1041 df_chain_dump (df, DF_REF_CHAIN (ref), file);
1042 ref = ref->next_ref;
1044 fprintf (file, "}");
1048 /* Dump either a ref-def or reg-use chain. */
1051 df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref, FILE *file)
1053 fprintf (file, "{ ");
1056 fprintf (file, "%c%d(%d) ",
1057 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1059 DF_REF_REGNO (ref));
1060 ref = ref->next_reg;
1062 fprintf (file, "}");
1067 df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
1072 uid = INSN_UID (insn);
1074 if (DF_INSN_UID_DEFS (df, uid))
1075 bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1076 else if (DF_INSN_UID_USES(df, uid))
1077 bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1081 fprintf (file, "insn %d bb %d luid %d defs ",
1082 uid, bbi, DF_INSN_LUID (df, insn));
1084 df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
1085 fprintf (file, " defs ");
1086 df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
1087 fprintf (file, "\n");
1091 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
1096 uid = INSN_UID (insn);
1097 if (DF_INSN_UID_DEFS (df, uid))
1098 bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1099 else if (DF_INSN_UID_USES(df, uid))
1100 bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1104 fprintf (file, "insn %d bb %d luid %d defs ",
1105 uid, bbi, DF_INSN_LUID (df, insn));
1106 df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
1108 fprintf (file, " uses ");
1109 df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
1110 fprintf (file, "\n");
1114 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
1116 fprintf (file, "reg %d defs ", regno);
1117 df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
1118 fprintf (file, " uses ");
1119 df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
1120 fprintf (file, "\n");
1125 df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
1127 fprintf (file, "%c%d ",
1128 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1130 fprintf (file, "reg %d bb %d luid %d insn %d chain ",
1133 DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
1134 DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
1135 df_chain_dump (df, DF_REF_CHAIN (ref), file);
1136 fprintf (file, "\n");
1139 /* Functions for debugging from GDB. */
1142 debug_df_insn (rtx insn)
1144 df_insn_debug (ddf, insn, true, stderr);
1150 debug_df_reg (rtx reg)
1152 df_regno_debug (ddf, REGNO (reg), stderr);
1157 debug_df_regno (unsigned int regno)
1159 df_regno_debug (ddf, regno, stderr);
1164 debug_df_ref (struct df_ref *ref)
1166 df_ref_debug (ddf, ref, stderr);
1171 debug_df_defno (unsigned int defno)
1173 df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
1178 debug_df_useno (unsigned int defno)
1180 df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
1185 debug_df_chain (struct df_link *link)
1187 df_chain_dump (ddf, link, stderr);
1188 fputc ('\n', stderr);