1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2013 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
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
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/>. */
26 #include "coretypes.h"
30 #include "insn-config.h"
34 #include "alloc-pool.h"
36 #include "hard-reg-set.h"
37 #include "basic-block.h"
48 /* Note that turning REG_DEAD_DEBUGGING on will cause
49 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50 addresses in the dumps. */
51 #define REG_DEAD_DEBUGGING 0
53 #define DF_SPARSE_THRESHOLD 32
55 static bitmap_head seen_in_block
;
56 static bitmap_head seen_in_insn
;
58 /*----------------------------------------------------------------------------
60 ----------------------------------------------------------------------------*/
62 /* A helper function checking if UD/DU is large and dense. It returns true
63 if UD/DU can potentially consume huge amount of memory. Returns false
68 df_check_ud_du_memory_usage (void)
70 /* TODO: make this a target hook. The heuristic applies only to x86 in
71 m32 mode with -Os. In that mode 'push' instruction is used in argument
72 passing, with sp adjustment instruction after each function call. The
73 side effect is that the DU/UD becomes really dense. */
74 #define DF_LARGE_FUNC 20000
77 && n_basic_blocks_for_function (cfun
) > DF_LARGE_FUNC
)
84 /* Generic versions to get the void* version of the block info. Only
85 used inside the problem instance vectors. */
87 /* Dump a def-use or use-def chain for REF to FILE. */
90 df_chain_dump (struct df_link
*link
, FILE *file
)
93 for (; link
; link
= link
->next
)
95 fprintf (file
, "%c%d(bb %d insn %d) ",
96 DF_REF_REG_DEF_P (link
->ref
)
98 : (DF_REF_FLAGS (link
->ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
99 DF_REF_ID (link
->ref
),
100 DF_REF_BBNO (link
->ref
),
101 DF_REF_IS_ARTIFICIAL (link
->ref
)
102 ? -1 : DF_REF_INSN_UID (link
->ref
));
108 /* Print some basic block info as part of df_dump. */
111 df_print_bb_index (basic_block bb
, FILE *file
)
116 fprintf (file
, "\n( ");
117 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
119 basic_block pred
= e
->src
;
120 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
122 fprintf (file
, ")->[%d]->( ", bb
->index
);
123 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
125 basic_block succ
= e
->dest
;
126 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
128 fprintf (file
, ")\n");
132 /*----------------------------------------------------------------------------
135 Find the locations in the function where each definition site for a
136 pseudo reaches. In and out bitvectors are built for each basic
137 block. The id field in the ref is used to index into these sets.
138 See df.h for details.
140 If the DF_RD_PRUNE_DEAD_DEFS changable flag is set, only DEFs reaching
141 existing uses are included in the global reaching DEFs set, or in other
142 words only DEFs that are still live. This is a kind of pruned version
143 of the traditional reaching definitions problem that is much less
144 complex to compute and produces enough information to compute UD-chains.
145 In this context, live must be interpreted in the DF_LR sense: Uses that
146 are upward exposed but maybe not initialized on all paths through the
147 CFG. For a USE that is not reached by a DEF on all paths, we still want
148 to make those DEFs that do reach the USE visible, and pruning based on
149 DF_LIVE would make that impossible.
150 ----------------------------------------------------------------------------*/
152 /* This problem plays a large number of games for the sake of
155 1) The order of the bits in the bitvectors. After the scanning
156 phase, all of the defs are sorted. All of the defs for the reg 0
157 are first, followed by all defs for reg 1 and so on.
159 2) There are two kill sets, one if the number of defs is less or
160 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
163 <= : Data is built directly in the kill set.
165 > : One level of indirection is used to keep from generating long
166 strings of 1 bits in the kill sets. Bitvectors that are indexed
167 by the regnum are used to represent that there is a killing def
168 for the register. The confluence and transfer functions use
169 these along with the bitmap_clear_range call to remove ranges of
170 bits without actually generating a knockout vector.
172 The kill and sparse_kill and the dense_invalidated_by_call and
173 sparse_invalidated_by_call both play this game. */
175 /* Private data used to compute the solution for this problem. These
176 data structures are not accessible outside of this module. */
177 struct df_rd_problem_data
179 /* The set of defs to regs invalidated by call. */
180 bitmap_head sparse_invalidated_by_call
;
181 /* The set of defs to regs invalidate by call for rd. */
182 bitmap_head dense_invalidated_by_call
;
183 /* An obstack for the bitmaps we need for this problem. */
184 bitmap_obstack rd_bitmaps
;
188 /* Free basic block info. */
191 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
194 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
197 bitmap_clear (&bb_info
->kill
);
198 bitmap_clear (&bb_info
->sparse_kill
);
199 bitmap_clear (&bb_info
->gen
);
200 bitmap_clear (&bb_info
->in
);
201 bitmap_clear (&bb_info
->out
);
206 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
207 not touched unless the block is new. */
210 df_rd_alloc (bitmap all_blocks
)
212 unsigned int bb_index
;
214 struct df_rd_problem_data
*problem_data
;
216 if (df_rd
->problem_data
)
218 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
219 bitmap_clear (&problem_data
->sparse_invalidated_by_call
);
220 bitmap_clear (&problem_data
->dense_invalidated_by_call
);
224 problem_data
= XNEW (struct df_rd_problem_data
);
225 df_rd
->problem_data
= problem_data
;
227 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
228 bitmap_initialize (&problem_data
->sparse_invalidated_by_call
,
229 &problem_data
->rd_bitmaps
);
230 bitmap_initialize (&problem_data
->dense_invalidated_by_call
,
231 &problem_data
->rd_bitmaps
);
234 df_grow_bb_info (df_rd
);
236 /* Because of the clustering of all use sites for the same pseudo,
237 we have to process all of the blocks before doing the analysis. */
239 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
241 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
243 /* When bitmaps are already initialized, just clear them. */
244 if (bb_info
->kill
.obstack
)
246 bitmap_clear (&bb_info
->kill
);
247 bitmap_clear (&bb_info
->sparse_kill
);
248 bitmap_clear (&bb_info
->gen
);
252 bitmap_initialize (&bb_info
->kill
, &problem_data
->rd_bitmaps
);
253 bitmap_initialize (&bb_info
->sparse_kill
, &problem_data
->rd_bitmaps
);
254 bitmap_initialize (&bb_info
->gen
, &problem_data
->rd_bitmaps
);
255 bitmap_initialize (&bb_info
->in
, &problem_data
->rd_bitmaps
);
256 bitmap_initialize (&bb_info
->out
, &problem_data
->rd_bitmaps
);
259 df_rd
->optional_p
= true;
263 /* Add the effect of the top artificial defs of BB to the reaching definitions
267 df_rd_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_rd
)
269 int bb_index
= bb
->index
;
271 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
273 df_ref def
= *def_rec
;
274 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
276 unsigned int dregno
= DF_REF_REGNO (def
);
277 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
278 bitmap_clear_range (local_rd
,
279 DF_DEFS_BEGIN (dregno
),
280 DF_DEFS_COUNT (dregno
));
281 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
286 /* Add the effect of the defs of INSN to the reaching definitions bitmap
290 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
293 unsigned uid
= INSN_UID (insn
);
296 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
298 df_ref def
= *def_rec
;
299 unsigned int dregno
= DF_REF_REGNO (def
);
300 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
301 || (dregno
>= FIRST_PSEUDO_REGISTER
))
303 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
304 bitmap_clear_range (local_rd
,
305 DF_DEFS_BEGIN (dregno
),
306 DF_DEFS_COUNT (dregno
));
307 if (!(DF_REF_FLAGS (def
)
308 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
309 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
314 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
315 more complicated than just simulating, because we must produce the
316 gen and kill sets and hence deal with the two possible representations
320 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
326 df_ref def
= *def_rec
;
327 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
329 unsigned int regno
= DF_REF_REGNO (def
);
330 unsigned int begin
= DF_DEFS_BEGIN (regno
);
331 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
333 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
334 || (regno
>= FIRST_PSEUDO_REGISTER
))
336 /* Only the last def(s) for a regno in the block has any
338 if (!bitmap_bit_p (&seen_in_block
, regno
))
340 /* The first def for regno in insn gets to knock out the
341 defs from other instructions. */
342 if ((!bitmap_bit_p (&seen_in_insn
, regno
))
343 /* If the def is to only part of the reg, it does
344 not kill the other defs that reach here. */
345 && (!(DF_REF_FLAGS (def
) &
346 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
348 if (n_defs
> DF_SPARSE_THRESHOLD
)
350 bitmap_set_bit (&bb_info
->sparse_kill
, regno
);
351 bitmap_clear_range(&bb_info
->gen
, begin
, n_defs
);
355 bitmap_set_range (&bb_info
->kill
, begin
, n_defs
);
356 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
360 bitmap_set_bit (&seen_in_insn
, regno
);
361 /* All defs for regno in the instruction may be put into
363 if (!(DF_REF_FLAGS (def
)
364 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
365 bitmap_set_bit (&bb_info
->gen
, DF_REF_ID (def
));
373 /* Compute local reaching def info for basic block BB. */
376 df_rd_bb_local_compute (unsigned int bb_index
)
378 basic_block bb
= BASIC_BLOCK (bb_index
);
379 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
382 bitmap_clear (&seen_in_block
);
383 bitmap_clear (&seen_in_insn
);
385 /* Artificials are only hard regs. */
386 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
387 df_rd_bb_local_compute_process_def (bb_info
,
388 df_get_artificial_defs (bb_index
),
391 FOR_BB_INSNS_REVERSE (bb
, insn
)
393 unsigned int uid
= INSN_UID (insn
);
398 df_rd_bb_local_compute_process_def (bb_info
,
399 DF_INSN_UID_DEFS (uid
), 0);
401 /* This complex dance with the two bitmaps is required because
402 instructions can assign twice to the same pseudo. This
403 generally happens with calls that will have one def for the
404 result and another def for the clobber. If only one vector
405 is used and the clobber goes first, the result will be
407 bitmap_ior_into (&seen_in_block
, &seen_in_insn
);
408 bitmap_clear (&seen_in_insn
);
411 /* Process the artificial defs at the top of the block last since we
412 are going backwards through the block and these are logically at
414 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
415 df_rd_bb_local_compute_process_def (bb_info
,
416 df_get_artificial_defs (bb_index
),
421 /* Compute local reaching def info for each basic block within BLOCKS. */
424 df_rd_local_compute (bitmap all_blocks
)
426 unsigned int bb_index
;
429 struct df_rd_problem_data
*problem_data
430 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
431 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
432 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
434 bitmap_initialize (&seen_in_block
, &df_bitmap_obstack
);
435 bitmap_initialize (&seen_in_insn
, &df_bitmap_obstack
);
437 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
439 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
441 df_rd_bb_local_compute (bb_index
);
444 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
445 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset
, 0, regno
, bi
)
447 if (! HARD_REGISTER_NUM_P (regno
)
448 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
450 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
451 bitmap_set_bit (sparse_invalidated
, regno
);
453 bitmap_set_range (dense_invalidated
,
454 DF_DEFS_BEGIN (regno
),
455 DF_DEFS_COUNT (regno
));
459 bitmap_clear (&seen_in_block
);
460 bitmap_clear (&seen_in_insn
);
464 /* Initialize the solution bit vectors for problem. */
467 df_rd_init_solution (bitmap all_blocks
)
469 unsigned int bb_index
;
472 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
474 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
476 bitmap_copy (&bb_info
->out
, &bb_info
->gen
);
477 bitmap_clear (&bb_info
->in
);
481 /* In of target gets or of out of source. */
484 df_rd_confluence_n (edge e
)
486 bitmap op1
= &df_rd_get_bb_info (e
->dest
->index
)->in
;
487 bitmap op2
= &df_rd_get_bb_info (e
->src
->index
)->out
;
488 bool changed
= false;
490 if (e
->flags
& EDGE_FAKE
)
493 if (e
->flags
& EDGE_EH
)
495 struct df_rd_problem_data
*problem_data
496 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
497 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
498 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
503 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
504 bitmap_copy (&tmp
, op2
);
505 bitmap_and_compl_into (&tmp
, dense_invalidated
);
507 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
509 bitmap_clear_range (&tmp
,
510 DF_DEFS_BEGIN (regno
),
511 DF_DEFS_COUNT (regno
));
513 changed
|= bitmap_ior_into (op1
, &tmp
);
518 return bitmap_ior_into (op1
, op2
);
522 /* Transfer function. */
525 df_rd_transfer_function (int bb_index
)
527 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
530 bitmap in
= &bb_info
->in
;
531 bitmap out
= &bb_info
->out
;
532 bitmap gen
= &bb_info
->gen
;
533 bitmap kill
= &bb_info
->kill
;
534 bitmap sparse_kill
= &bb_info
->sparse_kill
;
535 bool changed
= false;
537 if (bitmap_empty_p (sparse_kill
))
538 changed
= bitmap_ior_and_compl (out
, gen
, in
, kill
);
541 struct df_rd_problem_data
*problem_data
;
544 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
545 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
546 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
547 bitmap_initialize (&tmp
, &problem_data
->rd_bitmaps
);
549 bitmap_copy (&tmp
, in
);
550 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
552 bitmap_clear_range (&tmp
,
553 DF_DEFS_BEGIN (regno
),
554 DF_DEFS_COUNT (regno
));
556 bitmap_and_compl_into (&tmp
, kill
);
557 bitmap_ior_into (&tmp
, gen
);
558 changed
= !bitmap_equal_p (&tmp
, out
);
568 if (df
->changeable_flags
& DF_RD_PRUNE_DEAD_DEFS
)
570 /* Create a mask of DEFs for all registers live at the end of this
571 basic block, and mask out DEFs of registers that are not live.
572 Computing the mask looks costly, but the benefit of the pruning
573 outweighs the cost. */
574 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
575 bitmap regs_live_out
= &df_lr_get_bb_info (bb_index
)->out
;
576 bitmap live_defs
= BITMAP_ALLOC (&df_bitmap_obstack
);
580 EXECUTE_IF_SET_IN_BITMAP (regs_live_out
, 0, regno
, bi
)
581 bitmap_set_range (live_defs
,
582 DF_DEFS_BEGIN (regno
),
583 DF_DEFS_COUNT (regno
));
584 changed
|= bitmap_and_into (&bb_info
->out
, live_defs
);
585 BITMAP_FREE (live_defs
);
591 /* Free all storage associated with the problem. */
596 struct df_rd_problem_data
*problem_data
597 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
601 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
603 df_rd
->block_info_size
= 0;
604 free (df_rd
->block_info
);
605 df_rd
->block_info
= NULL
;
606 free (df_rd
->problem_data
);
612 /* Debugging info. */
615 df_rd_start_dump (FILE *file
)
617 struct df_rd_problem_data
*problem_data
618 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
619 unsigned int m
= DF_REG_SIZE(df
);
622 if (!df_rd
->block_info
)
625 fprintf (file
, ";; Reaching defs:\n");
627 fprintf (file
, ";; sparse invalidated \t");
628 dump_bitmap (file
, &problem_data
->sparse_invalidated_by_call
);
629 fprintf (file
, ";; dense invalidated \t");
630 dump_bitmap (file
, &problem_data
->dense_invalidated_by_call
);
632 fprintf (file
, ";; reg->defs[] map:\t");
633 for (regno
= 0; regno
< m
; regno
++)
634 if (DF_DEFS_COUNT (regno
))
635 fprintf (file
, "%d[%d,%d] ", regno
,
636 DF_DEFS_BEGIN (regno
),
637 DF_DEFS_BEGIN (regno
) + DF_DEFS_COUNT (regno
) - 1);
638 fprintf (file
, "\n");
643 df_rd_dump_defs_set (bitmap defs_set
, const char *prefix
, FILE *file
)
647 unsigned int m
= DF_REG_SIZE(df
);
648 bool first_reg
= true;
650 fprintf (file
, "%s\t(%d) ", prefix
, (int) bitmap_count_bits (defs_set
));
652 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
653 for (regno
= 0; regno
< m
; regno
++)
655 if (HARD_REGISTER_NUM_P (regno
)
656 && (df
->changeable_flags
& DF_NO_HARD_REGS
))
658 bitmap_set_range (&tmp
, DF_DEFS_BEGIN (regno
), DF_DEFS_COUNT (regno
));
659 bitmap_and_into (&tmp
, defs_set
);
660 if (! bitmap_empty_p (&tmp
))
664 bool first_def
= true;
670 fprintf (file
, "%u[", regno
);
671 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, ix
, bi
)
673 fprintf (file
, "%s%u", first_def
? "" : ",", ix
);
681 fprintf (file
, "\n");
685 /* Debugging info at top of bb. */
688 df_rd_top_dump (basic_block bb
, FILE *file
)
690 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
694 df_rd_dump_defs_set (&bb_info
->in
, ";; rd in ", file
);
695 df_rd_dump_defs_set (&bb_info
->gen
, ";; rd gen ", file
);
696 df_rd_dump_defs_set (&bb_info
->kill
, ";; rd kill", file
);
700 /* Debugging info at bottom of bb. */
703 df_rd_bottom_dump (basic_block bb
, FILE *file
)
705 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
709 df_rd_dump_defs_set (&bb_info
->out
, ";; rd out ", file
);
712 /* All of the information associated with every instance of the problem. */
714 static struct df_problem problem_RD
=
716 DF_RD
, /* Problem id. */
717 DF_FORWARD
, /* Direction. */
718 df_rd_alloc
, /* Allocate the problem specific data. */
719 NULL
, /* Reset global information. */
720 df_rd_free_bb_info
, /* Free basic block info. */
721 df_rd_local_compute
, /* Local compute function. */
722 df_rd_init_solution
, /* Init the solution specific data. */
723 df_worklist_dataflow
, /* Worklist solver. */
724 NULL
, /* Confluence operator 0. */
725 df_rd_confluence_n
, /* Confluence operator n. */
726 df_rd_transfer_function
, /* Transfer function. */
727 NULL
, /* Finalize function. */
728 df_rd_free
, /* Free all of the problem information. */
729 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
730 df_rd_start_dump
, /* Debugging. */
731 df_rd_top_dump
, /* Debugging start block. */
732 df_rd_bottom_dump
, /* Debugging end block. */
733 NULL
, /* Debugging start insn. */
734 NULL
, /* Debugging end insn. */
735 NULL
, /* Incremental solution verify start. */
736 NULL
, /* Incremental solution verify end. */
737 NULL
, /* Dependent problem. */
738 sizeof (struct df_rd_bb_info
),/* Size of entry of block_info array. */
739 TV_DF_RD
, /* Timing variable. */
740 true /* Reset blocks on dropping out of blocks_to_analyze. */
745 /* Create a new RD instance and add it to the existing instance
749 df_rd_add_problem (void)
751 df_add_problem (&problem_RD
);
756 /*----------------------------------------------------------------------------
759 Find the locations in the function where any use of a pseudo can
760 reach in the backwards direction. In and out bitvectors are built
761 for each basic block. The regno is used to index into these sets.
762 See df.h for details.
763 ----------------------------------------------------------------------------*/
765 /* Private data used to verify the solution for this problem. */
766 struct df_lr_problem_data
770 /* An obstack for the bitmaps we need for this problem. */
771 bitmap_obstack lr_bitmaps
;
774 /* Free basic block info. */
777 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
780 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
783 bitmap_clear (&bb_info
->use
);
784 bitmap_clear (&bb_info
->def
);
785 bitmap_clear (&bb_info
->in
);
786 bitmap_clear (&bb_info
->out
);
791 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
792 not touched unless the block is new. */
795 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
797 unsigned int bb_index
;
799 struct df_lr_problem_data
*problem_data
;
801 df_grow_bb_info (df_lr
);
802 if (df_lr
->problem_data
)
803 problem_data
= (struct df_lr_problem_data
*) df_lr
->problem_data
;
806 problem_data
= XNEW (struct df_lr_problem_data
);
807 df_lr
->problem_data
= problem_data
;
809 problem_data
->out
= NULL
;
810 problem_data
->in
= NULL
;
811 bitmap_obstack_initialize (&problem_data
->lr_bitmaps
);
814 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
816 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
818 /* When bitmaps are already initialized, just clear them. */
819 if (bb_info
->use
.obstack
)
821 bitmap_clear (&bb_info
->def
);
822 bitmap_clear (&bb_info
->use
);
826 bitmap_initialize (&bb_info
->use
, &problem_data
->lr_bitmaps
);
827 bitmap_initialize (&bb_info
->def
, &problem_data
->lr_bitmaps
);
828 bitmap_initialize (&bb_info
->in
, &problem_data
->lr_bitmaps
);
829 bitmap_initialize (&bb_info
->out
, &problem_data
->lr_bitmaps
);
833 df_lr
->optional_p
= false;
837 /* Reset the global solution for recalculation. */
840 df_lr_reset (bitmap all_blocks
)
842 unsigned int bb_index
;
845 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
847 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
848 gcc_assert (bb_info
);
849 bitmap_clear (&bb_info
->in
);
850 bitmap_clear (&bb_info
->out
);
855 /* Compute local live register info for basic block BB. */
858 df_lr_bb_local_compute (unsigned int bb_index
)
860 basic_block bb
= BASIC_BLOCK (bb_index
);
861 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
866 /* Process the registers set in an exception handler. */
867 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
869 df_ref def
= *def_rec
;
870 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
872 unsigned int dregno
= DF_REF_REGNO (def
);
873 bitmap_set_bit (&bb_info
->def
, dregno
);
874 bitmap_clear_bit (&bb_info
->use
, dregno
);
878 /* Process the hardware registers that are always live. */
879 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
881 df_ref use
= *use_rec
;
882 /* Add use to set of uses in this BB. */
883 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
884 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
887 FOR_BB_INSNS_REVERSE (bb
, insn
)
889 unsigned int uid
= INSN_UID (insn
);
891 if (!NONDEBUG_INSN_P (insn
))
894 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
896 df_ref def
= *def_rec
;
897 /* If the def is to only part of the reg, it does
898 not kill the other defs that reach here. */
899 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
901 unsigned int dregno
= DF_REF_REGNO (def
);
902 bitmap_set_bit (&bb_info
->def
, dregno
);
903 bitmap_clear_bit (&bb_info
->use
, dregno
);
907 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
909 df_ref use
= *use_rec
;
910 /* Add use to set of uses in this BB. */
911 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
915 /* Process the registers set in an exception handler or the hard
916 frame pointer if this block is the target of a non local
918 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
920 df_ref def
= *def_rec
;
921 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
923 unsigned int dregno
= DF_REF_REGNO (def
);
924 bitmap_set_bit (&bb_info
->def
, dregno
);
925 bitmap_clear_bit (&bb_info
->use
, dregno
);
930 /* Process the uses that are live into an exception handler. */
931 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
933 df_ref use
= *use_rec
;
934 /* Add use to set of uses in this BB. */
935 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
936 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
940 /* If the df_live problem is not defined, such as at -O0 and -O1, we
941 still need to keep the luids up to date. This is normally done
942 in the df_live problem since this problem has a forwards
945 df_recompute_luids (bb
);
949 /* Compute local live register info for each basic block within BLOCKS. */
952 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
954 unsigned int bb_index
, i
;
957 bitmap_clear (&df
->hardware_regs_used
);
959 /* The all-important stack pointer must always be live. */
960 bitmap_set_bit (&df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
962 /* Global regs are always live, too. */
963 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
965 bitmap_set_bit (&df
->hardware_regs_used
, i
);
967 /* Before reload, there are a few registers that must be forced
968 live everywhere -- which might not already be the case for
969 blocks within infinite loops. */
970 if (!reload_completed
)
972 unsigned int pic_offset_table_regnum
= PIC_OFFSET_TABLE_REGNUM
;
973 /* Any reference to any pseudo before reload is a potential
974 reference of the frame pointer. */
975 bitmap_set_bit (&df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
977 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
978 /* Pseudos with argument area equivalences may require
979 reloading via the argument pointer. */
980 if (fixed_regs
[ARG_POINTER_REGNUM
])
981 bitmap_set_bit (&df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
984 /* Any constant, or pseudo with constant equivalences, may
985 require reloading from memory using the pic register. */
986 if (pic_offset_table_regnum
!= INVALID_REGNUM
987 && fixed_regs
[pic_offset_table_regnum
])
988 bitmap_set_bit (&df
->hardware_regs_used
, pic_offset_table_regnum
);
991 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
993 if (bb_index
== EXIT_BLOCK
)
995 /* The exit block is special for this problem and its bits are
996 computed from thin air. */
997 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
998 bitmap_copy (&bb_info
->use
, df
->exit_block_uses
);
1001 df_lr_bb_local_compute (bb_index
);
1004 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
1008 /* Initialize the solution vectors. */
1011 df_lr_init (bitmap all_blocks
)
1013 unsigned int bb_index
;
1016 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1018 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1019 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
1020 bitmap_clear (&bb_info
->out
);
1025 /* Confluence function that processes infinite loops. This might be a
1026 noreturn function that throws. And even if it isn't, getting the
1027 unwind info right helps debugging. */
1029 df_lr_confluence_0 (basic_block bb
)
1031 bitmap op1
= &df_lr_get_bb_info (bb
->index
)->out
;
1032 if (bb
!= EXIT_BLOCK_PTR
)
1033 bitmap_copy (op1
, &df
->hardware_regs_used
);
1037 /* Confluence function that ignores fake edges. */
1040 df_lr_confluence_n (edge e
)
1042 bitmap op1
= &df_lr_get_bb_info (e
->src
->index
)->out
;
1043 bitmap op2
= &df_lr_get_bb_info (e
->dest
->index
)->in
;
1044 bool changed
= false;
1046 /* Call-clobbered registers die across exception and call edges. */
1047 /* ??? Abnormal call edges ignored for the moment, as this gets
1048 confused by sibling call edges, which crashes reg-stack. */
1049 if (e
->flags
& EDGE_EH
)
1050 changed
= bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
1052 changed
= bitmap_ior_into (op1
, op2
);
1054 changed
|= bitmap_ior_into (op1
, &df
->hardware_regs_used
);
1059 /* Transfer function. */
1062 df_lr_transfer_function (int bb_index
)
1064 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1065 bitmap in
= &bb_info
->in
;
1066 bitmap out
= &bb_info
->out
;
1067 bitmap use
= &bb_info
->use
;
1068 bitmap def
= &bb_info
->def
;
1070 return bitmap_ior_and_compl (in
, use
, out
, def
);
1074 /* Run the fast dce as a side effect of building LR. */
1077 df_lr_finalize (bitmap all_blocks
)
1079 df_lr
->solutions_dirty
= false;
1080 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1084 /* If dce deletes some instructions, we need to recompute the lr
1085 solution before proceeding further. The problem is that fast
1086 dce is a pessimestic dataflow algorithm. In the case where
1087 it deletes a statement S inside of a loop, the uses inside of
1088 S may not be deleted from the dataflow solution because they
1089 were carried around the loop. While it is conservatively
1090 correct to leave these extra bits, the standards of df
1091 require that we maintain the best possible (least fixed
1092 point) solution. The only way to do that is to redo the
1093 iteration from the beginning. See PR35805 for an
1095 if (df_lr
->solutions_dirty
)
1097 df_clear_flags (DF_LR_RUN_DCE
);
1098 df_lr_alloc (all_blocks
);
1099 df_lr_local_compute (all_blocks
);
1100 df_worklist_dataflow (df_lr
, all_blocks
, df
->postorder
, df
->n_blocks
);
1101 df_lr_finalize (all_blocks
);
1102 df_set_flags (DF_LR_RUN_DCE
);
1108 /* Free all storage associated with the problem. */
1113 struct df_lr_problem_data
*problem_data
1114 = (struct df_lr_problem_data
*) df_lr
->problem_data
;
1115 if (df_lr
->block_info
)
1118 df_lr
->block_info_size
= 0;
1119 free (df_lr
->block_info
);
1120 df_lr
->block_info
= NULL
;
1121 bitmap_obstack_release (&problem_data
->lr_bitmaps
);
1122 free (df_lr
->problem_data
);
1123 df_lr
->problem_data
= NULL
;
1126 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1131 /* Debugging info at top of bb. */
1134 df_lr_top_dump (basic_block bb
, FILE *file
)
1136 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1137 struct df_lr_problem_data
*problem_data
;
1141 fprintf (file
, ";; lr in \t");
1142 df_print_regset (file
, &bb_info
->in
);
1143 if (df_lr
->problem_data
)
1145 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1146 if (problem_data
->in
)
1148 fprintf (file
, ";; old in \t");
1149 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1152 fprintf (file
, ";; lr use \t");
1153 df_print_regset (file
, &bb_info
->use
);
1154 fprintf (file
, ";; lr def \t");
1155 df_print_regset (file
, &bb_info
->def
);
1159 /* Debugging info at bottom of bb. */
1162 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1164 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1165 struct df_lr_problem_data
*problem_data
;
1169 fprintf (file
, ";; lr out \t");
1170 df_print_regset (file
, &bb_info
->out
);
1171 if (df_lr
->problem_data
)
1173 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1174 if (problem_data
->out
)
1176 fprintf (file
, ";; old out \t");
1177 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1183 /* Build the datastructure to verify that the solution to the dataflow
1184 equations is not dirty. */
1187 df_lr_verify_solution_start (void)
1190 struct df_lr_problem_data
*problem_data
;
1191 if (df_lr
->solutions_dirty
)
1194 /* Set it true so that the solution is recomputed. */
1195 df_lr
->solutions_dirty
= true;
1197 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1198 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block
);
1199 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block
);
1203 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->lr_bitmaps
);
1204 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->lr_bitmaps
);
1205 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1206 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1211 /* Compare the saved datastructure and the new solution to the dataflow
1215 df_lr_verify_solution_end (void)
1217 struct df_lr_problem_data
*problem_data
;
1220 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1222 if (!problem_data
->out
)
1225 if (df_lr
->solutions_dirty
)
1226 /* Do not check if the solution is still dirty. See the comment
1227 in df_lr_finalize for details. */
1228 df_lr
->solutions_dirty
= false;
1232 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1233 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1235 /*df_dump (stderr);*/
1240 /* Cannot delete them immediately because you may want to dump them
1241 if the comparison fails. */
1244 bitmap_clear (&problem_data
->in
[bb
->index
]);
1245 bitmap_clear (&problem_data
->out
[bb
->index
]);
1248 free (problem_data
->in
);
1249 free (problem_data
->out
);
1250 problem_data
->in
= NULL
;
1251 problem_data
->out
= NULL
;
1255 /* All of the information associated with every instance of the problem. */
1257 static struct df_problem problem_LR
=
1259 DF_LR
, /* Problem id. */
1260 DF_BACKWARD
, /* Direction. */
1261 df_lr_alloc
, /* Allocate the problem specific data. */
1262 df_lr_reset
, /* Reset global information. */
1263 df_lr_free_bb_info
, /* Free basic block info. */
1264 df_lr_local_compute
, /* Local compute function. */
1265 df_lr_init
, /* Init the solution specific data. */
1266 df_worklist_dataflow
, /* Worklist solver. */
1267 df_lr_confluence_0
, /* Confluence operator 0. */
1268 df_lr_confluence_n
, /* Confluence operator n. */
1269 df_lr_transfer_function
, /* Transfer function. */
1270 df_lr_finalize
, /* Finalize function. */
1271 df_lr_free
, /* Free all of the problem information. */
1272 NULL
, /* Remove this problem from the stack of dataflow problems. */
1273 NULL
, /* Debugging. */
1274 df_lr_top_dump
, /* Debugging start block. */
1275 df_lr_bottom_dump
, /* Debugging end block. */
1276 NULL
, /* Debugging start insn. */
1277 NULL
, /* Debugging end insn. */
1278 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1279 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1280 NULL
, /* Dependent problem. */
1281 sizeof (struct df_lr_bb_info
),/* Size of entry of block_info array. */
1282 TV_DF_LR
, /* Timing variable. */
1283 false /* Reset blocks on dropping out of blocks_to_analyze. */
1287 /* Create a new DATAFLOW instance and add it to an existing instance
1288 of DF. The returned structure is what is used to get at the
1292 df_lr_add_problem (void)
1294 df_add_problem (&problem_LR
);
1295 /* These will be initialized when df_scan_blocks processes each
1297 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
1301 /* Verify that all of the lr related info is consistent and
1305 df_lr_verify_transfer_functions (void)
1308 bitmap_head saved_def
;
1309 bitmap_head saved_use
;
1310 bitmap_head all_blocks
;
1315 bitmap_initialize (&saved_def
, &bitmap_default_obstack
);
1316 bitmap_initialize (&saved_use
, &bitmap_default_obstack
);
1317 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1321 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1322 bitmap_set_bit (&all_blocks
, bb
->index
);
1326 /* Make a copy of the transfer functions and then compute
1327 new ones to see if the transfer functions have
1329 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1332 bitmap_copy (&saved_def
, &bb_info
->def
);
1333 bitmap_copy (&saved_use
, &bb_info
->use
);
1334 bitmap_clear (&bb_info
->def
);
1335 bitmap_clear (&bb_info
->use
);
1337 df_lr_bb_local_compute (bb
->index
);
1338 gcc_assert (bitmap_equal_p (&saved_def
, &bb_info
->def
));
1339 gcc_assert (bitmap_equal_p (&saved_use
, &bb_info
->use
));
1344 /* If we do not have basic block info, the block must be in
1345 the list of dirty blocks or else some one has added a
1346 block behind our backs. */
1347 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1350 /* Make sure no one created a block without following
1352 gcc_assert (df_scan_get_bb_info (bb
->index
));
1355 /* Make sure there are no dirty bits in blocks that have been deleted. */
1356 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1359 bitmap_clear (&saved_def
);
1360 bitmap_clear (&saved_use
);
1361 bitmap_clear (&all_blocks
);
1366 /*----------------------------------------------------------------------------
1367 LIVE AND MUST-INITIALIZED REGISTERS.
1369 This problem first computes the IN and OUT bitvectors for the
1370 must-initialized registers problems, which is a forward problem.
1371 It gives the set of registers for which we MUST have an available
1372 definition on any path from the entry block to the entry/exit of
1373 a basic block. Sets generate a definition, while clobbers kill
1376 In and out bitvectors are built for each basic block and are indexed by
1377 regnum (see df.h for details). In and out bitvectors in struct
1378 df_live_bb_info actually refers to the must-initialized problem;
1380 Then, the in and out sets for the LIVE problem itself are computed.
1381 These are the logical AND of the IN and OUT sets from the LR problem
1382 and the must-initialized problem.
1383 ----------------------------------------------------------------------------*/
1385 /* Private data used to verify the solution for this problem. */
1386 struct df_live_problem_data
1390 /* An obstack for the bitmaps we need for this problem. */
1391 bitmap_obstack live_bitmaps
;
1394 /* Scratch var used by transfer functions. This is used to implement
1395 an optimization to reduce the amount of space used to compute the
1396 combined lr and live analysis. */
1397 static bitmap_head df_live_scratch
;
1400 /* Free basic block info. */
1403 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1406 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1409 bitmap_clear (&bb_info
->gen
);
1410 bitmap_clear (&bb_info
->kill
);
1411 bitmap_clear (&bb_info
->in
);
1412 bitmap_clear (&bb_info
->out
);
1417 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1418 not touched unless the block is new. */
1421 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1423 unsigned int bb_index
;
1425 struct df_live_problem_data
*problem_data
;
1427 if (df_live
->problem_data
)
1428 problem_data
= (struct df_live_problem_data
*) df_live
->problem_data
;
1431 problem_data
= XNEW (struct df_live_problem_data
);
1432 df_live
->problem_data
= problem_data
;
1434 problem_data
->out
= NULL
;
1435 problem_data
->in
= NULL
;
1436 bitmap_obstack_initialize (&problem_data
->live_bitmaps
);
1437 bitmap_initialize (&df_live_scratch
, &problem_data
->live_bitmaps
);
1440 df_grow_bb_info (df_live
);
1442 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1444 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1446 /* When bitmaps are already initialized, just clear them. */
1447 if (bb_info
->kill
.obstack
)
1449 bitmap_clear (&bb_info
->kill
);
1450 bitmap_clear (&bb_info
->gen
);
1454 bitmap_initialize (&bb_info
->kill
, &problem_data
->live_bitmaps
);
1455 bitmap_initialize (&bb_info
->gen
, &problem_data
->live_bitmaps
);
1456 bitmap_initialize (&bb_info
->in
, &problem_data
->live_bitmaps
);
1457 bitmap_initialize (&bb_info
->out
, &problem_data
->live_bitmaps
);
1460 df_live
->optional_p
= (optimize
<= 1);
1464 /* Reset the global solution for recalculation. */
1467 df_live_reset (bitmap all_blocks
)
1469 unsigned int bb_index
;
1472 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1474 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1475 gcc_assert (bb_info
);
1476 bitmap_clear (&bb_info
->in
);
1477 bitmap_clear (&bb_info
->out
);
1482 /* Compute local uninitialized register info for basic block BB. */
1485 df_live_bb_local_compute (unsigned int bb_index
)
1487 basic_block bb
= BASIC_BLOCK (bb_index
);
1488 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1493 FOR_BB_INSNS (bb
, insn
)
1495 unsigned int uid
= INSN_UID (insn
);
1496 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1498 /* Inserting labels does not always trigger the incremental
1502 gcc_assert (!INSN_P (insn
));
1503 insn_info
= df_insn_create_insn_record (insn
);
1506 DF_INSN_INFO_LUID (insn_info
) = luid
;
1511 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
1513 df_ref def
= *def_rec
;
1514 unsigned int regno
= DF_REF_REGNO (def
);
1516 if (DF_REF_FLAGS_IS_SET (def
,
1517 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1518 /* All partial or conditional def
1519 seen are included in the gen set. */
1520 bitmap_set_bit (&bb_info
->gen
, regno
);
1521 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1522 /* Only must clobbers for the entire reg destroy the
1524 bitmap_set_bit (&bb_info
->kill
, regno
);
1525 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1526 bitmap_set_bit (&bb_info
->gen
, regno
);
1530 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1532 df_ref def
= *def_rec
;
1533 bitmap_set_bit (&bb_info
->gen
, DF_REF_REGNO (def
));
1538 /* Compute local uninitialized register info. */
1541 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1543 unsigned int bb_index
;
1546 df_grow_insn_info ();
1548 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1551 df_live_bb_local_compute (bb_index
);
1554 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1558 /* Initialize the solution vectors. */
1561 df_live_init (bitmap all_blocks
)
1563 unsigned int bb_index
;
1566 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1568 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1569 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1571 /* No register may reach a location where it is not used. Thus
1572 we trim the rr result to the places where it is used. */
1573 bitmap_and (&bb_info
->out
, &bb_info
->gen
, &bb_lr_info
->out
);
1574 bitmap_clear (&bb_info
->in
);
1578 /* Forward confluence function that ignores fake edges. */
1581 df_live_confluence_n (edge e
)
1583 bitmap op1
= &df_live_get_bb_info (e
->dest
->index
)->in
;
1584 bitmap op2
= &df_live_get_bb_info (e
->src
->index
)->out
;
1586 if (e
->flags
& EDGE_FAKE
)
1589 return bitmap_ior_into (op1
, op2
);
1593 /* Transfer function for the forwards must-initialized problem. */
1596 df_live_transfer_function (int bb_index
)
1598 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1599 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1600 bitmap in
= &bb_info
->in
;
1601 bitmap out
= &bb_info
->out
;
1602 bitmap gen
= &bb_info
->gen
;
1603 bitmap kill
= &bb_info
->kill
;
1605 /* We need to use a scratch set here so that the value returned from this
1606 function invocation properly reflects whether the sets changed in a
1607 significant way; i.e. not just because the lr set was anded in. */
1608 bitmap_and (&df_live_scratch
, gen
, &bb_lr_info
->out
);
1609 /* No register may reach a location where it is not used. Thus
1610 we trim the rr result to the places where it is used. */
1611 bitmap_and_into (in
, &bb_lr_info
->in
);
1613 return bitmap_ior_and_compl (out
, &df_live_scratch
, in
, kill
);
1617 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1620 df_live_finalize (bitmap all_blocks
)
1623 if (df_live
->solutions_dirty
)
1626 unsigned int bb_index
;
1628 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1630 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1631 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1633 /* No register may reach a location where it is not used. Thus
1634 we trim the rr result to the places where it is used. */
1635 bitmap_and_into (&bb_live_info
->in
, &bb_lr_info
->in
);
1636 bitmap_and_into (&bb_live_info
->out
, &bb_lr_info
->out
);
1639 df_live
->solutions_dirty
= false;
1644 /* Free all storage associated with the problem. */
1649 struct df_live_problem_data
*problem_data
1650 = (struct df_live_problem_data
*) df_live
->problem_data
;
1651 if (df_live
->block_info
)
1653 df_live
->block_info_size
= 0;
1654 free (df_live
->block_info
);
1655 df_live
->block_info
= NULL
;
1656 bitmap_clear (&df_live_scratch
);
1657 bitmap_obstack_release (&problem_data
->live_bitmaps
);
1658 free (problem_data
);
1659 df_live
->problem_data
= NULL
;
1661 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1666 /* Debugging info at top of bb. */
1669 df_live_top_dump (basic_block bb
, FILE *file
)
1671 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1672 struct df_live_problem_data
*problem_data
;
1677 fprintf (file
, ";; live in \t");
1678 df_print_regset (file
, &bb_info
->in
);
1679 if (df_live
->problem_data
)
1681 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1682 if (problem_data
->in
)
1684 fprintf (file
, ";; old in \t");
1685 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1688 fprintf (file
, ";; live gen \t");
1689 df_print_regset (file
, &bb_info
->gen
);
1690 fprintf (file
, ";; live kill\t");
1691 df_print_regset (file
, &bb_info
->kill
);
1695 /* Debugging info at bottom of bb. */
1698 df_live_bottom_dump (basic_block bb
, FILE *file
)
1700 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1701 struct df_live_problem_data
*problem_data
;
1706 fprintf (file
, ";; live out \t");
1707 df_print_regset (file
, &bb_info
->out
);
1708 if (df_live
->problem_data
)
1710 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1711 if (problem_data
->out
)
1713 fprintf (file
, ";; old out \t");
1714 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1720 /* Build the datastructure to verify that the solution to the dataflow
1721 equations is not dirty. */
1724 df_live_verify_solution_start (void)
1727 struct df_live_problem_data
*problem_data
;
1728 if (df_live
->solutions_dirty
)
1731 /* Set it true so that the solution is recomputed. */
1732 df_live
->solutions_dirty
= true;
1734 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1735 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block
);
1736 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block
);
1740 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->live_bitmaps
);
1741 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->live_bitmaps
);
1742 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1743 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1748 /* Compare the saved datastructure and the new solution to the dataflow
1752 df_live_verify_solution_end (void)
1754 struct df_live_problem_data
*problem_data
;
1757 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1758 if (!problem_data
->out
)
1763 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1764 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
1766 /*df_dump (stderr);*/
1771 /* Cannot delete them immediately because you may want to dump them
1772 if the comparison fails. */
1775 bitmap_clear (&problem_data
->in
[bb
->index
]);
1776 bitmap_clear (&problem_data
->out
[bb
->index
]);
1779 free (problem_data
->in
);
1780 free (problem_data
->out
);
1781 free (problem_data
);
1782 df_live
->problem_data
= NULL
;
1786 /* All of the information associated with every instance of the problem. */
1788 static struct df_problem problem_LIVE
=
1790 DF_LIVE
, /* Problem id. */
1791 DF_FORWARD
, /* Direction. */
1792 df_live_alloc
, /* Allocate the problem specific data. */
1793 df_live_reset
, /* Reset global information. */
1794 df_live_free_bb_info
, /* Free basic block info. */
1795 df_live_local_compute
, /* Local compute function. */
1796 df_live_init
, /* Init the solution specific data. */
1797 df_worklist_dataflow
, /* Worklist solver. */
1798 NULL
, /* Confluence operator 0. */
1799 df_live_confluence_n
, /* Confluence operator n. */
1800 df_live_transfer_function
, /* Transfer function. */
1801 df_live_finalize
, /* Finalize function. */
1802 df_live_free
, /* Free all of the problem information. */
1803 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1804 NULL
, /* Debugging. */
1805 df_live_top_dump
, /* Debugging start block. */
1806 df_live_bottom_dump
, /* Debugging end block. */
1807 NULL
, /* Debugging start insn. */
1808 NULL
, /* Debugging end insn. */
1809 df_live_verify_solution_start
,/* Incremental solution verify start. */
1810 df_live_verify_solution_end
, /* Incremental solution verify end. */
1811 &problem_LR
, /* Dependent problem. */
1812 sizeof (struct df_live_bb_info
),/* Size of entry of block_info array. */
1813 TV_DF_LIVE
, /* Timing variable. */
1814 false /* Reset blocks on dropping out of blocks_to_analyze. */
1818 /* Create a new DATAFLOW instance and add it to an existing instance
1819 of DF. The returned structure is what is used to get at the
1823 df_live_add_problem (void)
1825 df_add_problem (&problem_LIVE
);
1826 /* These will be initialized when df_scan_blocks processes each
1828 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
1832 /* Set all of the blocks as dirty. This needs to be done if this
1833 problem is added after all of the insns have been scanned. */
1836 df_live_set_all_dirty (void)
1840 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1845 /* Verify that all of the lr related info is consistent and
1849 df_live_verify_transfer_functions (void)
1852 bitmap_head saved_gen
;
1853 bitmap_head saved_kill
;
1854 bitmap_head all_blocks
;
1859 bitmap_initialize (&saved_gen
, &bitmap_default_obstack
);
1860 bitmap_initialize (&saved_kill
, &bitmap_default_obstack
);
1861 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1863 df_grow_insn_info ();
1867 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1868 bitmap_set_bit (&all_blocks
, bb
->index
);
1872 /* Make a copy of the transfer functions and then compute
1873 new ones to see if the transfer functions have
1875 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1878 bitmap_copy (&saved_gen
, &bb_info
->gen
);
1879 bitmap_copy (&saved_kill
, &bb_info
->kill
);
1880 bitmap_clear (&bb_info
->gen
);
1881 bitmap_clear (&bb_info
->kill
);
1883 df_live_bb_local_compute (bb
->index
);
1884 gcc_assert (bitmap_equal_p (&saved_gen
, &bb_info
->gen
));
1885 gcc_assert (bitmap_equal_p (&saved_kill
, &bb_info
->kill
));
1890 /* If we do not have basic block info, the block must be in
1891 the list of dirty blocks or else some one has added a
1892 block behind our backs. */
1893 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1896 /* Make sure no one created a block without following
1898 gcc_assert (df_scan_get_bb_info (bb
->index
));
1901 /* Make sure there are no dirty bits in blocks that have been deleted. */
1902 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1904 bitmap_clear (&saved_gen
);
1905 bitmap_clear (&saved_kill
);
1906 bitmap_clear (&all_blocks
);
1909 /*----------------------------------------------------------------------------
1910 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1912 Link either the defs to the uses and / or the uses to the defs.
1914 These problems are set up like the other dataflow problems so that
1915 they nicely fit into the framework. They are much simpler and only
1916 involve a single traversal of instructions and an examination of
1917 the reaching defs information (the dependent problem).
1918 ----------------------------------------------------------------------------*/
1920 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1922 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1925 df_chain_create (df_ref src
, df_ref dst
)
1927 struct df_link
*head
= DF_REF_CHAIN (src
);
1928 struct df_link
*link
= (struct df_link
*) pool_alloc (df_chain
->block_pool
);
1930 DF_REF_CHAIN (src
) = link
;
1937 /* Delete any du or ud chains that start at REF and point to
1940 df_chain_unlink_1 (df_ref ref
, df_ref target
)
1942 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1943 struct df_link
*prev
= NULL
;
1947 if (chain
->ref
== target
)
1950 prev
->next
= chain
->next
;
1952 DF_REF_CHAIN (ref
) = chain
->next
;
1953 pool_free (df_chain
->block_pool
, chain
);
1957 chain
= chain
->next
;
1962 /* Delete a du or ud chain that leave or point to REF. */
1965 df_chain_unlink (df_ref ref
)
1967 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1970 struct df_link
*next
= chain
->next
;
1971 /* Delete the other side if it exists. */
1972 df_chain_unlink_1 (chain
->ref
, ref
);
1973 pool_free (df_chain
->block_pool
, chain
);
1976 DF_REF_CHAIN (ref
) = NULL
;
1980 /* Copy the du or ud chain starting at FROM_REF and attach it to
1984 df_chain_copy (df_ref to_ref
,
1985 struct df_link
*from_ref
)
1989 df_chain_create (to_ref
, from_ref
->ref
);
1990 from_ref
= from_ref
->next
;
1995 /* Remove this problem from the stack of dataflow problems. */
1998 df_chain_remove_problem (void)
2001 unsigned int bb_index
;
2003 /* Wholesale destruction of the old chains. */
2004 if (df_chain
->block_pool
)
2005 free_alloc_pool (df_chain
->block_pool
);
2007 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2012 basic_block bb
= BASIC_BLOCK (bb_index
);
2014 if (df_chain_problem_p (DF_DU_CHAIN
))
2015 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
2016 DF_REF_CHAIN (*def_rec
) = NULL
;
2017 if (df_chain_problem_p (DF_UD_CHAIN
))
2018 for (use_rec
= df_get_artificial_uses (bb
->index
); *use_rec
; use_rec
++)
2019 DF_REF_CHAIN (*use_rec
) = NULL
;
2021 FOR_BB_INSNS (bb
, insn
)
2023 unsigned int uid
= INSN_UID (insn
);
2027 if (df_chain_problem_p (DF_DU_CHAIN
))
2028 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2029 DF_REF_CHAIN (*def_rec
) = NULL
;
2030 if (df_chain_problem_p (DF_UD_CHAIN
))
2032 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2033 DF_REF_CHAIN (*use_rec
) = NULL
;
2034 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
2035 DF_REF_CHAIN (*use_rec
) = NULL
;
2041 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
2042 df_chain
->block_pool
= NULL
;
2046 /* Remove the chain problem completely. */
2049 df_chain_fully_remove_problem (void)
2051 df_chain_remove_problem ();
2052 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2057 /* Create def-use or use-def chains. */
2060 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2062 df_chain_remove_problem ();
2063 df_chain
->block_pool
= create_alloc_pool ("df_chain_block pool",
2064 sizeof (struct df_link
), 50);
2065 df_chain
->optional_p
= true;
2069 /* Reset all of the chains when the set of basic blocks changes. */
2072 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2074 df_chain_remove_problem ();
2078 /* Create the chains for a list of USEs. */
2081 df_chain_create_bb_process_use (bitmap local_rd
,
2086 unsigned int def_index
;
2090 df_ref use
= *use_rec
;
2091 unsigned int uregno
= DF_REF_REGNO (use
);
2092 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2093 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2095 /* Do not want to go through this for an uninitialized var. */
2096 int count
= DF_DEFS_COUNT (uregno
);
2099 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2101 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2102 unsigned int last_index
= first_index
+ count
- 1;
2104 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2107 if (def_index
> last_index
)
2110 def
= DF_DEFS_GET (def_index
);
2111 if (df_chain_problem_p (DF_DU_CHAIN
))
2112 df_chain_create (def
, use
);
2113 if (df_chain_problem_p (DF_UD_CHAIN
))
2114 df_chain_create (use
, def
);
2125 /* Create chains from reaching defs bitmaps for basic block BB. */
2128 df_chain_create_bb (unsigned int bb_index
)
2130 basic_block bb
= BASIC_BLOCK (bb_index
);
2131 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2135 bitmap_initialize (&cpy
, &bitmap_default_obstack
);
2136 bitmap_copy (&cpy
, &bb_info
->in
);
2137 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2139 /* Since we are going forwards, process the artificial uses first
2140 then the artificial defs second. */
2143 /* Create the chains for the artificial uses from the EH_USES at the
2144 beginning of the block. */
2146 /* Artificials are only hard regs. */
2147 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2148 df_chain_create_bb_process_use (&cpy
,
2149 df_get_artificial_uses (bb
->index
),
2153 df_rd_simulate_artificial_defs_at_top (bb
, &cpy
);
2155 /* Process the regular instructions next. */
2156 FOR_BB_INSNS (bb
, insn
)
2159 unsigned int uid
= INSN_UID (insn
);
2161 /* First scan the uses and link them up with the defs that remain
2162 in the cpy vector. */
2163 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_USES (uid
), 0);
2164 if (df
->changeable_flags
& DF_EQ_NOTES
)
2165 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2167 /* Since we are going forwards, process the defs second. */
2168 df_rd_simulate_one_insn (bb
, insn
, &cpy
);
2171 /* Create the chains for the artificial uses of the hard registers
2172 at the end of the block. */
2173 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2174 df_chain_create_bb_process_use (&cpy
,
2175 df_get_artificial_uses (bb
->index
),
2178 bitmap_clear (&cpy
);
2181 /* Create def-use chains from reaching use bitmaps for basic blocks
2185 df_chain_finalize (bitmap all_blocks
)
2187 unsigned int bb_index
;
2190 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2192 df_chain_create_bb (bb_index
);
2197 /* Free all storage associated with the problem. */
2200 df_chain_free (void)
2202 free_alloc_pool (df_chain
->block_pool
);
2203 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2208 /* Debugging info. */
2211 df_chain_bb_dump (basic_block bb
, FILE *file
, bool top
)
2213 /* Artificials are only hard regs. */
2214 if (df
->changeable_flags
& DF_NO_HARD_REGS
)
2216 if (df_chain_problem_p (DF_UD_CHAIN
))
2219 ";; UD chains for artificial uses at %s\n",
2220 top
? "top" : "bottom");
2221 df_ref
*use_rec
= df_get_artificial_uses (bb
->index
);
2226 df_ref use
= *use_rec
;
2227 if ((top
&& (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2228 || (!top
&& !(DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)))
2230 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2231 df_chain_dump (DF_REF_CHAIN (use
), file
);
2232 fprintf (file
, "\n");
2238 if (df_chain_problem_p (DF_DU_CHAIN
))
2241 ";; DU chains for artificial defs at %s\n",
2242 top
? "top" : "bottom");
2243 df_ref
*def_rec
= df_get_artificial_defs (bb
->index
);
2248 df_ref def
= *def_rec
;
2250 if ((top
&& (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
2251 || (!top
&& !(DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)))
2253 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2254 df_chain_dump (DF_REF_CHAIN (def
), file
);
2255 fprintf (file
, "\n");
2264 df_chain_top_dump (basic_block bb
, FILE *file
)
2266 df_chain_bb_dump (bb
, file
, /*top=*/true);
2270 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2272 df_chain_bb_dump (bb
, file
, /*top=*/false);
2276 df_chain_insn_top_dump (const_rtx insn
, FILE *file
)
2278 if (df_chain_problem_p (DF_UD_CHAIN
) && INSN_P (insn
))
2280 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2281 df_ref
*use_rec
= DF_INSN_INFO_USES (insn_info
);
2282 df_ref
*eq_use_rec
= DF_INSN_INFO_EQ_USES (insn_info
);
2283 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2284 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2285 if (*use_rec
|| *eq_use_rec
)
2289 df_ref use
= *use_rec
;
2290 if (! HARD_REGISTER_NUM_P (DF_REF_REGNO (use
))
2291 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2293 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2294 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
2295 fprintf (file
, "read/write ");
2296 df_chain_dump (DF_REF_CHAIN (use
), file
);
2297 fprintf (file
, "\n");
2303 df_ref use
= *eq_use_rec
;
2304 if (! HARD_REGISTER_NUM_P (DF_REF_REGNO (use
))
2305 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2307 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2308 df_chain_dump (DF_REF_CHAIN (use
), file
);
2309 fprintf (file
, "\n");
2318 df_chain_insn_bottom_dump (const_rtx insn
, FILE *file
)
2320 if (df_chain_problem_p (DF_DU_CHAIN
) && INSN_P (insn
))
2322 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2323 df_ref
*def_rec
= DF_INSN_INFO_DEFS (insn_info
);
2324 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2325 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2330 df_ref def
= *def_rec
;
2331 if (! HARD_REGISTER_NUM_P (DF_REF_REGNO (def
))
2332 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2334 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2335 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
2336 fprintf (file
, "read/write ");
2337 df_chain_dump (DF_REF_CHAIN (def
), file
);
2338 fprintf (file
, "\n");
2343 fprintf (file
, "\n");
2347 static struct df_problem problem_CHAIN
=
2349 DF_CHAIN
, /* Problem id. */
2350 DF_NONE
, /* Direction. */
2351 df_chain_alloc
, /* Allocate the problem specific data. */
2352 df_chain_reset
, /* Reset global information. */
2353 NULL
, /* Free basic block info. */
2354 NULL
, /* Local compute function. */
2355 NULL
, /* Init the solution specific data. */
2356 NULL
, /* Iterative solver. */
2357 NULL
, /* Confluence operator 0. */
2358 NULL
, /* Confluence operator n. */
2359 NULL
, /* Transfer function. */
2360 df_chain_finalize
, /* Finalize function. */
2361 df_chain_free
, /* Free all of the problem information. */
2362 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2363 NULL
, /* Debugging. */
2364 df_chain_top_dump
, /* Debugging start block. */
2365 df_chain_bottom_dump
, /* Debugging end block. */
2366 df_chain_insn_top_dump
, /* Debugging start insn. */
2367 df_chain_insn_bottom_dump
, /* Debugging end insn. */
2368 NULL
, /* Incremental solution verify start. */
2369 NULL
, /* Incremental solution verify end. */
2370 &problem_RD
, /* Dependent problem. */
2371 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
2372 TV_DF_CHAIN
, /* Timing variable. */
2373 false /* Reset blocks on dropping out of blocks_to_analyze. */
2377 /* Create a new DATAFLOW instance and add it to an existing instance
2378 of DF. The returned structure is what is used to get at the
2382 df_chain_add_problem (unsigned int chain_flags
)
2384 df_add_problem (&problem_CHAIN
);
2385 df_chain
->local_flags
= chain_flags
;
2386 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
2389 #undef df_chain_problem_p
2392 /*----------------------------------------------------------------------------
2393 WORD LEVEL LIVE REGISTERS
2395 Find the locations in the function where any use of a pseudo can
2396 reach in the backwards direction. In and out bitvectors are built
2397 for each basic block. We only track pseudo registers that have a
2398 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2399 contain two bits corresponding to each of the subwords.
2401 ----------------------------------------------------------------------------*/
2403 /* Private data used to verify the solution for this problem. */
2404 struct df_word_lr_problem_data
2406 /* An obstack for the bitmaps we need for this problem. */
2407 bitmap_obstack word_lr_bitmaps
;
2411 /* Free basic block info. */
2414 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2417 struct df_word_lr_bb_info
*bb_info
= (struct df_word_lr_bb_info
*) vbb_info
;
2420 bitmap_clear (&bb_info
->use
);
2421 bitmap_clear (&bb_info
->def
);
2422 bitmap_clear (&bb_info
->in
);
2423 bitmap_clear (&bb_info
->out
);
2428 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2429 not touched unless the block is new. */
2432 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2434 unsigned int bb_index
;
2437 struct df_word_lr_problem_data
*problem_data
2438 = XNEW (struct df_word_lr_problem_data
);
2440 df_word_lr
->problem_data
= problem_data
;
2442 df_grow_bb_info (df_word_lr
);
2444 /* Create the mapping from regnos to slots. This does not change
2445 unless the problem is destroyed and recreated. In particular, if
2446 we end up deleting the only insn that used a subreg, we do not
2447 want to redo the mapping because this would invalidate everything
2450 bitmap_obstack_initialize (&problem_data
->word_lr_bitmaps
);
2453 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, bb
->index
);
2455 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
2456 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, EXIT_BLOCK
);
2458 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2460 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2462 /* When bitmaps are already initialized, just clear them. */
2463 if (bb_info
->use
.obstack
)
2465 bitmap_clear (&bb_info
->def
);
2466 bitmap_clear (&bb_info
->use
);
2470 bitmap_initialize (&bb_info
->use
, &problem_data
->word_lr_bitmaps
);
2471 bitmap_initialize (&bb_info
->def
, &problem_data
->word_lr_bitmaps
);
2472 bitmap_initialize (&bb_info
->in
, &problem_data
->word_lr_bitmaps
);
2473 bitmap_initialize (&bb_info
->out
, &problem_data
->word_lr_bitmaps
);
2477 df_word_lr
->optional_p
= true;
2481 /* Reset the global solution for recalculation. */
2484 df_word_lr_reset (bitmap all_blocks
)
2486 unsigned int bb_index
;
2489 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2491 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2492 gcc_assert (bb_info
);
2493 bitmap_clear (&bb_info
->in
);
2494 bitmap_clear (&bb_info
->out
);
2498 /* Examine REF, and if it is for a reg we're interested in, set or
2499 clear the bits corresponding to its subwords from the bitmap
2500 according to IS_SET. LIVE is the bitmap we should update. We do
2501 not track hard regs or pseudos of any size other than 2 *
2503 We return true if we changed the bitmap, or if we encountered a register
2504 we're not tracking. */
2507 df_word_lr_mark_ref (df_ref ref
, bool is_set
, regset live
)
2509 rtx orig_reg
= DF_REF_REG (ref
);
2511 enum machine_mode reg_mode
;
2513 /* Left at -1 for whole accesses. */
2514 int which_subword
= -1;
2515 bool changed
= false;
2517 if (GET_CODE (reg
) == SUBREG
)
2518 reg
= SUBREG_REG (orig_reg
);
2519 regno
= REGNO (reg
);
2520 reg_mode
= GET_MODE (reg
);
2521 if (regno
< FIRST_PSEUDO_REGISTER
2522 || GET_MODE_SIZE (reg_mode
) != 2 * UNITS_PER_WORD
)
2525 if (GET_CODE (orig_reg
) == SUBREG
2526 && df_read_modify_subreg_p (orig_reg
))
2528 gcc_assert (DF_REF_FLAGS_IS_SET (ref
, DF_REF_PARTIAL
));
2529 if (subreg_lowpart_p (orig_reg
))
2536 if (which_subword
!= 1)
2537 changed
|= bitmap_set_bit (live
, regno
* 2);
2538 if (which_subword
!= 0)
2539 changed
|= bitmap_set_bit (live
, regno
* 2 + 1);
2543 if (which_subword
!= 1)
2544 changed
|= bitmap_clear_bit (live
, regno
* 2);
2545 if (which_subword
!= 0)
2546 changed
|= bitmap_clear_bit (live
, regno
* 2 + 1);
2551 /* Compute local live register info for basic block BB. */
2554 df_word_lr_bb_local_compute (unsigned int bb_index
)
2556 basic_block bb
= BASIC_BLOCK (bb_index
);
2557 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2562 /* Ensure that artificial refs don't contain references to pseudos. */
2563 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2565 df_ref def
= *def_rec
;
2566 gcc_assert (DF_REF_REGNO (def
) < FIRST_PSEUDO_REGISTER
);
2569 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2571 df_ref use
= *use_rec
;
2572 gcc_assert (DF_REF_REGNO (use
) < FIRST_PSEUDO_REGISTER
);
2575 FOR_BB_INSNS_REVERSE (bb
, insn
)
2577 unsigned int uid
= INSN_UID (insn
);
2579 if (!NONDEBUG_INSN_P (insn
))
2581 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2583 df_ref def
= *def_rec
;
2584 /* If the def is to only part of the reg, it does
2585 not kill the other defs that reach here. */
2586 if (!(DF_REF_FLAGS (def
) & (DF_REF_CONDITIONAL
)))
2588 df_word_lr_mark_ref (def
, true, &bb_info
->def
);
2589 df_word_lr_mark_ref (def
, false, &bb_info
->use
);
2592 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2594 df_ref use
= *use_rec
;
2595 df_word_lr_mark_ref (use
, true, &bb_info
->use
);
2601 /* Compute local live register info for each basic block within BLOCKS. */
2604 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2606 unsigned int bb_index
;
2609 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2611 if (bb_index
== EXIT_BLOCK
)
2615 EXECUTE_IF_SET_IN_BITMAP (df
->exit_block_uses
, FIRST_PSEUDO_REGISTER
,
2620 df_word_lr_bb_local_compute (bb_index
);
2623 bitmap_clear (df_word_lr
->out_of_date_transfer_functions
);
2627 /* Initialize the solution vectors. */
2630 df_word_lr_init (bitmap all_blocks
)
2632 unsigned int bb_index
;
2635 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2637 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2638 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
2639 bitmap_clear (&bb_info
->out
);
2644 /* Confluence function that ignores fake edges. */
2647 df_word_lr_confluence_n (edge e
)
2649 bitmap op1
= &df_word_lr_get_bb_info (e
->src
->index
)->out
;
2650 bitmap op2
= &df_word_lr_get_bb_info (e
->dest
->index
)->in
;
2652 return bitmap_ior_into (op1
, op2
);
2656 /* Transfer function. */
2659 df_word_lr_transfer_function (int bb_index
)
2661 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2662 bitmap in
= &bb_info
->in
;
2663 bitmap out
= &bb_info
->out
;
2664 bitmap use
= &bb_info
->use
;
2665 bitmap def
= &bb_info
->def
;
2667 return bitmap_ior_and_compl (in
, use
, out
, def
);
2671 /* Free all storage associated with the problem. */
2674 df_word_lr_free (void)
2676 struct df_word_lr_problem_data
*problem_data
2677 = (struct df_word_lr_problem_data
*)df_word_lr
->problem_data
;
2679 if (df_word_lr
->block_info
)
2681 df_word_lr
->block_info_size
= 0;
2682 free (df_word_lr
->block_info
);
2683 df_word_lr
->block_info
= NULL
;
2686 BITMAP_FREE (df_word_lr
->out_of_date_transfer_functions
);
2687 bitmap_obstack_release (&problem_data
->word_lr_bitmaps
);
2688 free (problem_data
);
2693 /* Debugging info at top of bb. */
2696 df_word_lr_top_dump (basic_block bb
, FILE *file
)
2698 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2702 fprintf (file
, ";; blr in \t");
2703 df_print_word_regset (file
, &bb_info
->in
);
2704 fprintf (file
, ";; blr use \t");
2705 df_print_word_regset (file
, &bb_info
->use
);
2706 fprintf (file
, ";; blr def \t");
2707 df_print_word_regset (file
, &bb_info
->def
);
2711 /* Debugging info at bottom of bb. */
2714 df_word_lr_bottom_dump (basic_block bb
, FILE *file
)
2716 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2720 fprintf (file
, ";; blr out \t");
2721 df_print_word_regset (file
, &bb_info
->out
);
2725 /* All of the information associated with every instance of the problem. */
2727 static struct df_problem problem_WORD_LR
=
2729 DF_WORD_LR
, /* Problem id. */
2730 DF_BACKWARD
, /* Direction. */
2731 df_word_lr_alloc
, /* Allocate the problem specific data. */
2732 df_word_lr_reset
, /* Reset global information. */
2733 df_word_lr_free_bb_info
, /* Free basic block info. */
2734 df_word_lr_local_compute
, /* Local compute function. */
2735 df_word_lr_init
, /* Init the solution specific data. */
2736 df_worklist_dataflow
, /* Worklist solver. */
2737 NULL
, /* Confluence operator 0. */
2738 df_word_lr_confluence_n
, /* Confluence operator n. */
2739 df_word_lr_transfer_function
, /* Transfer function. */
2740 NULL
, /* Finalize function. */
2741 df_word_lr_free
, /* Free all of the problem information. */
2742 df_word_lr_free
, /* Remove this problem from the stack of dataflow problems. */
2743 NULL
, /* Debugging. */
2744 df_word_lr_top_dump
, /* Debugging start block. */
2745 df_word_lr_bottom_dump
, /* Debugging end block. */
2746 NULL
, /* Debugging start insn. */
2747 NULL
, /* Debugging end insn. */
2748 NULL
, /* Incremental solution verify start. */
2749 NULL
, /* Incremental solution verify end. */
2750 NULL
, /* Dependent problem. */
2751 sizeof (struct df_word_lr_bb_info
),/* Size of entry of block_info array. */
2752 TV_DF_WORD_LR
, /* Timing variable. */
2753 false /* Reset blocks on dropping out of blocks_to_analyze. */
2757 /* Create a new DATAFLOW instance and add it to an existing instance
2758 of DF. The returned structure is what is used to get at the
2762 df_word_lr_add_problem (void)
2764 df_add_problem (&problem_WORD_LR
);
2765 /* These will be initialized when df_scan_blocks processes each
2767 df_word_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
2771 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
2772 any bits, which is used by the caller to determine whether a set is
2773 necessary. We also return true if there are other reasons not to delete
2777 df_word_lr_simulate_defs (rtx insn
, bitmap live
)
2779 bool changed
= false;
2781 unsigned int uid
= INSN_UID (insn
);
2783 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2785 df_ref def
= *def_rec
;
2786 if (DF_REF_FLAGS (def
) & DF_REF_CONDITIONAL
)
2789 changed
|= df_word_lr_mark_ref (*def_rec
, false, live
);
2795 /* Simulate the effects of the uses of INSN on LIVE. */
2798 df_word_lr_simulate_uses (rtx insn
, bitmap live
)
2801 unsigned int uid
= INSN_UID (insn
);
2803 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2804 df_word_lr_mark_ref (*use_rec
, true, live
);
2807 /*----------------------------------------------------------------------------
2808 This problem computes REG_DEAD and REG_UNUSED notes.
2809 ----------------------------------------------------------------------------*/
2812 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2814 df_note
->optional_p
= true;
2817 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
2819 df_print_note (const char *prefix
, rtx insn
, rtx note
)
2823 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
2824 print_rtl (dump_file
, note
);
2825 fprintf (dump_file
, "\n");
2830 /* After reg-stack, the x86 floating point stack regs are difficult to
2831 analyze because of all of the pushes, pops and rotations. Thus, we
2832 just leave the notes alone. */
2836 df_ignore_stack_reg (int regno
)
2838 return regstack_completed
2839 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
2843 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
2850 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
2853 df_remove_dead_and_unused_notes (rtx insn
)
2855 rtx
*pprev
= ®_NOTES (insn
);
2860 switch (REG_NOTE_KIND (link
))
2863 /* After reg-stack, we need to ignore any unused notes
2864 for the stack registers. */
2865 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2867 pprev
= &XEXP (link
, 1);
2872 rtx next
= XEXP (link
, 1);
2873 if (REG_DEAD_DEBUGGING
)
2874 df_print_note ("deleting: ", insn
, link
);
2875 free_EXPR_LIST_node (link
);
2876 *pprev
= link
= next
;
2881 /* After reg-stack, we need to ignore any unused notes
2882 for the stack registers. */
2883 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2885 pprev
= &XEXP (link
, 1);
2890 rtx next
= XEXP (link
, 1);
2891 if (REG_DEAD_DEBUGGING
)
2892 df_print_note ("deleting: ", insn
, link
);
2893 free_EXPR_LIST_node (link
);
2894 *pprev
= link
= next
;
2899 pprev
= &XEXP (link
, 1);
2906 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2907 as the bitmap of currently live registers. */
2910 df_remove_dead_eq_notes (rtx insn
, bitmap live
)
2912 rtx
*pprev
= ®_NOTES (insn
);
2917 switch (REG_NOTE_KIND (link
))
2922 /* Remove the notes that refer to dead registers. As we have at most
2923 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2924 so we need to purge the complete EQ_USES vector when removing
2925 the note using df_notes_rescan. */
2927 bool deleted
= false;
2929 for (use_rec
= DF_INSN_EQ_USES (insn
); *use_rec
; use_rec
++)
2931 df_ref use
= *use_rec
;
2932 if (DF_REF_REGNO (use
) > FIRST_PSEUDO_REGISTER
2934 && (DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
)
2935 && ! bitmap_bit_p (live
, DF_REF_REGNO (use
))
2936 && loc_mentioned_in_p (DF_REF_LOC (use
), XEXP (link
, 0)))
2945 if (REG_DEAD_DEBUGGING
)
2946 df_print_note ("deleting: ", insn
, link
);
2947 next
= XEXP (link
, 1);
2948 free_EXPR_LIST_node (link
);
2949 *pprev
= link
= next
;
2950 df_notes_rescan (insn
);
2954 pprev
= &XEXP (link
, 1);
2961 pprev
= &XEXP (link
, 1);
2968 /* Set a NOTE_TYPE note for REG in INSN. */
2971 df_set_note (enum reg_note note_type
, rtx insn
, rtx reg
)
2973 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2974 add_reg_note (insn
, note_type
, reg
);
2977 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2978 arguments. Return true if the register value described by MWS's
2979 mw_reg is known to be completely unused, and if mw_reg can therefore
2980 be used in a REG_UNUSED note. */
2983 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
2984 bitmap live
, bitmap artificial_uses
)
2988 /* If MWS describes a partial reference, create REG_UNUSED notes for
2989 individual hard registers. */
2990 if (mws
->flags
& DF_REF_PARTIAL
)
2993 /* Likewise if some part of the register is used. */
2994 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2995 if (bitmap_bit_p (live
, r
)
2996 || bitmap_bit_p (artificial_uses
, r
))
2999 gcc_assert (REG_P (mws
->mw_reg
));
3004 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3005 based on the bits in LIVE. Do not generate notes for registers in
3006 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3007 not generated if the reg is both read and written by the
3012 df_set_unused_notes_for_mw (rtx insn
, struct df_mw_hardreg
*mws
,
3013 bitmap live
, bitmap do_not_gen
,
3014 bitmap artificial_uses
,
3015 struct dead_debug_local
*debug
)
3019 if (REG_DEAD_DEBUGGING
&& dump_file
)
3020 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
3021 mws
->start_regno
, mws
->end_regno
);
3023 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
3025 unsigned int regno
= mws
->start_regno
;
3026 df_set_note (REG_UNUSED
, insn
, mws
->mw_reg
);
3027 dead_debug_insert_temp (debug
, regno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
3029 if (REG_DEAD_DEBUGGING
)
3030 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3032 bitmap_set_bit (do_not_gen
, regno
);
3033 /* Only do this if the value is totally dead. */
3036 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3038 if (!bitmap_bit_p (live
, r
)
3039 && !bitmap_bit_p (artificial_uses
, r
))
3041 df_set_note (REG_UNUSED
, insn
, regno_reg_rtx
[r
]);
3042 dead_debug_insert_temp (debug
, r
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
3043 if (REG_DEAD_DEBUGGING
)
3044 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3046 bitmap_set_bit (do_not_gen
, r
);
3051 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3052 arguments. Return true if the register value described by MWS's
3053 mw_reg is known to be completely dead, and if mw_reg can therefore
3054 be used in a REG_DEAD note. */
3057 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
3058 bitmap live
, bitmap artificial_uses
,
3063 /* If MWS describes a partial reference, create REG_DEAD notes for
3064 individual hard registers. */
3065 if (mws
->flags
& DF_REF_PARTIAL
)
3068 /* Likewise if some part of the register is not dead. */
3069 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3070 if (bitmap_bit_p (live
, r
)
3071 || bitmap_bit_p (artificial_uses
, r
)
3072 || bitmap_bit_p (do_not_gen
, r
))
3075 gcc_assert (REG_P (mws
->mw_reg
));
3079 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3080 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3081 from being set if the instruction both reads and writes the
3085 df_set_dead_notes_for_mw (rtx insn
, struct df_mw_hardreg
*mws
,
3086 bitmap live
, bitmap do_not_gen
,
3087 bitmap artificial_uses
, bool *added_notes_p
)
3090 bool is_debug
= *added_notes_p
;
3092 *added_notes_p
= false;
3094 if (REG_DEAD_DEBUGGING
&& dump_file
)
3096 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3097 mws
->start_regno
, mws
->end_regno
);
3098 df_print_regset (dump_file
, do_not_gen
);
3099 fprintf (dump_file
, " live =");
3100 df_print_regset (dump_file
, live
);
3101 fprintf (dump_file
, " artificial uses =");
3102 df_print_regset (dump_file
, artificial_uses
);
3105 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3109 *added_notes_p
= true;
3112 /* Add a dead note for the entire multi word register. */
3113 df_set_note (REG_DEAD
, insn
, mws
->mw_reg
);
3114 if (REG_DEAD_DEBUGGING
)
3115 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3119 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3120 if (!bitmap_bit_p (live
, r
)
3121 && !bitmap_bit_p (artificial_uses
, r
)
3122 && !bitmap_bit_p (do_not_gen
, r
))
3126 *added_notes_p
= true;
3129 df_set_note (REG_DEAD
, insn
, regno_reg_rtx
[r
]);
3130 if (REG_DEAD_DEBUGGING
)
3131 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3138 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3139 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3142 df_create_unused_note (rtx insn
, df_ref def
,
3143 bitmap live
, bitmap artificial_uses
,
3144 struct dead_debug_local
*debug
)
3146 unsigned int dregno
= DF_REF_REGNO (def
);
3148 if (REG_DEAD_DEBUGGING
&& dump_file
)
3150 fprintf (dump_file
, " regular looking at def ");
3151 df_ref_debug (def
, dump_file
);
3154 if (!((DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3155 || bitmap_bit_p (live
, dregno
)
3156 || bitmap_bit_p (artificial_uses
, dregno
)
3157 || df_ignore_stack_reg (dregno
)))
3159 rtx reg
= (DF_REF_LOC (def
))
3160 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3161 df_set_note (REG_UNUSED
, insn
, reg
);
3162 dead_debug_insert_temp (debug
, dregno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
3163 if (REG_DEAD_DEBUGGING
)
3164 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3171 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3172 info: lifetime, bb, and number of defs and uses for basic block
3173 BB. The three bitvectors are scratch regs used here. */
3176 df_note_bb_compute (unsigned int bb_index
,
3177 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3179 basic_block bb
= BASIC_BLOCK (bb_index
);
3183 struct dead_debug_local debug
;
3185 dead_debug_local_init (&debug
, NULL
, NULL
);
3187 bitmap_copy (live
, df_get_live_out (bb
));
3188 bitmap_clear (artificial_uses
);
3190 if (REG_DEAD_DEBUGGING
&& dump_file
)
3192 fprintf (dump_file
, "live at bottom ");
3193 df_print_regset (dump_file
, live
);
3196 /* Process the artificial defs and uses at the bottom of the block
3197 to begin processing. */
3198 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3200 df_ref def
= *def_rec
;
3202 if (REG_DEAD_DEBUGGING
&& dump_file
)
3203 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3205 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3206 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3209 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3211 df_ref use
= *use_rec
;
3212 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3214 unsigned int regno
= DF_REF_REGNO (use
);
3215 bitmap_set_bit (live
, regno
);
3217 /* Notes are not generated for any of the artificial registers
3218 at the bottom of the block. */
3219 bitmap_set_bit (artificial_uses
, regno
);
3223 if (REG_DEAD_DEBUGGING
&& dump_file
)
3225 fprintf (dump_file
, "live before artificials out ");
3226 df_print_regset (dump_file
, live
);
3229 FOR_BB_INSNS_REVERSE (bb
, insn
)
3231 unsigned int uid
= INSN_UID (insn
);
3232 struct df_mw_hardreg
**mws_rec
;
3238 debug_insn
= DEBUG_INSN_P (insn
);
3240 bitmap_clear (do_not_gen
);
3241 df_remove_dead_and_unused_notes (insn
);
3243 /* Process the defs. */
3246 if (REG_DEAD_DEBUGGING
&& dump_file
)
3248 fprintf (dump_file
, "processing call %d\n live =", INSN_UID (insn
));
3249 df_print_regset (dump_file
, live
);
3252 /* We only care about real sets for calls. Clobbers cannot
3253 be depended on to really die. */
3254 mws_rec
= DF_INSN_UID_MWS (uid
);
3257 struct df_mw_hardreg
*mws
= *mws_rec
;
3258 if ((DF_MWS_REG_DEF_P (mws
))
3259 && !df_ignore_stack_reg (mws
->start_regno
))
3260 df_set_unused_notes_for_mw (insn
,
3261 mws
, live
, do_not_gen
,
3262 artificial_uses
, &debug
);
3266 /* All of the defs except the return value are some sort of
3267 clobber. This code is for the return. */
3268 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3270 df_ref def
= *def_rec
;
3271 unsigned int dregno
= DF_REF_REGNO (def
);
3272 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3274 df_create_unused_note (insn
,
3275 def
, live
, artificial_uses
, &debug
);
3276 bitmap_set_bit (do_not_gen
, dregno
);
3279 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3280 bitmap_clear_bit (live
, dregno
);
3286 mws_rec
= DF_INSN_UID_MWS (uid
);
3289 struct df_mw_hardreg
*mws
= *mws_rec
;
3290 if (DF_MWS_REG_DEF_P (mws
))
3291 df_set_unused_notes_for_mw (insn
,
3292 mws
, live
, do_not_gen
,
3293 artificial_uses
, &debug
);
3297 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3299 df_ref def
= *def_rec
;
3300 unsigned int dregno
= DF_REF_REGNO (def
);
3301 df_create_unused_note (insn
,
3302 def
, live
, artificial_uses
, &debug
);
3304 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3305 bitmap_set_bit (do_not_gen
, dregno
);
3307 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3308 bitmap_clear_bit (live
, dregno
);
3312 /* Process the uses. */
3313 mws_rec
= DF_INSN_UID_MWS (uid
);
3316 struct df_mw_hardreg
*mws
= *mws_rec
;
3317 if (DF_MWS_REG_USE_P (mws
)
3318 && !df_ignore_stack_reg (mws
->start_regno
))
3320 bool really_add_notes
= debug_insn
!= 0;
3322 df_set_dead_notes_for_mw (insn
,
3323 mws
, live
, do_not_gen
,
3327 if (really_add_notes
)
3333 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3335 df_ref use
= *use_rec
;
3336 unsigned int uregno
= DF_REF_REGNO (use
);
3338 if (REG_DEAD_DEBUGGING
&& dump_file
&& !debug_insn
)
3340 fprintf (dump_file
, " regular looking at use ");
3341 df_ref_debug (use
, dump_file
);
3344 if (!bitmap_bit_p (live
, uregno
))
3350 /* We won't add REG_UNUSED or REG_DEAD notes for
3351 these, so we don't have to mess with them in
3352 debug insns either. */
3353 if (!bitmap_bit_p (artificial_uses
, uregno
)
3354 && !df_ignore_stack_reg (uregno
))
3355 dead_debug_add (&debug
, use
, uregno
);
3361 dead_debug_insert_temp (&debug
, uregno
, insn
,
3362 DEBUG_TEMP_BEFORE_WITH_REG
);
3364 if ( (!(DF_REF_FLAGS (use
)
3365 & (DF_REF_MW_HARDREG
| DF_REF_READ_WRITE
)))
3366 && (!bitmap_bit_p (do_not_gen
, uregno
))
3367 && (!bitmap_bit_p (artificial_uses
, uregno
))
3368 && (!df_ignore_stack_reg (uregno
)))
3370 rtx reg
= (DF_REF_LOC (use
))
3371 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3372 df_set_note (REG_DEAD
, insn
, reg
);
3374 if (REG_DEAD_DEBUGGING
)
3375 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3377 /* This register is now live. */
3378 bitmap_set_bit (live
, uregno
);
3382 df_remove_dead_eq_notes (insn
, live
);
3384 if (debug_insn
== -1)
3386 /* ??? We could probably do better here, replacing dead
3387 registers with their definitions. */
3388 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3389 df_insn_rescan_debug_internal (insn
);
3393 dead_debug_local_finish (&debug
, NULL
);
3397 /* Compute register info: lifetime, bb, and number of defs and uses. */
3399 df_note_compute (bitmap all_blocks
)
3401 unsigned int bb_index
;
3403 bitmap_head live
, do_not_gen
, artificial_uses
;
3405 bitmap_initialize (&live
, &df_bitmap_obstack
);
3406 bitmap_initialize (&do_not_gen
, &df_bitmap_obstack
);
3407 bitmap_initialize (&artificial_uses
, &df_bitmap_obstack
);
3409 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3411 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3412 pseudos in debug insns because we don't always (re)visit blocks
3413 with death points after visiting dead uses. Even changing this
3414 loop to postorder would still leave room for visiting a death
3415 point before visiting a subsequent debug use. */
3416 df_note_bb_compute (bb_index
, &live
, &do_not_gen
, &artificial_uses
);
3419 bitmap_clear (&live
);
3420 bitmap_clear (&do_not_gen
);
3421 bitmap_clear (&artificial_uses
);
3425 /* Free all storage associated with the problem. */
3434 /* All of the information associated every instance of the problem. */
3436 static struct df_problem problem_NOTE
=
3438 DF_NOTE
, /* Problem id. */
3439 DF_NONE
, /* Direction. */
3440 df_note_alloc
, /* Allocate the problem specific data. */
3441 NULL
, /* Reset global information. */
3442 NULL
, /* Free basic block info. */
3443 df_note_compute
, /* Local compute function. */
3444 NULL
, /* Init the solution specific data. */
3445 NULL
, /* Iterative solver. */
3446 NULL
, /* Confluence operator 0. */
3447 NULL
, /* Confluence operator n. */
3448 NULL
, /* Transfer function. */
3449 NULL
, /* Finalize function. */
3450 df_note_free
, /* Free all of the problem information. */
3451 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3452 NULL
, /* Debugging. */
3453 NULL
, /* Debugging start block. */
3454 NULL
, /* Debugging end block. */
3455 NULL
, /* Debugging start insn. */
3456 NULL
, /* Debugging end insn. */
3457 NULL
, /* Incremental solution verify start. */
3458 NULL
, /* Incremental solution verify end. */
3459 &problem_LR
, /* Dependent problem. */
3460 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
3461 TV_DF_NOTE
, /* Timing variable. */
3462 false /* Reset blocks on dropping out of blocks_to_analyze. */
3466 /* Create a new DATAFLOW instance and add it to an existing instance
3467 of DF. The returned structure is what is used to get at the
3471 df_note_add_problem (void)
3473 df_add_problem (&problem_NOTE
);
3479 /*----------------------------------------------------------------------------
3480 Functions for simulating the effects of single insns.
3482 You can either simulate in the forwards direction, starting from
3483 the top of a block or the backwards direction from the end of the
3484 block. If you go backwards, defs are examined first to clear bits,
3485 then uses are examined to set bits. If you go forwards, defs are
3486 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3487 are examined to clear bits. In either case, the result of examining
3488 a def can be undone (respectively by a use or a REG_UNUSED note).
3490 If you start at the top of the block, use one of DF_LIVE_IN or
3491 DF_LR_IN. If you start at the bottom of the block use one of
3492 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3493 THEY WILL BE DESTROYED.
3494 ----------------------------------------------------------------------------*/
3497 /* Find the set of DEFs for INSN. */
3500 df_simulate_find_defs (rtx insn
, bitmap defs
)
3503 unsigned int uid
= INSN_UID (insn
);
3505 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3507 df_ref def
= *def_rec
;
3508 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3512 /* Find the set of uses for INSN. This includes partial defs. */
3515 df_simulate_find_uses (rtx insn
, bitmap uses
)
3518 unsigned int uid
= INSN_UID (insn
);
3520 for (rec
= DF_INSN_UID_DEFS (uid
); *rec
; rec
++)
3523 if (DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3524 bitmap_set_bit (uses
, DF_REF_REGNO (def
));
3526 for (rec
= DF_INSN_UID_USES (uid
); *rec
; rec
++)
3529 bitmap_set_bit (uses
, DF_REF_REGNO (use
));
3533 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3536 df_simulate_find_noclobber_defs (rtx insn
, bitmap defs
)
3539 unsigned int uid
= INSN_UID (insn
);
3541 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3543 df_ref def
= *def_rec
;
3544 if (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
3545 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3550 /* Simulate the effects of the defs of INSN on LIVE. */
3553 df_simulate_defs (rtx insn
, bitmap live
)
3556 unsigned int uid
= INSN_UID (insn
);
3558 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3560 df_ref def
= *def_rec
;
3561 unsigned int dregno
= DF_REF_REGNO (def
);
3563 /* If the def is to only part of the reg, it does
3564 not kill the other defs that reach here. */
3565 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3566 bitmap_clear_bit (live
, dregno
);
3571 /* Simulate the effects of the uses of INSN on LIVE. */
3574 df_simulate_uses (rtx insn
, bitmap live
)
3577 unsigned int uid
= INSN_UID (insn
);
3579 if (DEBUG_INSN_P (insn
))
3582 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3584 df_ref use
= *use_rec
;
3585 /* Add use to set of uses in this BB. */
3586 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3591 /* Add back the always live regs in BB to LIVE. */
3594 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3596 /* These regs are considered always live so if they end up dying
3597 because of some def, we need to bring the back again. */
3598 if (bb_has_eh_pred (bb
))
3599 bitmap_ior_into (live
, &df
->eh_block_artificial_uses
);
3601 bitmap_ior_into (live
, &df
->regular_block_artificial_uses
);
3605 /*----------------------------------------------------------------------------
3606 The following three functions are used only for BACKWARDS scanning:
3607 i.e. they process the defs before the uses.
3609 df_simulate_initialize_backwards should be called first with a
3610 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3611 df_simulate_one_insn_backwards should be called for each insn in
3612 the block, starting with the last one. Finally,
3613 df_simulate_finalize_backwards can be called to get a new value
3614 of the sets at the top of the block (this is rarely used).
3615 ----------------------------------------------------------------------------*/
3617 /* Apply the artificial uses and defs at the end of BB in a backwards
3621 df_simulate_initialize_backwards (basic_block bb
, bitmap live
)
3625 int bb_index
= bb
->index
;
3627 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3629 df_ref def
= *def_rec
;
3630 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3631 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3634 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3636 df_ref use
= *use_rec
;
3637 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3638 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3643 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3646 df_simulate_one_insn_backwards (basic_block bb
, rtx insn
, bitmap live
)
3648 if (!NONDEBUG_INSN_P (insn
))
3651 df_simulate_defs (insn
, live
);
3652 df_simulate_uses (insn
, live
);
3653 df_simulate_fixup_sets (bb
, live
);
3657 /* Apply the artificial uses and defs at the top of BB in a backwards
3661 df_simulate_finalize_backwards (basic_block bb
, bitmap live
)
3667 int bb_index
= bb
->index
;
3669 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3671 df_ref def
= *def_rec
;
3672 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3673 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3677 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3679 df_ref use
= *use_rec
;
3680 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3681 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3685 /*----------------------------------------------------------------------------
3686 The following three functions are used only for FORWARDS scanning:
3687 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3688 Thus it is important to add the DF_NOTES problem to the stack of
3689 problems computed before using these functions.
3691 df_simulate_initialize_forwards should be called first with a
3692 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3693 df_simulate_one_insn_forwards should be called for each insn in
3694 the block, starting with the first one.
3695 ----------------------------------------------------------------------------*/
3697 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3698 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3702 df_simulate_initialize_forwards (basic_block bb
, bitmap live
)
3705 int bb_index
= bb
->index
;
3707 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3709 df_ref def
= *def_rec
;
3710 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3711 bitmap_set_bit (live
, DF_REF_REGNO (def
));
3715 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3718 df_simulate_one_insn_forwards (basic_block bb
, rtx insn
, bitmap live
)
3721 if (! INSN_P (insn
))
3724 /* Make sure that DF_NOTE really is an active df problem. */
3725 gcc_assert (df_note
);
3727 /* Note that this is the opposite as how the problem is defined, because
3728 in the LR problem defs _kill_ liveness. However, they do so backwards,
3729 while here the scan is performed forwards! So, first assume that the
3730 def is live, and if this is not true REG_UNUSED notes will rectify the
3732 df_simulate_find_noclobber_defs (insn
, live
);
3734 /* Clear all of the registers that go dead. */
3735 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3737 switch (REG_NOTE_KIND (link
))
3742 rtx reg
= XEXP (link
, 0);
3743 int regno
= REGNO (reg
);
3744 if (HARD_REGISTER_NUM_P (regno
))
3745 bitmap_clear_range (live
, regno
,
3746 hard_regno_nregs
[regno
][GET_MODE (reg
)]);
3748 bitmap_clear_bit (live
, regno
);
3755 df_simulate_fixup_sets (bb
, live
);
3758 /* Used by the next two functions to encode information about the
3759 memory references we found. */
3760 #define MEMREF_NORMAL 1
3761 #define MEMREF_VOLATILE 2
3763 /* A subroutine of can_move_insns_across_p called through for_each_rtx.
3764 Return either MEMREF_NORMAL or MEMREF_VOLATILE if a memory is found. */
3767 find_memory (rtx
*px
, void *data ATTRIBUTE_UNUSED
)
3771 if (GET_CODE (x
) == ASM_OPERANDS
&& MEM_VOLATILE_P (x
))
3772 return MEMREF_VOLATILE
;
3776 if (MEM_VOLATILE_P (x
))
3777 return MEMREF_VOLATILE
;
3778 if (MEM_READONLY_P (x
))
3781 return MEMREF_NORMAL
;
3784 /* A subroutine of can_move_insns_across_p called through note_stores.
3785 DATA points to an integer in which we set either the bit for
3786 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3790 find_memory_stores (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
,
3791 void *data ATTRIBUTE_UNUSED
)
3793 int *pflags
= (int *)data
;
3794 if (GET_CODE (x
) == SUBREG
)
3796 /* Treat stores to SP as stores to memory, this will prevent problems
3797 when there are references to the stack frame. */
3798 if (x
== stack_pointer_rtx
)
3799 *pflags
|= MEMREF_VOLATILE
;
3802 *pflags
|= MEM_VOLATILE_P (x
) ? MEMREF_VOLATILE
: MEMREF_NORMAL
;
3805 /* Scan BB backwards, using df_simulate functions to keep track of
3806 lifetimes, up to insn POINT. The result is stored in LIVE. */
3809 simulate_backwards_to_point (basic_block bb
, regset live
, rtx point
)
3812 bitmap_copy (live
, df_get_live_out (bb
));
3813 df_simulate_initialize_backwards (bb
, live
);
3815 /* Scan and update life information until we reach the point we're
3817 for (insn
= BB_END (bb
); insn
!= point
; insn
= PREV_INSN (insn
))
3818 df_simulate_one_insn_backwards (bb
, insn
, live
);
3821 /* Return true if it is safe to move a group of insns, described by
3822 the range FROM to TO, backwards across another group of insns,
3823 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
3824 are no insns between ACROSS_TO and FROM, but they may be in
3825 different basic blocks; MERGE_BB is the block from which the
3826 insns will be moved. The caller must pass in a regset MERGE_LIVE
3827 which specifies the registers live after TO.
3829 This function may be called in one of two cases: either we try to
3830 move identical instructions from all successor blocks into their
3831 predecessor, or we try to move from only one successor block. If
3832 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3833 the second case. It should contain a set of registers live at the
3834 end of ACROSS_TO which must not be clobbered by moving the insns.
3835 In that case, we're also more careful about moving memory references
3838 We return false if it is not safe to move the entire group, but it
3839 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
3840 is set to point at the last moveable insn in such a case. */
3843 can_move_insns_across (rtx from
, rtx to
, rtx across_from
, rtx across_to
,
3844 basic_block merge_bb
, regset merge_live
,
3845 regset other_branch_live
, rtx
*pmove_upto
)
3847 rtx insn
, next
, max_to
;
3848 bitmap merge_set
, merge_use
, local_merge_live
;
3849 bitmap test_set
, test_use
;
3850 unsigned i
, fail
= 0;
3852 int memrefs_in_across
= 0;
3853 int mem_sets_in_across
= 0;
3854 bool trapping_insns_in_across
= false;
3856 if (pmove_upto
!= NULL
)
3857 *pmove_upto
= NULL_RTX
;
3859 /* Find real bounds, ignoring debug insns. */
3860 while (!NONDEBUG_INSN_P (from
) && from
!= to
)
3861 from
= NEXT_INSN (from
);
3862 while (!NONDEBUG_INSN_P (to
) && from
!= to
)
3863 to
= PREV_INSN (to
);
3865 for (insn
= across_to
; ; insn
= next
)
3869 if (RTL_CONST_OR_PURE_CALL_P (insn
))
3870 /* Pure functions can read from memory. Const functions can
3871 read from arguments that the ABI has forced onto the stack.
3872 Neither sort of read can be volatile. */
3873 memrefs_in_across
|= MEMREF_NORMAL
;
3876 memrefs_in_across
|= MEMREF_VOLATILE
;
3877 mem_sets_in_across
|= MEMREF_VOLATILE
;
3880 if (NONDEBUG_INSN_P (insn
))
3882 if (volatile_insn_p (PATTERN (insn
)))
3884 memrefs_in_across
|= for_each_rtx (&PATTERN (insn
), find_memory
,
3886 note_stores (PATTERN (insn
), find_memory_stores
,
3887 &mem_sets_in_across
);
3888 /* This is used just to find sets of the stack pointer. */
3889 memrefs_in_across
|= mem_sets_in_across
;
3890 trapping_insns_in_across
|= may_trap_p (PATTERN (insn
));
3892 next
= PREV_INSN (insn
);
3893 if (insn
== across_from
)
3898 MERGE_SET = set of registers set in MERGE_BB
3899 MERGE_USE = set of registers used in MERGE_BB and live at its top
3900 MERGE_LIVE = set of registers live at the point inside the MERGE
3901 range that we've reached during scanning
3902 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3903 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3904 and live before ACROSS_FROM. */
3906 merge_set
= BITMAP_ALLOC (®_obstack
);
3907 merge_use
= BITMAP_ALLOC (®_obstack
);
3908 local_merge_live
= BITMAP_ALLOC (®_obstack
);
3909 test_set
= BITMAP_ALLOC (®_obstack
);
3910 test_use
= BITMAP_ALLOC (®_obstack
);
3912 /* Compute the set of registers set and used in the ACROSS range. */
3913 if (other_branch_live
!= NULL
)
3914 bitmap_copy (test_use
, other_branch_live
);
3915 df_simulate_initialize_backwards (merge_bb
, test_use
);
3916 for (insn
= across_to
; ; insn
= next
)
3918 if (NONDEBUG_INSN_P (insn
))
3920 df_simulate_find_defs (insn
, test_set
);
3921 df_simulate_defs (insn
, test_use
);
3922 df_simulate_uses (insn
, test_use
);
3924 next
= PREV_INSN (insn
);
3925 if (insn
== across_from
)
3929 /* Compute an upper bound for the amount of insns moved, by finding
3930 the first insn in MERGE that sets a register in TEST_USE, or uses
3931 a register in TEST_SET. We also check for calls, trapping operations,
3932 and memory references. */
3934 for (insn
= from
; ; insn
= next
)
3938 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3940 if (NONDEBUG_INSN_P (insn
))
3942 if (may_trap_or_fault_p (PATTERN (insn
))
3943 && (trapping_insns_in_across
3944 || other_branch_live
!= NULL
3945 || volatile_insn_p (PATTERN (insn
))))
3948 /* We cannot move memory stores past each other, or move memory
3949 reads past stores, at least not without tracking them and
3950 calling true_dependence on every pair.
3952 If there is no other branch and no memory references or
3953 sets in the ACROSS range, we can move memory references
3954 freely, even volatile ones.
3956 Otherwise, the rules are as follows: volatile memory
3957 references and stores can't be moved at all, and any type
3958 of memory reference can't be moved if there are volatile
3959 accesses or stores in the ACROSS range. That leaves
3960 normal reads, which can be moved, as the trapping case is
3961 dealt with elsewhere. */
3962 if (other_branch_live
!= NULL
|| memrefs_in_across
!= 0)
3964 int mem_ref_flags
= 0;
3965 int mem_set_flags
= 0;
3966 note_stores (PATTERN (insn
), find_memory_stores
, &mem_set_flags
);
3967 mem_ref_flags
= for_each_rtx (&PATTERN (insn
), find_memory
,
3969 /* Catch sets of the stack pointer. */
3970 mem_ref_flags
|= mem_set_flags
;
3972 if ((mem_ref_flags
| mem_set_flags
) & MEMREF_VOLATILE
)
3974 if ((memrefs_in_across
& MEMREF_VOLATILE
) && mem_ref_flags
!= 0)
3976 if (mem_set_flags
!= 0
3977 || (mem_sets_in_across
!= 0 && mem_ref_flags
!= 0))
3980 df_simulate_find_uses (insn
, merge_use
);
3981 /* We're only interested in uses which use a value live at
3982 the top, not one previously set in this block. */
3983 bitmap_and_compl_into (merge_use
, merge_set
);
3984 df_simulate_find_defs (insn
, merge_set
);
3985 if (bitmap_intersect_p (merge_set
, test_use
)
3986 || bitmap_intersect_p (merge_use
, test_set
))
3989 if (!sets_cc0_p (insn
))
3993 next
= NEXT_INSN (insn
);
4000 if (max_to
== NULL_RTX
|| (fail
&& pmove_upto
== NULL
))
4003 /* Now, lower this upper bound by also taking into account that
4004 a range of insns moved across ACROSS must not leave a register
4005 live at the end that will be clobbered in ACROSS. We need to
4006 find a point where TEST_SET & LIVE == 0.
4008 Insns in the MERGE range that set registers which are also set
4009 in the ACROSS range may still be moved as long as we also move
4010 later insns which use the results of the set, and make the
4011 register dead again. This is verified by the condition stated
4012 above. We only need to test it for registers that are set in
4015 MERGE_LIVE is provided by the caller and holds live registers after
4017 bitmap_copy (local_merge_live
, merge_live
);
4018 for (insn
= to
; insn
!= max_to
; insn
= PREV_INSN (insn
))
4019 df_simulate_one_insn_backwards (merge_bb
, insn
, local_merge_live
);
4021 /* We're not interested in registers that aren't set in the moved
4023 bitmap_and_into (local_merge_live
, merge_set
);
4026 if (NONDEBUG_INSN_P (insn
))
4028 if (!bitmap_intersect_p (test_set
, local_merge_live
)
4030 && !sets_cc0_p (insn
)
4038 df_simulate_one_insn_backwards (merge_bb
, insn
,
4046 insn
= PREV_INSN (insn
);
4053 *pmove_upto
= max_to
;
4055 /* For small register class machines, don't lengthen lifetimes of
4056 hard registers before reload. */
4057 if (! reload_completed
4058 && targetm
.small_register_classes_for_mode_p (VOIDmode
))
4060 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
4062 if (i
< FIRST_PSEUDO_REGISTER
4064 && ! global_regs
[i
])
4070 BITMAP_FREE (merge_set
);
4071 BITMAP_FREE (merge_use
);
4072 BITMAP_FREE (local_merge_live
);
4073 BITMAP_FREE (test_set
);
4074 BITMAP_FREE (test_use
);
4080 /*----------------------------------------------------------------------------
4081 MULTIPLE DEFINITIONS
4083 Find the locations in the function reached by multiple definition sites
4084 for a live pseudo. In and out bitvectors are built for each basic
4085 block. They are restricted for efficiency to live registers.
4087 The gen and kill sets for the problem are obvious. Together they
4088 include all defined registers in a basic block; the gen set includes
4089 registers where a partial or conditional or may-clobber definition is
4090 last in the BB, while the kill set includes registers with a complete
4091 definition coming last. However, the computation of the dataflow
4092 itself is interesting.
4094 The idea behind it comes from SSA form's iterated dominance frontier
4095 criterion for inserting PHI functions. Just like in that case, we can use
4096 the dominance frontier to find places where multiple definitions meet;
4097 a register X defined in a basic block BB1 has multiple definitions in
4098 basic blocks in BB1's dominance frontier.
4100 So, the in-set of a basic block BB2 is not just the union of the
4101 out-sets of BB2's predecessors, but includes some more bits that come
4102 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4103 the previous paragraph). I called this set the init-set of BB2.
4105 (Note: I actually use the kill-set only to build the init-set.
4106 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4108 For example, if you have
4112 if <...> goto BB2 else goto BB3;
4120 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4121 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4122 not need to iterate the dominance frontier, because we do not insert
4123 anything like PHI functions there! Instead, dataflow will take care of
4124 propagating the information to BB3's successors.
4125 ---------------------------------------------------------------------------*/
4127 /* Private data used to verify the solution for this problem. */
4128 struct df_md_problem_data
4130 /* An obstack for the bitmaps we need for this problem. */
4131 bitmap_obstack md_bitmaps
;
4134 /* Scratch var used by transfer functions. This is used to do md analysis
4135 only for live registers. */
4136 static bitmap_head df_md_scratch
;
4140 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
4143 struct df_md_bb_info
*bb_info
= (struct df_md_bb_info
*) vbb_info
;
4146 bitmap_clear (&bb_info
->kill
);
4147 bitmap_clear (&bb_info
->gen
);
4148 bitmap_clear (&bb_info
->init
);
4149 bitmap_clear (&bb_info
->in
);
4150 bitmap_clear (&bb_info
->out
);
4155 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4156 not touched unless the block is new. */
4159 df_md_alloc (bitmap all_blocks
)
4161 unsigned int bb_index
;
4163 struct df_md_problem_data
*problem_data
;
4165 df_grow_bb_info (df_md
);
4166 if (df_md
->problem_data
)
4167 problem_data
= (struct df_md_problem_data
*) df_md
->problem_data
;
4170 problem_data
= XNEW (struct df_md_problem_data
);
4171 df_md
->problem_data
= problem_data
;
4172 bitmap_obstack_initialize (&problem_data
->md_bitmaps
);
4174 bitmap_initialize (&df_md_scratch
, &problem_data
->md_bitmaps
);
4176 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4178 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4179 /* When bitmaps are already initialized, just clear them. */
4180 if (bb_info
->init
.obstack
)
4182 bitmap_clear (&bb_info
->init
);
4183 bitmap_clear (&bb_info
->gen
);
4184 bitmap_clear (&bb_info
->kill
);
4185 bitmap_clear (&bb_info
->in
);
4186 bitmap_clear (&bb_info
->out
);
4190 bitmap_initialize (&bb_info
->init
, &problem_data
->md_bitmaps
);
4191 bitmap_initialize (&bb_info
->gen
, &problem_data
->md_bitmaps
);
4192 bitmap_initialize (&bb_info
->kill
, &problem_data
->md_bitmaps
);
4193 bitmap_initialize (&bb_info
->in
, &problem_data
->md_bitmaps
);
4194 bitmap_initialize (&bb_info
->out
, &problem_data
->md_bitmaps
);
4198 df_md
->optional_p
= true;
4201 /* Add the effect of the top artificial defs of BB to the multiple definitions
4205 df_md_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_md
)
4207 int bb_index
= bb
->index
;
4209 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4211 df_ref def
= *def_rec
;
4212 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4214 unsigned int dregno
= DF_REF_REGNO (def
);
4215 if (DF_REF_FLAGS (def
)
4216 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4217 bitmap_set_bit (local_md
, dregno
);
4219 bitmap_clear_bit (local_md
, dregno
);
4225 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4229 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
4232 unsigned uid
= INSN_UID (insn
);
4235 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4237 df_ref def
= *def_rec
;
4238 unsigned int dregno
= DF_REF_REGNO (def
);
4239 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4240 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4242 if (DF_REF_FLAGS (def
)
4243 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4244 bitmap_set_bit (local_md
, DF_REF_ID (def
));
4246 bitmap_clear_bit (local_md
, DF_REF_ID (def
));
4252 df_md_bb_local_compute_process_def (struct df_md_bb_info
*bb_info
,
4257 bitmap_clear (&seen_in_insn
);
4259 while ((def
= *def_rec
++) != NULL
)
4261 unsigned int dregno
= DF_REF_REGNO (def
);
4262 if (((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4263 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4264 && top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
4266 if (!bitmap_bit_p (&seen_in_insn
, dregno
))
4268 if (DF_REF_FLAGS (def
)
4269 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4271 bitmap_set_bit (&bb_info
->gen
, dregno
);
4272 bitmap_clear_bit (&bb_info
->kill
, dregno
);
4276 /* When we find a clobber and a regular def,
4277 make sure the regular def wins. */
4278 bitmap_set_bit (&seen_in_insn
, dregno
);
4279 bitmap_set_bit (&bb_info
->kill
, dregno
);
4280 bitmap_clear_bit (&bb_info
->gen
, dregno
);
4288 /* Compute local multiple def info for basic block BB. */
4291 df_md_bb_local_compute (unsigned int bb_index
)
4293 basic_block bb
= BASIC_BLOCK (bb_index
);
4294 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4297 /* Artificials are only hard regs. */
4298 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4299 df_md_bb_local_compute_process_def (bb_info
,
4300 df_get_artificial_defs (bb_index
),
4303 FOR_BB_INSNS (bb
, insn
)
4305 unsigned int uid
= INSN_UID (insn
);
4309 df_md_bb_local_compute_process_def (bb_info
, DF_INSN_UID_DEFS (uid
), 0);
4312 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4313 df_md_bb_local_compute_process_def (bb_info
,
4314 df_get_artificial_defs (bb_index
),
4318 /* Compute local reaching def info for each basic block within BLOCKS. */
4321 df_md_local_compute (bitmap all_blocks
)
4323 unsigned int bb_index
, df_bb_index
;
4324 bitmap_iterator bi1
, bi2
;
4326 bitmap_head
*frontiers
;
4328 bitmap_initialize (&seen_in_insn
, &bitmap_default_obstack
);
4330 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4332 df_md_bb_local_compute (bb_index
);
4335 bitmap_clear (&seen_in_insn
);
4337 frontiers
= XNEWVEC (bitmap_head
, last_basic_block
);
4339 bitmap_initialize (&frontiers
[bb
->index
], &bitmap_default_obstack
);
4341 compute_dominance_frontiers (frontiers
);
4343 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4344 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4346 bitmap kill
= &df_md_get_bb_info (bb_index
)->kill
;
4347 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[bb_index
], 0, df_bb_index
, bi2
)
4349 basic_block bb
= BASIC_BLOCK (df_bb_index
);
4350 if (bitmap_bit_p (all_blocks
, df_bb_index
))
4351 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index
)->init
, kill
,
4352 df_get_live_in (bb
));
4357 bitmap_clear (&frontiers
[bb
->index
]);
4362 /* Reset the global solution for recalculation. */
4365 df_md_reset (bitmap all_blocks
)
4367 unsigned int bb_index
;
4370 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4372 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4373 gcc_assert (bb_info
);
4374 bitmap_clear (&bb_info
->in
);
4375 bitmap_clear (&bb_info
->out
);
4380 df_md_transfer_function (int bb_index
)
4382 basic_block bb
= BASIC_BLOCK (bb_index
);
4383 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4384 bitmap in
= &bb_info
->in
;
4385 bitmap out
= &bb_info
->out
;
4386 bitmap gen
= &bb_info
->gen
;
4387 bitmap kill
= &bb_info
->kill
;
4389 /* We need to use a scratch set here so that the value returned from this
4390 function invocation properly reflects whether the sets changed in a
4391 significant way; i.e. not just because the live set was anded in. */
4392 bitmap_and (&df_md_scratch
, gen
, df_get_live_out (bb
));
4394 /* Multiple definitions of a register are not relevant if it is not
4395 live. Thus we trim the result to the places where it is live. */
4396 bitmap_and_into (in
, df_get_live_in (bb
));
4398 return bitmap_ior_and_compl (out
, &df_md_scratch
, in
, kill
);
4401 /* Initialize the solution bit vectors for problem. */
4404 df_md_init (bitmap all_blocks
)
4406 unsigned int bb_index
;
4409 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4411 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4413 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4414 df_md_transfer_function (bb_index
);
4419 df_md_confluence_0 (basic_block bb
)
4421 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4422 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4425 /* In of target gets or of out of source. */
4428 df_md_confluence_n (edge e
)
4430 bitmap op1
= &df_md_get_bb_info (e
->dest
->index
)->in
;
4431 bitmap op2
= &df_md_get_bb_info (e
->src
->index
)->out
;
4433 if (e
->flags
& EDGE_FAKE
)
4436 if (e
->flags
& EDGE_EH
)
4437 return bitmap_ior_and_compl_into (op1
, op2
,
4438 regs_invalidated_by_call_regset
);
4440 return bitmap_ior_into (op1
, op2
);
4443 /* Free all storage associated with the problem. */
4448 struct df_md_problem_data
*problem_data
4449 = (struct df_md_problem_data
*) df_md
->problem_data
;
4451 bitmap_obstack_release (&problem_data
->md_bitmaps
);
4452 free (problem_data
);
4453 df_md
->problem_data
= NULL
;
4455 df_md
->block_info_size
= 0;
4456 free (df_md
->block_info
);
4457 df_md
->block_info
= NULL
;
4462 /* Debugging info at top of bb. */
4465 df_md_top_dump (basic_block bb
, FILE *file
)
4467 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4471 fprintf (file
, ";; md in \t");
4472 df_print_regset (file
, &bb_info
->in
);
4473 fprintf (file
, ";; md init \t");
4474 df_print_regset (file
, &bb_info
->init
);
4475 fprintf (file
, ";; md gen \t");
4476 df_print_regset (file
, &bb_info
->gen
);
4477 fprintf (file
, ";; md kill \t");
4478 df_print_regset (file
, &bb_info
->kill
);
4481 /* Debugging info at bottom of bb. */
4484 df_md_bottom_dump (basic_block bb
, FILE *file
)
4486 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4490 fprintf (file
, ";; md out \t");
4491 df_print_regset (file
, &bb_info
->out
);
4494 static struct df_problem problem_MD
=
4496 DF_MD
, /* Problem id. */
4497 DF_FORWARD
, /* Direction. */
4498 df_md_alloc
, /* Allocate the problem specific data. */
4499 df_md_reset
, /* Reset global information. */
4500 df_md_free_bb_info
, /* Free basic block info. */
4501 df_md_local_compute
, /* Local compute function. */
4502 df_md_init
, /* Init the solution specific data. */
4503 df_worklist_dataflow
, /* Worklist solver. */
4504 df_md_confluence_0
, /* Confluence operator 0. */
4505 df_md_confluence_n
, /* Confluence operator n. */
4506 df_md_transfer_function
, /* Transfer function. */
4507 NULL
, /* Finalize function. */
4508 df_md_free
, /* Free all of the problem information. */
4509 df_md_free
, /* Remove this problem from the stack of dataflow problems. */
4510 NULL
, /* Debugging. */
4511 df_md_top_dump
, /* Debugging start block. */
4512 df_md_bottom_dump
, /* Debugging end block. */
4513 NULL
, /* Debugging start insn. */
4514 NULL
, /* Debugging end insn. */
4515 NULL
, /* Incremental solution verify start. */
4516 NULL
, /* Incremental solution verify end. */
4517 NULL
, /* Dependent problem. */
4518 sizeof (struct df_md_bb_info
),/* Size of entry of block_info array. */
4519 TV_DF_MD
, /* Timing variable. */
4520 false /* Reset blocks on dropping out of blocks_to_analyze. */
4523 /* Create a new MD instance and add it to the existing instance
4527 df_md_add_problem (void)
4529 df_add_problem (&problem_MD
);