1 /* Allocation for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
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 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
28 The files in this collection (df*.c,df.h) provide a general framework
29 for solving dataflow problems. The global dataflow is performed using
30 a good implementation of iterative dataflow analysis.
32 The file df-problems.c provides problem instance for the most common
33 dataflow problems: reaching defs, upward exposed uses, live variables,
34 uninitialized variables, def-use chains, and use-def chains. However,
35 the interface allows other dataflow problems to be defined as well.
40 Here is an example of using the dataflow routines.
44 df = df_init (init_flags);
46 df_add_problem (df, problem, flags);
48 df_set_blocks (df, blocks);
50 df_rescan_blocks (df, blocks);
60 DF_INIT simply creates a poor man's object (df) that needs to be
61 passed to all the dataflow routines. df_finish destroys this object
62 and frees up any allocated memory.
64 There are three flags that can be passed to df_init, each of these
65 flags controls the scanning of the rtl:
67 DF_HARD_REGS means that the scanning is to build information about
68 both pseudo registers and hardware registers. Without this
69 information, the problems will be solved only on pseudo registers.
70 DF_EQUIV_NOTES marks the uses present in EQUIV/EQUAL notes.
71 DF_SUBREGS return subregs rather than the inner reg.
74 DF_ADD_PROBLEM adds a problem, defined by an instance to struct
75 df_problem, to the set of problems solved in this instance of df. All
76 calls to add a problem for a given instance of df must occur before
77 the first call to DF_RESCAN_BLOCKS, DF_SET_BLOCKS or DF_ANALYZE.
79 For all of the problems defined in df-problems.c, there are
80 convenience functions named DF_*_ADD_PROBLEM.
83 Problems can be dependent on other problems. For instance, solving
84 def-use or use-def chains is dependent on solving reaching
85 definitions. As long as these dependencies are listed in the problem
86 definition, the order of adding the problems is not material.
87 Otherwise, the problems will be solved in the order of calls to
88 df_add_problem. Note that it is not necessary to have a problem. In
89 that case, df will just be used to do the scanning.
93 DF_SET_BLOCKS is an optional call used to define a region of the
94 function on which the analysis will be performed. The normal case is
95 to analyze the entire function and no call to df_set_blocks is made.
97 When a subset is given, the analysis behaves as if the function only
98 contains those blocks and any edges that occur directly between the
99 blocks in the set. Care should be taken to call df_set_blocks right
100 before the call to analyze in order to eliminate the possibility that
101 optimizations that reorder blocks invalidate the bitvector.
105 DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
106 (re)run over the set of blocks passed in. If blocks is NULL, the entire
107 function (or all of the blocks defined in df_set_blocks) is rescanned.
108 If blocks contains blocks that were not defined in the call to
109 df_set_blocks, these blocks are added to the set of blocks.
112 DF_ANALYZE causes all of the defined problems to be (re)solved. It
113 does not cause blocks to be (re)scanned at the rtl level unless no
114 prior call is made to df_rescan_blocks. When DF_ANALYZE is completes,
115 the IN and OUT sets for each basic block contain the computer
116 information. The DF_*_BB_INFO macros can be used to access these
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 information 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 both at the beginning and ends of blocks.
210 For blocks that area at the destination of eh edges, the
211 artificial uses and defs occur at the beginning. The defs relate
212 to the registers specified in EH_RETURN_DATA_REGNO and the uses
213 relate to the registers specified in ED_USES. Logically these
214 defs and uses should really occur along the eh edge, but there is
215 no convenient way to do this. Artificial edges that occur at the
216 beginning of the block have the DF_REF_AT_TOP flag set.
218 Artificial uses occur at the end of all blocks. These arise from
219 the hard registers that are always live, such as the stack
220 register and are put there to keep the code from forgetting about
223 Artificial defs occur at the end of the entry block. These arise
224 from registers that are live at entry to the function.
226 2) All of the uses and defs associated with each pseudo or hard
227 register are linked in a bidirectional chain. These are called
228 reg-use or reg_def chains.
230 The first use (or def) for a register can be obtained using the
231 DF_REG_USE_GET macro (or DF_REG_DEF_GET macro). Subsequent uses
232 for the same regno can be obtained by following the next_reg field
235 In previous versions of this code, these chains were ordered. It
236 has not been practical to continue this practice.
238 3) If def-use or use-def chains are built, these can be traversed to
241 4) An array of all of the uses (and an array of all of the defs) can
242 be built. These arrays are indexed by the value in the id
243 structure. These arrays are only lazily kept up to date, and that
244 process can be expensive. To have these arrays built, call
245 df_reorganize_refs. Note that the values in the id field of a ref
246 may change across calls to df_analyze or df_reorganize refs.
248 If the only use of this array is to find all of the refs, it is
249 better to traverse all of the registers and then traverse all of
250 reg-use or reg-def chains.
256 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
257 both a use and a def. These are both marked read/write to show that they
258 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
259 will generate a use of reg 42 followed by a def of reg 42 (both marked
260 read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
261 generates a use of reg 41 then a def of reg 41 (both marked read/write),
262 even though reg 41 is decremented before it is used for the memory
263 address in this second example.
265 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
266 for which the number of word_mode units covered by the outer mode is
267 smaller than that covered by the inner mode, invokes a read-modify-write.
268 operation. We generate both a use and a def and again mark them
271 Paradoxical subreg writes do not leave a trace of the old content, so they
272 are write-only operations.
278 #include "coretypes.h"
282 #include "insn-config.h"
284 #include "function.h"
287 #include "alloc-pool.h"
289 #include "hard-reg-set.h"
290 #include "basic-block.h"
295 #include "tree-pass.h"
297 static struct df
*ddf
= NULL
;
298 struct df
*shared_df
= NULL
;
300 static void *df_get_bb_info (struct dataflow
*, unsigned int);
301 static void df_set_bb_info (struct dataflow
*, unsigned int, void *);
302 /*----------------------------------------------------------------------------
303 Functions to create, destroy and manipulate an instance of df.
304 ----------------------------------------------------------------------------*/
307 /* Initialize dataflow analysis and allocate and initialize dataflow
313 struct df
*df
= XCNEW (struct df
);
315 /* This is executed once per compilation to initialize platform
316 specific data structures. */
319 /* All df instance must define the scanning problem. */
320 df_scan_add_problem (df
, flags
);
325 /* Add PROBLEM to the DF instance. */
328 df_add_problem (struct df
*df
, struct df_problem
*problem
, int flags
)
330 struct dataflow
*dflow
;
332 /* First try to add the dependent problem. */
333 if (problem
->dependent_problem_fun
)
334 (problem
->dependent_problem_fun
) (df
, 0);
336 /* Check to see if this problem has already been defined. If it
337 has, just return that instance, if not, add it to the end of the
339 dflow
= df
->problems_by_index
[problem
->id
];
343 /* Make a new one and add it to the end. */
344 dflow
= XCNEW (struct dataflow
);
345 dflow
->flags
= flags
;
347 dflow
->problem
= problem
;
348 df
->problems_in_order
[df
->num_problems_defined
++] = dflow
;
349 df
->problems_by_index
[dflow
->problem
->id
] = dflow
;
355 /* Set the MASK flags in the DFLOW problem. The old flags are
356 returned. If a flag is not allowed to be changed this will fail if
357 checking is enabled. */
359 df_set_flags (struct dataflow
*dflow
, int mask
)
361 int old_flags
= dflow
->flags
;
363 gcc_assert (!(mask
& (~dflow
->problem
->changeable_flags
)));
365 dflow
->flags
|= mask
;
370 /* Clear the MASK flags in the DFLOW problem. The old flags are
371 returned. If a flag is not allowed to be changed this will fail if
372 checking is enabled. */
374 df_clear_flags (struct dataflow
*dflow
, int mask
)
376 int old_flags
= dflow
->flags
;
378 gcc_assert (!(mask
& (~dflow
->problem
->changeable_flags
)));
380 dflow
->flags
&= !mask
;
385 /* Set the blocks that are to be considered for analysis. If this is
386 not called or is called with null, the entire function in
390 df_set_blocks (struct df
*df
, bitmap blocks
)
394 if (df
->blocks_to_analyze
)
397 bitmap diff
= BITMAP_ALLOC (NULL
);
398 bitmap_and_compl (diff
, df
->blocks_to_analyze
, blocks
);
399 for (p
= df
->num_problems_defined
- 1; p
>= 0 ;p
--)
401 struct dataflow
*dflow
= df
->problems_in_order
[p
];
402 if (dflow
->problem
->reset_fun
)
403 dflow
->problem
->reset_fun (dflow
, df
->blocks_to_analyze
);
404 else if (dflow
->problem
->free_bb_fun
)
407 unsigned int bb_index
;
409 EXECUTE_IF_SET_IN_BITMAP (diff
, 0, bb_index
, bi
)
411 basic_block bb
= BASIC_BLOCK (bb_index
);
414 dflow
->problem
->free_bb_fun
415 (dflow
, bb
, df_get_bb_info (dflow
, bb_index
));
416 df_set_bb_info (dflow
, bb_index
, NULL
);
426 /* If we have not actually run scanning before, do not try
427 to clear anything. */
428 struct dataflow
*scan_dflow
= df
->problems_by_index
[DF_SCAN
];
429 if (scan_dflow
->problem_data
)
431 bitmap blocks_to_reset
= NULL
;
433 for (p
= df
->num_problems_defined
- 1; p
>= 0 ;p
--)
435 struct dataflow
*dflow
= df
->problems_in_order
[p
];
436 if (dflow
->problem
->reset_fun
)
438 if (!blocks_to_reset
)
441 blocks_to_reset
= BITMAP_ALLOC (NULL
);
444 bitmap_set_bit (blocks_to_reset
, bb
->index
);
447 dflow
->problem
->reset_fun (dflow
, blocks_to_reset
);
451 BITMAP_FREE (blocks_to_reset
);
453 df
->blocks_to_analyze
= BITMAP_ALLOC (NULL
);
455 bitmap_copy (df
->blocks_to_analyze
, blocks
);
459 if (df
->blocks_to_analyze
)
461 BITMAP_FREE (df
->blocks_to_analyze
);
462 df
->blocks_to_analyze
= NULL
;
468 /* Free all of the per basic block dataflow from all of the problems.
469 This is typically called before a basic block is deleted and the
470 problem will be reanalyzed. */
473 df_delete_basic_block (struct df
*df
, int bb_index
)
475 basic_block bb
= BASIC_BLOCK (bb_index
);
478 for (i
= 0; i
< df
->num_problems_defined
; i
++)
480 struct dataflow
*dflow
= df
->problems_in_order
[i
];
481 if (dflow
->problem
->free_bb_fun
)
482 dflow
->problem
->free_bb_fun
483 (dflow
, bb
, df_get_bb_info (dflow
, bb_index
));
488 /* Free all the dataflow info and the DF structure. This should be
489 called from the df_finish macro which also NULLs the parm. */
492 df_finish1 (struct df
*df
)
496 for (i
= 0; i
< df
->num_problems_defined
; i
++)
497 df
->problems_in_order
[i
]->problem
->free_fun (df
->problems_in_order
[i
]);
503 /*----------------------------------------------------------------------------
504 The general data flow analysis engine.
505 ----------------------------------------------------------------------------*/
508 /* Hybrid search algorithm from "Implementation Techniques for
509 Efficient Data-Flow Analysis of Large Programs". */
512 df_hybrid_search_forward (basic_block bb
,
513 struct dataflow
*dataflow
,
521 SET_BIT (dataflow
->visited
, bb
->index
);
522 gcc_assert (TEST_BIT (dataflow
->pending
, bb
->index
));
523 RESET_BIT (dataflow
->pending
, i
);
525 /* Calculate <conf_op> of predecessor_outs. */
526 if (EDGE_COUNT (bb
->preds
) > 0)
527 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
529 if (!TEST_BIT (dataflow
->considered
, e
->src
->index
))
532 dataflow
->problem
->con_fun_n (dataflow
, e
);
534 else if (dataflow
->problem
->con_fun_0
)
535 dataflow
->problem
->con_fun_0 (dataflow
, bb
);
537 result_changed
= dataflow
->problem
->trans_fun (dataflow
, i
);
539 if (!result_changed
|| single_pass
)
542 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
544 if (e
->dest
->index
== i
)
546 if (!TEST_BIT (dataflow
->considered
, e
->dest
->index
))
548 SET_BIT (dataflow
->pending
, e
->dest
->index
);
551 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
553 if (e
->dest
->index
== i
)
556 if (!TEST_BIT (dataflow
->considered
, e
->dest
->index
))
558 if (!TEST_BIT (dataflow
->visited
, e
->dest
->index
))
559 df_hybrid_search_forward (e
->dest
, dataflow
, single_pass
);
564 df_hybrid_search_backward (basic_block bb
,
565 struct dataflow
*dataflow
,
573 SET_BIT (dataflow
->visited
, bb
->index
);
574 gcc_assert (TEST_BIT (dataflow
->pending
, bb
->index
));
575 RESET_BIT (dataflow
->pending
, i
);
577 /* Calculate <conf_op> of predecessor_outs. */
578 if (EDGE_COUNT (bb
->succs
) > 0)
579 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
581 if (!TEST_BIT (dataflow
->considered
, e
->dest
->index
))
584 dataflow
->problem
->con_fun_n (dataflow
, e
);
586 else if (dataflow
->problem
->con_fun_0
)
587 dataflow
->problem
->con_fun_0 (dataflow
, bb
);
589 result_changed
= dataflow
->problem
->trans_fun (dataflow
, i
);
591 if (!result_changed
|| single_pass
)
594 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
596 if (e
->src
->index
== i
)
599 if (!TEST_BIT (dataflow
->considered
, e
->src
->index
))
602 SET_BIT (dataflow
->pending
, e
->src
->index
);
605 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
607 if (e
->src
->index
== i
)
610 if (!TEST_BIT (dataflow
->considered
, e
->src
->index
))
613 if (!TEST_BIT (dataflow
->visited
, e
->src
->index
))
614 df_hybrid_search_backward (e
->src
, dataflow
, single_pass
);
619 /* This function will perform iterative bitvector dataflow described
620 by DATAFLOW, producing the in and out sets. Only the part of the
621 cfg induced by blocks in DATAFLOW->order is taken into account.
623 SINGLE_PASS is true if you just want to make one pass over the
627 df_iterative_dataflow (struct dataflow
*dataflow
,
628 bitmap blocks_to_consider
, bitmap blocks_to_init
,
629 int *blocks_in_postorder
, int n_blocks
,
634 sbitmap visited
= sbitmap_alloc (last_basic_block
);
635 sbitmap pending
= sbitmap_alloc (last_basic_block
);
636 sbitmap considered
= sbitmap_alloc (last_basic_block
);
639 dataflow
->visited
= visited
;
640 dataflow
->pending
= pending
;
641 dataflow
->considered
= considered
;
643 sbitmap_zero (visited
);
644 sbitmap_zero (pending
);
645 sbitmap_zero (considered
);
647 gcc_assert (dataflow
->problem
->dir
);
649 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider
, 0, idx
, bi
)
651 SET_BIT (considered
, idx
);
654 for (i
= 0; i
< n_blocks
; i
++)
656 idx
= blocks_in_postorder
[i
];
657 SET_BIT (pending
, idx
);
660 dataflow
->problem
->init_fun (dataflow
, blocks_to_init
);
665 /* For forward problems, you want to pass in reverse postorder
666 and for backward problems you want postorder. This has been
667 shown to be as good as you can do by several people, the
668 first being Mathew Hecht in his phd dissertation.
670 The nodes are passed into this function in postorder. */
672 if (dataflow
->problem
->dir
== DF_FORWARD
)
674 for (i
= n_blocks
- 1 ; i
>= 0 ; i
--)
676 idx
= blocks_in_postorder
[i
];
678 if (TEST_BIT (pending
, idx
) && !TEST_BIT (visited
, idx
))
679 df_hybrid_search_forward (BASIC_BLOCK (idx
), dataflow
, single_pass
);
684 for (i
= 0; i
< n_blocks
; i
++)
686 idx
= blocks_in_postorder
[i
];
688 if (TEST_BIT (pending
, idx
) && !TEST_BIT (visited
, idx
))
689 df_hybrid_search_backward (BASIC_BLOCK (idx
), dataflow
, single_pass
);
693 if (sbitmap_first_set_bit (pending
) == -1)
696 sbitmap_zero (visited
);
699 sbitmap_free (pending
);
700 sbitmap_free (visited
);
701 sbitmap_free (considered
);
705 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
706 the order of the remaining entries. Returns the length of the resulting
710 df_prune_to_subcfg (int list
[], unsigned len
, bitmap blocks
)
714 for (act
= 0, last
= 0; act
< len
; act
++)
715 if (bitmap_bit_p (blocks
, list
[act
]))
716 list
[last
++] = list
[act
];
722 /* Execute dataflow analysis on a single dataflow problem.
724 There are three sets of blocks passed in:
726 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
727 examined or will be computed. For calls from DF_ANALYZE, this is
728 the set of blocks that has been passed to DF_SET_BLOCKS. For calls
729 from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
730 blocks in the fringe (the set of blocks passed in plus the set of
731 immed preds and succs of those blocks).
733 BLOCKS_TO_INIT are the blocks whose solution will be changed by
734 this iteration. For calls from DF_ANALYZE, this is the set of
735 blocks that has been passed to DF_SET_BLOCKS. For calls from
736 DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
739 BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
740 For calls from DF_ANALYZE, this is the accumulated set of blocks
741 that has been passed to DF_RESCAN_BLOCKS since the last call to
742 DF_ANALYZE. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
743 this is the set of blocks passed in.
745 blocks_to_consider blocks_to_init blocks_to_scan
746 full redo all all all
747 partial redo all all sub
748 small fixup fringe sub sub
752 df_analyze_problem (struct dataflow
*dflow
,
753 bitmap blocks_to_consider
,
754 bitmap blocks_to_init
,
755 bitmap blocks_to_scan
,
756 int *postorder
, int n_blocks
, bool single_pass
)
758 /* (Re)Allocate the datastructures necessary to solve the problem. */
759 if (dflow
->problem
->alloc_fun
)
760 dflow
->problem
->alloc_fun (dflow
, blocks_to_scan
, blocks_to_init
);
762 /* Set up the problem and compute the local information. This
763 function is passed both the blocks_to_consider and the
764 blocks_to_scan because the RD and RU problems require the entire
765 function to be rescanned if they are going to be updated. */
766 if (dflow
->problem
->local_compute_fun
)
767 dflow
->problem
->local_compute_fun (dflow
, blocks_to_consider
, blocks_to_scan
);
769 /* Solve the equations. */
770 if (dflow
->problem
->dataflow_fun
)
771 dflow
->problem
->dataflow_fun (dflow
, blocks_to_consider
, blocks_to_init
,
772 postorder
, n_blocks
, single_pass
);
774 /* Massage the solution. */
775 if (dflow
->problem
->finalize_fun
)
776 dflow
->problem
->finalize_fun (dflow
, blocks_to_consider
);
780 /* Analyze dataflow info for the basic blocks specified by the bitmap
781 BLOCKS, or for the whole CFG if BLOCKS is zero. */
784 df_analyze (struct df
*df
)
786 int *postorder
= XNEWVEC (int, last_basic_block
);
787 bitmap current_all_blocks
= BITMAP_ALLOC (NULL
);
792 n_blocks
= post_order_compute (postorder
, true);
794 if (n_blocks
!= n_basic_blocks
)
795 delete_unreachable_blocks ();
797 for (i
= 0; i
< n_blocks
; i
++)
798 bitmap_set_bit (current_all_blocks
, postorder
[i
]);
800 /* No one called df_rescan_blocks, so do it. */
801 if (!df
->blocks_to_scan
)
802 df_rescan_blocks (df
, NULL
);
804 /* Make sure that we have pruned any unreachable blocks from these
806 bitmap_and_into (df
->blocks_to_scan
, current_all_blocks
);
808 if (df
->blocks_to_analyze
)
811 bitmap_and_into (df
->blocks_to_analyze
, current_all_blocks
);
812 n_blocks
= df_prune_to_subcfg (postorder
, n_blocks
, df
->blocks_to_analyze
);
813 BITMAP_FREE (current_all_blocks
);
818 df
->blocks_to_analyze
= current_all_blocks
;
819 current_all_blocks
= NULL
;
822 /* Skip over the DF_SCAN problem. */
823 for (i
= 1; i
< df
->num_problems_defined
; i
++)
824 df_analyze_problem (df
->problems_in_order
[i
],
825 df
->blocks_to_analyze
, df
->blocks_to_analyze
,
827 postorder
, n_blocks
, false);
831 BITMAP_FREE (df
->blocks_to_analyze
);
832 df
->blocks_to_analyze
= NULL
;
835 BITMAP_FREE (df
->blocks_to_scan
);
836 df
->blocks_to_scan
= NULL
;
842 /*----------------------------------------------------------------------------
843 Functions to support limited incremental change.
844 ----------------------------------------------------------------------------*/
847 /* Get basic block info. */
850 df_get_bb_info (struct dataflow
*dflow
, unsigned int index
)
852 return (struct df_scan_bb_info
*) dflow
->block_info
[index
];
856 /* Set basic block info. */
859 df_set_bb_info (struct dataflow
*dflow
, unsigned int index
,
862 dflow
->block_info
[index
] = bb_info
;
866 /* Called from the rtl_compact_blocks to reorganize the problems basic
870 df_compact_blocks (struct df
*df
)
874 void **problem_temps
;
875 int size
= last_basic_block
*sizeof (void *);
876 problem_temps
= xmalloc (size
);
878 for (p
= 0; p
< df
->num_problems_defined
; p
++)
880 struct dataflow
*dflow
= df
->problems_in_order
[p
];
881 if (dflow
->problem
->free_bb_fun
)
883 df_grow_bb_info (dflow
);
884 memcpy (problem_temps
, dflow
->block_info
, size
);
886 /* Copy the bb info from the problem tmps to the proper
887 place in the block_info vector. Null out the copied
889 i
= NUM_FIXED_BLOCKS
;
892 df_set_bb_info (dflow
, i
, problem_temps
[bb
->index
]);
893 problem_temps
[bb
->index
] = NULL
;
896 memset (dflow
->block_info
+ i
, 0,
897 (last_basic_block
- i
) *sizeof (void *));
899 /* Free any block infos that were not copied (and NULLed).
900 These are from orphaned blocks. */
901 for (i
= NUM_FIXED_BLOCKS
; i
< last_basic_block
; i
++)
903 basic_block bb
= BASIC_BLOCK (i
);
904 if (problem_temps
[i
] && bb
)
905 dflow
->problem
->free_bb_fun
906 (dflow
, bb
, problem_temps
[i
]);
911 free (problem_temps
);
913 i
= NUM_FIXED_BLOCKS
;
916 SET_BASIC_BLOCK (i
, bb
);
921 gcc_assert (i
== n_basic_blocks
);
923 for (; i
< last_basic_block
; i
++)
924 SET_BASIC_BLOCK (i
, NULL
);
928 /* Shove NEW_BLOCK in at OLD_INDEX. Called from if-cvt to hack a
929 block. There is no excuse for people to do this kind of thing. */
932 df_bb_replace (struct df
*df
, int old_index
, basic_block new_block
)
936 for (p
= 0; p
< df
->num_problems_defined
; p
++)
938 struct dataflow
*dflow
= df
->problems_in_order
[p
];
939 if (dflow
->block_info
)
943 df_grow_bb_info (dflow
);
945 /* The old switcheroo. */
947 temp
= df_get_bb_info (dflow
, old_index
);
948 df_set_bb_info (dflow
, old_index
,
949 df_get_bb_info (dflow
, new_block
->index
));
950 df_set_bb_info (dflow
, new_block
->index
, temp
);
954 SET_BASIC_BLOCK (old_index
, new_block
);
955 new_block
->index
= old_index
;
958 /*----------------------------------------------------------------------------
959 PUBLIC INTERFACES TO QUERY INFORMATION.
960 ----------------------------------------------------------------------------*/
963 /* Return last use of REGNO within BB. */
966 df_bb_regno_last_use_find (struct df
*df
, basic_block bb
, unsigned int regno
)
972 FOR_BB_INSNS_REVERSE (bb
, insn
)
977 uid
= INSN_UID (insn
);
978 for (use
= DF_INSN_UID_GET (df
, uid
)->uses
; use
; use
= use
->next_ref
)
979 if (DF_REF_REGNO (use
) == regno
)
986 /* Return first def of REGNO within BB. */
989 df_bb_regno_first_def_find (struct df
*df
, basic_block bb
, unsigned int regno
)
995 FOR_BB_INSNS (bb
, insn
)
1000 uid
= INSN_UID (insn
);
1001 for (def
= DF_INSN_UID_GET (df
, uid
)->defs
; def
; def
= def
->next_ref
)
1002 if (DF_REF_REGNO (def
) == regno
)
1009 /* Return last def of REGNO within BB. */
1012 df_bb_regno_last_def_find (struct df
*df
, basic_block bb
, unsigned int regno
)
1018 FOR_BB_INSNS_REVERSE (bb
, insn
)
1023 uid
= INSN_UID (insn
);
1024 for (def
= DF_INSN_UID_GET (df
, uid
)->defs
; def
; def
= def
->next_ref
)
1025 if (DF_REF_REGNO (def
) == regno
)
1032 /* Return true if INSN defines REGNO. */
1035 df_insn_regno_def_p (struct df
*df
, rtx insn
, unsigned int regno
)
1040 uid
= INSN_UID (insn
);
1041 for (def
= DF_INSN_UID_GET (df
, uid
)->defs
; def
; def
= def
->next_ref
)
1042 if (DF_REF_REGNO (def
) == regno
)
1049 /* Finds the reference corresponding to the definition of REG in INSN.
1050 DF is the dataflow object. */
1053 df_find_def (struct df
*df
, rtx insn
, rtx reg
)
1058 if (GET_CODE (reg
) == SUBREG
)
1059 reg
= SUBREG_REG (reg
);
1060 gcc_assert (REG_P (reg
));
1062 uid
= INSN_UID (insn
);
1063 for (def
= DF_INSN_UID_GET (df
, uid
)->defs
; def
; def
= def
->next_ref
)
1064 if (rtx_equal_p (DF_REF_REAL_REG (def
), reg
))
1071 /* Return true if REG is defined in INSN, zero otherwise. */
1074 df_reg_defined (struct df
*df
, rtx insn
, rtx reg
)
1076 return df_find_def (df
, insn
, reg
) != NULL
;
1080 /* Finds the reference corresponding to the use of REG in INSN.
1081 DF is the dataflow object. */
1084 df_find_use (struct df
*df
, rtx insn
, rtx reg
)
1089 if (GET_CODE (reg
) == SUBREG
)
1090 reg
= SUBREG_REG (reg
);
1091 gcc_assert (REG_P (reg
));
1093 uid
= INSN_UID (insn
);
1094 for (use
= DF_INSN_UID_GET (df
, uid
)->uses
; use
; use
= use
->next_ref
)
1095 if (rtx_equal_p (DF_REF_REAL_REG (use
), reg
))
1102 /* Return true if REG is referenced in INSN, zero otherwise. */
1105 df_reg_used (struct df
*df
, rtx insn
, rtx reg
)
1107 return df_find_use (df
, insn
, reg
) != NULL
;
1111 /*----------------------------------------------------------------------------
1112 Debugging and printing functions.
1113 ----------------------------------------------------------------------------*/
1115 /* Dump dataflow info. */
1117 df_dump (struct df
*df
, FILE *file
)
1124 fprintf (file
, "\n\n%s\n", current_function_name ());
1125 fprintf (file
, "\nDataflow summary:\n");
1126 fprintf (file
, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
1127 df
->def_info
.bitmap_size
, df
->use_info
.bitmap_size
);
1129 for (i
= 0; i
< df
->num_problems_defined
; i
++)
1130 df
->problems_in_order
[i
]->problem
->dump_fun (df
->problems_in_order
[i
], file
);
1132 fprintf (file
, "\n");
1137 df_refs_chain_dump (struct df_ref
*ref
, bool follow_chain
, FILE *file
)
1139 fprintf (file
, "{ ");
1142 fprintf (file
, "%c%d(%d) ",
1143 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
1145 DF_REF_REGNO (ref
));
1147 df_chain_dump (DF_REF_CHAIN (ref
), file
);
1148 ref
= ref
->next_ref
;
1150 fprintf (file
, "}");
1154 /* Dump either a ref-def or reg-use chain. */
1157 df_regs_chain_dump (struct df
*df ATTRIBUTE_UNUSED
, struct df_ref
*ref
, FILE *file
)
1159 fprintf (file
, "{ ");
1162 fprintf (file
, "%c%d(%d) ",
1163 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
1165 DF_REF_REGNO (ref
));
1166 ref
= ref
->next_reg
;
1168 fprintf (file
, "}");
1173 df_mws_dump (struct df_mw_hardreg
*mws
, FILE *file
)
1177 struct df_link
*regs
= mws
->regs
;
1178 fprintf (file
, "%c%d(",
1179 (mws
->type
== DF_REF_REG_DEF
) ? 'd' : 'u',
1180 DF_REF_REGNO (regs
->ref
));
1183 fprintf (file
, "%d ", DF_REF_REGNO (regs
->ref
));
1187 fprintf (file
, ") ");
1194 df_insn_uid_debug (struct df
*df
, unsigned int uid
,
1195 bool follow_chain
, FILE *file
)
1199 if (DF_INSN_UID_DEFS (df
, uid
))
1200 bbi
= DF_REF_BBNO (DF_INSN_UID_DEFS (df
, uid
));
1201 else if (DF_INSN_UID_USES(df
, uid
))
1202 bbi
= DF_REF_BBNO (DF_INSN_UID_USES (df
, uid
));
1206 fprintf (file
, "insn %d bb %d luid %d",
1207 uid
, bbi
, DF_INSN_UID_LUID (df
, uid
));
1209 if (DF_INSN_UID_DEFS (df
, uid
))
1211 fprintf (file
, " defs ");
1212 df_refs_chain_dump (DF_INSN_UID_DEFS (df
, uid
), follow_chain
, file
);
1215 if (DF_INSN_UID_USES (df
, uid
))
1217 fprintf (file
, " uses ");
1218 df_refs_chain_dump (DF_INSN_UID_USES (df
, uid
), follow_chain
, file
);
1221 if (DF_INSN_UID_MWS (df
, uid
))
1223 fprintf (file
, " mws ");
1224 df_mws_dump (DF_INSN_UID_MWS (df
, uid
), file
);
1226 fprintf (file
, "\n");
1231 df_insn_debug (struct df
*df
, rtx insn
, bool follow_chain
, FILE *file
)
1233 df_insn_uid_debug (df
, INSN_UID (insn
), follow_chain
, file
);
1237 df_insn_debug_regno (struct df
*df
, rtx insn
, FILE *file
)
1242 uid
= INSN_UID (insn
);
1243 if (DF_INSN_UID_DEFS (df
, uid
))
1244 bbi
= DF_REF_BBNO (DF_INSN_UID_DEFS (df
, uid
));
1245 else if (DF_INSN_UID_USES(df
, uid
))
1246 bbi
= DF_REF_BBNO (DF_INSN_UID_USES (df
, uid
));
1250 fprintf (file
, "insn %d bb %d luid %d defs ",
1251 uid
, bbi
, DF_INSN_LUID (df
, insn
));
1252 df_regs_chain_dump (df
, DF_INSN_UID_DEFS (df
, uid
), file
);
1254 fprintf (file
, " uses ");
1255 df_regs_chain_dump (df
, DF_INSN_UID_USES (df
, uid
), file
);
1256 fprintf (file
, "\n");
1260 df_regno_debug (struct df
*df
, unsigned int regno
, FILE *file
)
1262 fprintf (file
, "reg %d defs ", regno
);
1263 df_regs_chain_dump (df
, DF_REG_DEF_GET (df
, regno
)->reg_chain
, file
);
1264 fprintf (file
, " uses ");
1265 df_regs_chain_dump (df
, DF_REG_USE_GET (df
, regno
)->reg_chain
, file
);
1266 fprintf (file
, "\n");
1271 df_ref_debug (struct df_ref
*ref
, FILE *file
)
1273 fprintf (file
, "%c%d ",
1274 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
1276 fprintf (file
, "reg %d bb %d insn %d flag %x chain ",
1279 DF_REF_INSN (ref
) ? INSN_UID (DF_REF_INSN (ref
)) : -1,
1280 DF_REF_FLAGS (ref
));
1281 df_chain_dump (DF_REF_CHAIN (ref
), file
);
1282 fprintf (file
, "\n");
1285 /* Functions for debugging from GDB. */
1288 debug_df_insn (rtx insn
)
1290 df_insn_debug (ddf
, insn
, true, stderr
);
1296 debug_df_reg (rtx reg
)
1298 df_regno_debug (ddf
, REGNO (reg
), stderr
);
1303 debug_df_regno (unsigned int regno
)
1305 df_regno_debug (ddf
, regno
, stderr
);
1310 debug_df_ref (struct df_ref
*ref
)
1312 df_ref_debug (ref
, stderr
);
1317 debug_df_defno (unsigned int defno
)
1319 df_ref_debug (DF_DEFS_GET (ddf
, defno
), stderr
);
1324 debug_df_useno (unsigned int defno
)
1326 df_ref_debug (DF_USES_GET (ddf
, defno
), stderr
);
1331 debug_df_chain (struct df_link
*link
)
1333 df_chain_dump (link
, stderr
);
1334 fputc ('\n', stderr
);