1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
31 #include "insn-config.h"
35 #include "alloc-pool.h"
37 #include "hard-reg-set.h"
38 #include "basic-block.h"
49 /* Note that turning REG_DEAD_DEBUGGING on will cause
50 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
51 addresses in the dumps. */
52 #define REG_DEAD_DEBUGGING 0
54 #define DF_SPARSE_THRESHOLD 32
56 static bitmap_head seen_in_block
;
57 static bitmap_head seen_in_insn
;
60 /*----------------------------------------------------------------------------
61 Public functions access functions for the dataflow problems.
62 ----------------------------------------------------------------------------*/
63 /* Get the live at out set for BB no matter what problem happens to be
64 defined. This function is used by the register allocators who
65 choose different dataflow problems depending on the optimization
69 df_get_live_out (basic_block bb
)
74 return DF_LIVE_OUT (bb
);
76 return DF_LR_OUT (bb
);
79 /* Get the live at in set for BB no matter what problem happens to be
80 defined. This function is used by the register allocators who
81 choose different dataflow problems depending on the optimization
85 df_get_live_in (basic_block bb
)
90 return DF_LIVE_IN (bb
);
95 /*----------------------------------------------------------------------------
97 ----------------------------------------------------------------------------*/
99 /* Generic versions to get the void* version of the block info. Only
100 used inside the problem instance vectors. */
102 /* Dump a def-use or use-def chain for REF to FILE. */
105 df_chain_dump (struct df_link
*link
, FILE *file
)
107 fprintf (file
, "{ ");
108 for (; link
; link
= link
->next
)
110 fprintf (file
, "%c%d(bb %d insn %d) ",
111 DF_REF_REG_DEF_P (link
->ref
)
113 : (DF_REF_FLAGS (link
->ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
114 DF_REF_ID (link
->ref
),
115 DF_REF_BBNO (link
->ref
),
116 DF_REF_IS_ARTIFICIAL (link
->ref
)
117 ? -1 : DF_REF_INSN_UID (link
->ref
));
123 /* Print some basic block info as part of df_dump. */
126 df_print_bb_index (basic_block bb
, FILE *file
)
131 fprintf (file
, "\n( ");
132 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
134 basic_block pred
= e
->src
;
135 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
137 fprintf (file
, ")->[%d]->( ", bb
->index
);
138 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
140 basic_block succ
= e
->dest
;
141 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
143 fprintf (file
, ")\n");
147 /*----------------------------------------------------------------------------
150 Find the locations in the function where each definition site for a
151 pseudo reaches. In and out bitvectors are built for each basic
152 block. The id field in the ref is used to index into these sets.
153 See df.h for details.
154 ----------------------------------------------------------------------------*/
156 /* This problem plays a large number of games for the sake of
159 1) The order of the bits in the bitvectors. After the scanning
160 phase, all of the defs are sorted. All of the defs for the reg 0
161 are first, followed by all defs for reg 1 and so on.
163 2) There are two kill sets, one if the number of defs is less or
164 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
167 <= : Data is built directly in the kill set.
169 > : One level of indirection is used to keep from generating long
170 strings of 1 bits in the kill sets. Bitvectors that are indexed
171 by the regnum are used to represent that there is a killing def
172 for the register. The confluence and transfer functions use
173 these along with the bitmap_clear_range call to remove ranges of
174 bits without actually generating a knockout vector.
176 The kill and sparse_kill and the dense_invalidated_by_call and
177 sparse_invalidated_by_call both play this game. */
179 /* Private data used to compute the solution for this problem. These
180 data structures are not accessible outside of this module. */
181 struct df_rd_problem_data
183 /* The set of defs to regs invalidated by call. */
184 bitmap_head sparse_invalidated_by_call
;
185 /* The set of defs to regs invalidate by call for rd. */
186 bitmap_head dense_invalidated_by_call
;
187 /* An obstack for the bitmaps we need for this problem. */
188 bitmap_obstack rd_bitmaps
;
192 /* Free basic block info. */
195 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
198 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
201 bitmap_clear (&bb_info
->kill
);
202 bitmap_clear (&bb_info
->sparse_kill
);
203 bitmap_clear (&bb_info
->gen
);
204 bitmap_clear (&bb_info
->in
);
205 bitmap_clear (&bb_info
->out
);
210 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
211 not touched unless the block is new. */
214 df_rd_alloc (bitmap all_blocks
)
216 unsigned int bb_index
;
218 struct df_rd_problem_data
*problem_data
;
220 if (df_rd
->problem_data
)
222 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
223 bitmap_clear (&problem_data
->sparse_invalidated_by_call
);
224 bitmap_clear (&problem_data
->dense_invalidated_by_call
);
228 problem_data
= XNEW (struct df_rd_problem_data
);
229 df_rd
->problem_data
= problem_data
;
231 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
232 bitmap_initialize (&problem_data
->sparse_invalidated_by_call
,
233 &problem_data
->rd_bitmaps
);
234 bitmap_initialize (&problem_data
->dense_invalidated_by_call
,
235 &problem_data
->rd_bitmaps
);
238 df_grow_bb_info (df_rd
);
240 /* Because of the clustering of all use sites for the same pseudo,
241 we have to process all of the blocks before doing the
244 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
246 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
248 /* When bitmaps are already initialized, just clear them. */
249 if (bb_info
->kill
.obstack
)
251 bitmap_clear (&bb_info
->kill
);
252 bitmap_clear (&bb_info
->sparse_kill
);
253 bitmap_clear (&bb_info
->gen
);
257 bitmap_initialize (&bb_info
->kill
, &problem_data
->rd_bitmaps
);
258 bitmap_initialize (&bb_info
->sparse_kill
, &problem_data
->rd_bitmaps
);
259 bitmap_initialize (&bb_info
->gen
, &problem_data
->rd_bitmaps
);
260 bitmap_initialize (&bb_info
->in
, &problem_data
->rd_bitmaps
);
261 bitmap_initialize (&bb_info
->out
, &problem_data
->rd_bitmaps
);
264 df_rd
->optional_p
= true;
268 /* Add the effect of the top artificial defs of BB to the reaching definitions
272 df_rd_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_rd
)
274 int bb_index
= bb
->index
;
276 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
278 df_ref def
= *def_rec
;
279 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
281 unsigned int dregno
= DF_REF_REGNO (def
);
282 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
283 bitmap_clear_range (local_rd
,
284 DF_DEFS_BEGIN (dregno
),
285 DF_DEFS_COUNT (dregno
));
286 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
291 /* Add the effect of the defs of INSN to the reaching definitions bitmap
295 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
298 unsigned uid
= INSN_UID (insn
);
301 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
303 df_ref def
= *def_rec
;
304 unsigned int dregno
= DF_REF_REGNO (def
);
305 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
306 || (dregno
>= FIRST_PSEUDO_REGISTER
))
308 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
309 bitmap_clear_range (local_rd
,
310 DF_DEFS_BEGIN (dregno
),
311 DF_DEFS_COUNT (dregno
));
312 if (!(DF_REF_FLAGS (def
)
313 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
314 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
319 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
320 more complicated than just simulating, because we must produce the
321 gen and kill sets and hence deal with the two possible representations
325 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
331 df_ref def
= *def_rec
;
332 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
334 unsigned int regno
= DF_REF_REGNO (def
);
335 unsigned int begin
= DF_DEFS_BEGIN (regno
);
336 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
338 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
339 || (regno
>= FIRST_PSEUDO_REGISTER
))
341 /* Only the last def(s) for a regno in the block has any
343 if (!bitmap_bit_p (&seen_in_block
, regno
))
345 /* The first def for regno in insn gets to knock out the
346 defs from other instructions. */
347 if ((!bitmap_bit_p (&seen_in_insn
, regno
))
348 /* If the def is to only part of the reg, it does
349 not kill the other defs that reach here. */
350 && (!(DF_REF_FLAGS (def
) &
351 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
353 if (n_defs
> DF_SPARSE_THRESHOLD
)
355 bitmap_set_bit (&bb_info
->sparse_kill
, regno
);
356 bitmap_clear_range(&bb_info
->gen
, begin
, n_defs
);
360 bitmap_set_range (&bb_info
->kill
, begin
, n_defs
);
361 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
365 bitmap_set_bit (&seen_in_insn
, regno
);
366 /* All defs for regno in the instruction may be put into
368 if (!(DF_REF_FLAGS (def
)
369 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
370 bitmap_set_bit (&bb_info
->gen
, DF_REF_ID (def
));
378 /* Compute local reaching def info for basic block BB. */
381 df_rd_bb_local_compute (unsigned int bb_index
)
383 basic_block bb
= BASIC_BLOCK (bb_index
);
384 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
387 bitmap_clear (&seen_in_block
);
388 bitmap_clear (&seen_in_insn
);
390 /* Artificials are only hard regs. */
391 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
392 df_rd_bb_local_compute_process_def (bb_info
,
393 df_get_artificial_defs (bb_index
),
396 FOR_BB_INSNS_REVERSE (bb
, insn
)
398 unsigned int uid
= INSN_UID (insn
);
403 df_rd_bb_local_compute_process_def (bb_info
,
404 DF_INSN_UID_DEFS (uid
), 0);
406 /* This complex dance with the two bitmaps is required because
407 instructions can assign twice to the same pseudo. This
408 generally happens with calls that will have one def for the
409 result and another def for the clobber. If only one vector
410 is used and the clobber goes first, the result will be
412 bitmap_ior_into (&seen_in_block
, &seen_in_insn
);
413 bitmap_clear (&seen_in_insn
);
416 /* Process the artificial defs at the top of the block last since we
417 are going backwards through the block and these are logically at
419 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
420 df_rd_bb_local_compute_process_def (bb_info
,
421 df_get_artificial_defs (bb_index
),
426 /* Compute local reaching def info for each basic block within BLOCKS. */
429 df_rd_local_compute (bitmap all_blocks
)
431 unsigned int bb_index
;
434 struct df_rd_problem_data
*problem_data
435 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
436 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
437 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
439 bitmap_initialize (&seen_in_block
, &df_bitmap_obstack
);
440 bitmap_initialize (&seen_in_insn
, &df_bitmap_obstack
);
442 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
444 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
446 df_rd_bb_local_compute (bb_index
);
449 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
450 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset
, 0, regno
, bi
)
452 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
453 bitmap_set_bit (sparse_invalidated
, regno
);
455 bitmap_set_range (dense_invalidated
,
456 DF_DEFS_BEGIN (regno
),
457 DF_DEFS_COUNT (regno
));
460 bitmap_clear (&seen_in_block
);
461 bitmap_clear (&seen_in_insn
);
465 /* Initialize the solution bit vectors for problem. */
468 df_rd_init_solution (bitmap all_blocks
)
470 unsigned int bb_index
;
473 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
475 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
477 bitmap_copy (&bb_info
->out
, &bb_info
->gen
);
478 bitmap_clear (&bb_info
->in
);
482 /* In of target gets or of out of source. */
485 df_rd_confluence_n (edge e
)
487 bitmap op1
= &df_rd_get_bb_info (e
->dest
->index
)->in
;
488 bitmap op2
= &df_rd_get_bb_info (e
->src
->index
)->out
;
489 bool changed
= false;
491 if (e
->flags
& EDGE_FAKE
)
494 if (e
->flags
& EDGE_EH
)
496 struct df_rd_problem_data
*problem_data
497 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
498 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
499 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
504 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
505 bitmap_copy (&tmp
, op2
);
506 bitmap_and_compl_into (&tmp
, dense_invalidated
);
508 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
510 bitmap_clear_range (&tmp
,
511 DF_DEFS_BEGIN (regno
),
512 DF_DEFS_COUNT (regno
));
514 changed
|= bitmap_ior_into (op1
, &tmp
);
519 return bitmap_ior_into (op1
, op2
);
523 /* Transfer function. */
526 df_rd_transfer_function (int bb_index
)
528 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
531 bitmap in
= &bb_info
->in
;
532 bitmap out
= &bb_info
->out
;
533 bitmap gen
= &bb_info
->gen
;
534 bitmap kill
= &bb_info
->kill
;
535 bitmap sparse_kill
= &bb_info
->sparse_kill
;
537 if (bitmap_empty_p (sparse_kill
))
538 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
541 struct df_rd_problem_data
*problem_data
;
542 bool changed
= false;
545 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
546 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
547 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
548 bitmap_initialize (&tmp
, &problem_data
->rd_bitmaps
);
550 bitmap_copy (&tmp
, in
);
551 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
553 bitmap_clear_range (&tmp
,
554 DF_DEFS_BEGIN (regno
),
555 DF_DEFS_COUNT (regno
));
557 bitmap_and_compl_into (&tmp
, kill
);
558 bitmap_ior_into (&tmp
, gen
);
559 changed
= !bitmap_equal_p (&tmp
, out
);
572 /* Free all storage associated with the problem. */
577 struct df_rd_problem_data
*problem_data
578 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
582 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
584 df_rd
->block_info_size
= 0;
585 free (df_rd
->block_info
);
586 df_rd
->block_info
= NULL
;
587 free (df_rd
->problem_data
);
593 /* Debugging info. */
596 df_rd_start_dump (FILE *file
)
598 struct df_rd_problem_data
*problem_data
599 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
600 unsigned int m
= DF_REG_SIZE(df
);
603 if (!df_rd
->block_info
)
606 fprintf (file
, ";; Reaching defs:\n\n");
608 fprintf (file
, " sparse invalidated \t");
609 dump_bitmap (file
, &problem_data
->sparse_invalidated_by_call
);
610 fprintf (file
, " dense invalidated \t");
611 dump_bitmap (file
, &problem_data
->dense_invalidated_by_call
);
613 for (regno
= 0; regno
< m
; regno
++)
614 if (DF_DEFS_COUNT (regno
))
615 fprintf (file
, "%d[%d,%d] ", regno
,
616 DF_DEFS_BEGIN (regno
),
617 DF_DEFS_COUNT (regno
));
618 fprintf (file
, "\n");
623 /* Debugging info at top of bb. */
626 df_rd_top_dump (basic_block bb
, FILE *file
)
628 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
632 fprintf (file
, ";; rd in \t(%d)\n", (int) bitmap_count_bits (&bb_info
->in
));
633 dump_bitmap (file
, &bb_info
->in
);
634 fprintf (file
, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (&bb_info
->gen
));
635 dump_bitmap (file
, &bb_info
->gen
);
636 fprintf (file
, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (&bb_info
->kill
));
637 dump_bitmap (file
, &bb_info
->kill
);
641 /* Debugging info at top of bb. */
644 df_rd_bottom_dump (basic_block bb
, FILE *file
)
646 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
650 fprintf (file
, ";; rd out \t(%d)\n", (int) bitmap_count_bits (&bb_info
->out
));
651 dump_bitmap (file
, &bb_info
->out
);
654 /* All of the information associated with every instance of the problem. */
656 static struct df_problem problem_RD
=
658 DF_RD
, /* Problem id. */
659 DF_FORWARD
, /* Direction. */
660 df_rd_alloc
, /* Allocate the problem specific data. */
661 NULL
, /* Reset global information. */
662 df_rd_free_bb_info
, /* Free basic block info. */
663 df_rd_local_compute
, /* Local compute function. */
664 df_rd_init_solution
, /* Init the solution specific data. */
665 df_worklist_dataflow
, /* Worklist solver. */
666 NULL
, /* Confluence operator 0. */
667 df_rd_confluence_n
, /* Confluence operator n. */
668 df_rd_transfer_function
, /* Transfer function. */
669 NULL
, /* Finalize function. */
670 df_rd_free
, /* Free all of the problem information. */
671 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
672 df_rd_start_dump
, /* Debugging. */
673 df_rd_top_dump
, /* Debugging start block. */
674 df_rd_bottom_dump
, /* Debugging end block. */
675 NULL
, /* Incremental solution verify start. */
676 NULL
, /* Incremental solution verify end. */
677 NULL
, /* Dependent problem. */
678 sizeof (struct df_rd_bb_info
),/* Size of entry of block_info array. */
679 TV_DF_RD
, /* Timing variable. */
680 true /* Reset blocks on dropping out of blocks_to_analyze. */
685 /* Create a new RD instance and add it to the existing instance
689 df_rd_add_problem (void)
691 df_add_problem (&problem_RD
);
696 /*----------------------------------------------------------------------------
699 Find the locations in the function where any use of a pseudo can
700 reach in the backwards direction. In and out bitvectors are built
701 for each basic block. The regno is used to index into these sets.
702 See df.h for details.
703 ----------------------------------------------------------------------------*/
705 /* Private data used to verify the solution for this problem. */
706 struct df_lr_problem_data
710 /* An obstack for the bitmaps we need for this problem. */
711 bitmap_obstack lr_bitmaps
;
714 /* Free basic block info. */
717 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
720 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
723 bitmap_clear (&bb_info
->use
);
724 bitmap_clear (&bb_info
->def
);
725 bitmap_clear (&bb_info
->in
);
726 bitmap_clear (&bb_info
->out
);
731 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
732 not touched unless the block is new. */
735 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
737 unsigned int bb_index
;
739 struct df_lr_problem_data
*problem_data
;
741 df_grow_bb_info (df_lr
);
742 if (df_lr
->problem_data
)
743 problem_data
= (struct df_lr_problem_data
*) df_lr
->problem_data
;
746 problem_data
= XNEW (struct df_lr_problem_data
);
747 df_lr
->problem_data
= problem_data
;
749 problem_data
->out
= NULL
;
750 problem_data
->in
= NULL
;
751 bitmap_obstack_initialize (&problem_data
->lr_bitmaps
);
754 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
756 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
758 /* When bitmaps are already initialized, just clear them. */
759 if (bb_info
->use
.obstack
)
761 bitmap_clear (&bb_info
->def
);
762 bitmap_clear (&bb_info
->use
);
766 bitmap_initialize (&bb_info
->use
, &problem_data
->lr_bitmaps
);
767 bitmap_initialize (&bb_info
->def
, &problem_data
->lr_bitmaps
);
768 bitmap_initialize (&bb_info
->in
, &problem_data
->lr_bitmaps
);
769 bitmap_initialize (&bb_info
->out
, &problem_data
->lr_bitmaps
);
773 df_lr
->optional_p
= false;
777 /* Reset the global solution for recalculation. */
780 df_lr_reset (bitmap all_blocks
)
782 unsigned int bb_index
;
785 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
787 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
788 gcc_assert (bb_info
);
789 bitmap_clear (&bb_info
->in
);
790 bitmap_clear (&bb_info
->out
);
795 /* Compute local live register info for basic block BB. */
798 df_lr_bb_local_compute (unsigned int bb_index
)
800 basic_block bb
= BASIC_BLOCK (bb_index
);
801 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
806 /* Process the registers set in an exception handler. */
807 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
809 df_ref def
= *def_rec
;
810 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
812 unsigned int dregno
= DF_REF_REGNO (def
);
813 bitmap_set_bit (&bb_info
->def
, dregno
);
814 bitmap_clear_bit (&bb_info
->use
, dregno
);
818 /* Process the hardware registers that are always live. */
819 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
821 df_ref use
= *use_rec
;
822 /* Add use to set of uses in this BB. */
823 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
824 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
827 FOR_BB_INSNS_REVERSE (bb
, insn
)
829 unsigned int uid
= INSN_UID (insn
);
831 if (!NONDEBUG_INSN_P (insn
))
834 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
836 df_ref def
= *def_rec
;
837 /* If the def is to only part of the reg, it does
838 not kill the other defs that reach here. */
839 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
841 unsigned int dregno
= DF_REF_REGNO (def
);
842 bitmap_set_bit (&bb_info
->def
, dregno
);
843 bitmap_clear_bit (&bb_info
->use
, dregno
);
847 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
849 df_ref use
= *use_rec
;
850 /* Add use to set of uses in this BB. */
851 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
855 /* Process the registers set in an exception handler or the hard
856 frame pointer if this block is the target of a non local
858 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
860 df_ref def
= *def_rec
;
861 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
863 unsigned int dregno
= DF_REF_REGNO (def
);
864 bitmap_set_bit (&bb_info
->def
, dregno
);
865 bitmap_clear_bit (&bb_info
->use
, dregno
);
870 /* Process the uses that are live into an exception handler. */
871 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
873 df_ref use
= *use_rec
;
874 /* Add use to set of uses in this BB. */
875 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
876 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
880 /* If the df_live problem is not defined, such as at -O0 and -O1, we
881 still need to keep the luids up to date. This is normally done
882 in the df_live problem since this problem has a forwards
885 df_recompute_luids (bb
);
889 /* Compute local live register info for each basic block within BLOCKS. */
892 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
894 unsigned int bb_index
;
897 bitmap_clear (&df
->hardware_regs_used
);
899 /* The all-important stack pointer must always be live. */
900 bitmap_set_bit (&df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
902 /* Before reload, there are a few registers that must be forced
903 live everywhere -- which might not already be the case for
904 blocks within infinite loops. */
905 if (!reload_completed
)
907 unsigned int pic_offset_table_regnum
= PIC_OFFSET_TABLE_REGNUM
;
908 /* Any reference to any pseudo before reload is a potential
909 reference of the frame pointer. */
910 bitmap_set_bit (&df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
912 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
913 /* Pseudos with argument area equivalences may require
914 reloading via the argument pointer. */
915 if (fixed_regs
[ARG_POINTER_REGNUM
])
916 bitmap_set_bit (&df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
919 /* Any constant, or pseudo with constant equivalences, may
920 require reloading from memory using the pic register. */
921 if (pic_offset_table_regnum
!= INVALID_REGNUM
922 && fixed_regs
[pic_offset_table_regnum
])
923 bitmap_set_bit (&df
->hardware_regs_used
, pic_offset_table_regnum
);
926 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
928 if (bb_index
== EXIT_BLOCK
)
930 /* The exit block is special for this problem and its bits are
931 computed from thin air. */
932 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
933 bitmap_copy (&bb_info
->use
, df
->exit_block_uses
);
936 df_lr_bb_local_compute (bb_index
);
939 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
943 /* Initialize the solution vectors. */
946 df_lr_init (bitmap all_blocks
)
948 unsigned int bb_index
;
951 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
953 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
954 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
955 bitmap_clear (&bb_info
->out
);
960 /* Confluence function that processes infinite loops. This might be a
961 noreturn function that throws. And even if it isn't, getting the
962 unwind info right helps debugging. */
964 df_lr_confluence_0 (basic_block bb
)
966 bitmap op1
= &df_lr_get_bb_info (bb
->index
)->out
;
967 if (bb
!= EXIT_BLOCK_PTR
)
968 bitmap_copy (op1
, &df
->hardware_regs_used
);
972 /* Confluence function that ignores fake edges. */
975 df_lr_confluence_n (edge e
)
977 bitmap op1
= &df_lr_get_bb_info (e
->src
->index
)->out
;
978 bitmap op2
= &df_lr_get_bb_info (e
->dest
->index
)->in
;
979 bool changed
= false;
981 /* Call-clobbered registers die across exception and call edges. */
982 /* ??? Abnormal call edges ignored for the moment, as this gets
983 confused by sibling call edges, which crashes reg-stack. */
984 if (e
->flags
& EDGE_EH
)
985 changed
= bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
987 changed
= bitmap_ior_into (op1
, op2
);
989 changed
|= bitmap_ior_into (op1
, &df
->hardware_regs_used
);
994 /* Transfer function. */
997 df_lr_transfer_function (int bb_index
)
999 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1000 bitmap in
= &bb_info
->in
;
1001 bitmap out
= &bb_info
->out
;
1002 bitmap use
= &bb_info
->use
;
1003 bitmap def
= &bb_info
->def
;
1005 return bitmap_ior_and_compl (in
, use
, out
, def
);
1009 /* Run the fast dce as a side effect of building LR. */
1012 df_lr_finalize (bitmap all_blocks
)
1014 df_lr
->solutions_dirty
= false;
1015 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1019 /* If dce deletes some instructions, we need to recompute the lr
1020 solution before proceeding further. The problem is that fast
1021 dce is a pessimestic dataflow algorithm. In the case where
1022 it deletes a statement S inside of a loop, the uses inside of
1023 S may not be deleted from the dataflow solution because they
1024 were carried around the loop. While it is conservatively
1025 correct to leave these extra bits, the standards of df
1026 require that we maintain the best possible (least fixed
1027 point) solution. The only way to do that is to redo the
1028 iteration from the beginning. See PR35805 for an
1030 if (df_lr
->solutions_dirty
)
1032 df_clear_flags (DF_LR_RUN_DCE
);
1033 df_lr_alloc (all_blocks
);
1034 df_lr_local_compute (all_blocks
);
1035 df_worklist_dataflow (df_lr
, all_blocks
, df
->postorder
, df
->n_blocks
);
1036 df_lr_finalize (all_blocks
);
1037 df_set_flags (DF_LR_RUN_DCE
);
1043 /* Free all storage associated with the problem. */
1048 struct df_lr_problem_data
*problem_data
1049 = (struct df_lr_problem_data
*) df_lr
->problem_data
;
1050 if (df_lr
->block_info
)
1053 df_lr
->block_info_size
= 0;
1054 free (df_lr
->block_info
);
1055 df_lr
->block_info
= NULL
;
1056 bitmap_obstack_release (&problem_data
->lr_bitmaps
);
1057 free (df_lr
->problem_data
);
1058 df_lr
->problem_data
= NULL
;
1061 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1066 /* Debugging info at top of bb. */
1069 df_lr_top_dump (basic_block bb
, FILE *file
)
1071 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1072 struct df_lr_problem_data
*problem_data
;
1076 fprintf (file
, ";; lr in \t");
1077 df_print_regset (file
, &bb_info
->in
);
1078 if (df_lr
->problem_data
)
1080 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1081 if (problem_data
->in
)
1083 fprintf (file
, ";; old in \t");
1084 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1087 fprintf (file
, ";; lr use \t");
1088 df_print_regset (file
, &bb_info
->use
);
1089 fprintf (file
, ";; lr def \t");
1090 df_print_regset (file
, &bb_info
->def
);
1094 /* Debugging info at bottom of bb. */
1097 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1099 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1100 struct df_lr_problem_data
*problem_data
;
1104 fprintf (file
, ";; lr out \t");
1105 df_print_regset (file
, &bb_info
->out
);
1106 if (df_lr
->problem_data
)
1108 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1109 if (problem_data
->out
)
1111 fprintf (file
, ";; old out \t");
1112 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1118 /* Build the datastructure to verify that the solution to the dataflow
1119 equations is not dirty. */
1122 df_lr_verify_solution_start (void)
1125 struct df_lr_problem_data
*problem_data
;
1126 if (df_lr
->solutions_dirty
)
1129 /* Set it true so that the solution is recomputed. */
1130 df_lr
->solutions_dirty
= true;
1132 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1133 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block
);
1134 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block
);
1138 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->lr_bitmaps
);
1139 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->lr_bitmaps
);
1140 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1141 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1146 /* Compare the saved datastructure and the new solution to the dataflow
1150 df_lr_verify_solution_end (void)
1152 struct df_lr_problem_data
*problem_data
;
1155 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1157 if (!problem_data
->out
)
1160 if (df_lr
->solutions_dirty
)
1161 /* Do not check if the solution is still dirty. See the comment
1162 in df_lr_finalize for details. */
1163 df_lr
->solutions_dirty
= false;
1167 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1168 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1170 /*df_dump (stderr);*/
1175 /* Cannot delete them immediately because you may want to dump them
1176 if the comparison fails. */
1179 bitmap_clear (&problem_data
->in
[bb
->index
]);
1180 bitmap_clear (&problem_data
->out
[bb
->index
]);
1183 free (problem_data
->in
);
1184 free (problem_data
->out
);
1185 problem_data
->in
= NULL
;
1186 problem_data
->out
= NULL
;
1190 /* All of the information associated with every instance of the problem. */
1192 static struct df_problem problem_LR
=
1194 DF_LR
, /* Problem id. */
1195 DF_BACKWARD
, /* Direction. */
1196 df_lr_alloc
, /* Allocate the problem specific data. */
1197 df_lr_reset
, /* Reset global information. */
1198 df_lr_free_bb_info
, /* Free basic block info. */
1199 df_lr_local_compute
, /* Local compute function. */
1200 df_lr_init
, /* Init the solution specific data. */
1201 df_worklist_dataflow
, /* Worklist solver. */
1202 df_lr_confluence_0
, /* Confluence operator 0. */
1203 df_lr_confluence_n
, /* Confluence operator n. */
1204 df_lr_transfer_function
, /* Transfer function. */
1205 df_lr_finalize
, /* Finalize function. */
1206 df_lr_free
, /* Free all of the problem information. */
1207 NULL
, /* Remove this problem from the stack of dataflow problems. */
1208 NULL
, /* Debugging. */
1209 df_lr_top_dump
, /* Debugging start block. */
1210 df_lr_bottom_dump
, /* Debugging end block. */
1211 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1212 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1213 NULL
, /* Dependent problem. */
1214 sizeof (struct df_lr_bb_info
),/* Size of entry of block_info array. */
1215 TV_DF_LR
, /* Timing variable. */
1216 false /* Reset blocks on dropping out of blocks_to_analyze. */
1220 /* Create a new DATAFLOW instance and add it to an existing instance
1221 of DF. The returned structure is what is used to get at the
1225 df_lr_add_problem (void)
1227 df_add_problem (&problem_LR
);
1228 /* These will be initialized when df_scan_blocks processes each
1230 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1234 /* Verify that all of the lr related info is consistent and
1238 df_lr_verify_transfer_functions (void)
1241 bitmap_head saved_def
;
1242 bitmap_head saved_use
;
1243 bitmap_head all_blocks
;
1248 bitmap_initialize (&saved_def
, &bitmap_default_obstack
);
1249 bitmap_initialize (&saved_use
, &bitmap_default_obstack
);
1250 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1254 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1255 bitmap_set_bit (&all_blocks
, bb
->index
);
1259 /* Make a copy of the transfer functions and then compute
1260 new ones to see if the transfer functions have
1262 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1265 bitmap_copy (&saved_def
, &bb_info
->def
);
1266 bitmap_copy (&saved_use
, &bb_info
->use
);
1267 bitmap_clear (&bb_info
->def
);
1268 bitmap_clear (&bb_info
->use
);
1270 df_lr_bb_local_compute (bb
->index
);
1271 gcc_assert (bitmap_equal_p (&saved_def
, &bb_info
->def
));
1272 gcc_assert (bitmap_equal_p (&saved_use
, &bb_info
->use
));
1277 /* If we do not have basic block info, the block must be in
1278 the list of dirty blocks or else some one has added a
1279 block behind our backs. */
1280 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1283 /* Make sure no one created a block without following
1285 gcc_assert (df_scan_get_bb_info (bb
->index
));
1288 /* Make sure there are no dirty bits in blocks that have been deleted. */
1289 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1292 bitmap_clear (&saved_def
);
1293 bitmap_clear (&saved_use
);
1294 bitmap_clear (&all_blocks
);
1299 /*----------------------------------------------------------------------------
1300 LIVE AND MUST-INITIALIZED REGISTERS.
1302 This problem first computes the IN and OUT bitvectors for the
1303 must-initialized registers problems, which is a forward problem.
1304 It gives the set of registers for which we MUST have an available
1305 definition on any path from the entry block to the entry/exit of
1306 a basic block. Sets generate a definition, while clobbers kill
1309 In and out bitvectors are built for each basic block and are indexed by
1310 regnum (see df.h for details). In and out bitvectors in struct
1311 df_live_bb_info actually refers to the must-initialized problem;
1313 Then, the in and out sets for the LIVE problem itself are computed.
1314 These are the logical AND of the IN and OUT sets from the LR problem
1315 and the must-initialized problem.
1316 ----------------------------------------------------------------------------*/
1318 /* Private data used to verify the solution for this problem. */
1319 struct df_live_problem_data
1323 /* An obstack for the bitmaps we need for this problem. */
1324 bitmap_obstack live_bitmaps
;
1327 /* Scratch var used by transfer functions. This is used to implement
1328 an optimization to reduce the amount of space used to compute the
1329 combined lr and live analysis. */
1330 static bitmap_head df_live_scratch
;
1333 /* Free basic block info. */
1336 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1339 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1342 bitmap_clear (&bb_info
->gen
);
1343 bitmap_clear (&bb_info
->kill
);
1344 bitmap_clear (&bb_info
->in
);
1345 bitmap_clear (&bb_info
->out
);
1350 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1351 not touched unless the block is new. */
1354 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1356 unsigned int bb_index
;
1358 struct df_live_problem_data
*problem_data
;
1360 if (df_live
->problem_data
)
1361 problem_data
= (struct df_live_problem_data
*) df_live
->problem_data
;
1364 problem_data
= XNEW (struct df_live_problem_data
);
1365 df_live
->problem_data
= problem_data
;
1367 problem_data
->out
= NULL
;
1368 problem_data
->in
= NULL
;
1369 bitmap_obstack_initialize (&problem_data
->live_bitmaps
);
1370 bitmap_initialize (&df_live_scratch
, &problem_data
->live_bitmaps
);
1373 df_grow_bb_info (df_live
);
1375 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1377 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1379 /* When bitmaps are already initialized, just clear them. */
1380 if (bb_info
->kill
.obstack
)
1382 bitmap_clear (&bb_info
->kill
);
1383 bitmap_clear (&bb_info
->gen
);
1387 bitmap_initialize (&bb_info
->kill
, &problem_data
->live_bitmaps
);
1388 bitmap_initialize (&bb_info
->gen
, &problem_data
->live_bitmaps
);
1389 bitmap_initialize (&bb_info
->in
, &problem_data
->live_bitmaps
);
1390 bitmap_initialize (&bb_info
->out
, &problem_data
->live_bitmaps
);
1393 df_live
->optional_p
= (optimize
<= 1);
1397 /* Reset the global solution for recalculation. */
1400 df_live_reset (bitmap all_blocks
)
1402 unsigned int bb_index
;
1405 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1407 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1408 gcc_assert (bb_info
);
1409 bitmap_clear (&bb_info
->in
);
1410 bitmap_clear (&bb_info
->out
);
1415 /* Compute local uninitialized register info for basic block BB. */
1418 df_live_bb_local_compute (unsigned int bb_index
)
1420 basic_block bb
= BASIC_BLOCK (bb_index
);
1421 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1426 FOR_BB_INSNS (bb
, insn
)
1428 unsigned int uid
= INSN_UID (insn
);
1429 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1431 /* Inserting labels does not always trigger the incremental
1435 gcc_assert (!INSN_P (insn
));
1436 insn_info
= df_insn_create_insn_record (insn
);
1439 DF_INSN_INFO_LUID (insn_info
) = luid
;
1444 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
1446 df_ref def
= *def_rec
;
1447 unsigned int regno
= DF_REF_REGNO (def
);
1449 if (DF_REF_FLAGS_IS_SET (def
,
1450 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1451 /* All partial or conditional def
1452 seen are included in the gen set. */
1453 bitmap_set_bit (&bb_info
->gen
, regno
);
1454 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1455 /* Only must clobbers for the entire reg destroy the
1457 bitmap_set_bit (&bb_info
->kill
, regno
);
1458 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1459 bitmap_set_bit (&bb_info
->gen
, regno
);
1463 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1465 df_ref def
= *def_rec
;
1466 bitmap_set_bit (&bb_info
->gen
, DF_REF_REGNO (def
));
1471 /* Compute local uninitialized register info. */
1474 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1476 unsigned int bb_index
;
1479 df_grow_insn_info ();
1481 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1484 df_live_bb_local_compute (bb_index
);
1487 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1491 /* Initialize the solution vectors. */
1494 df_live_init (bitmap all_blocks
)
1496 unsigned int bb_index
;
1499 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1501 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1502 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1504 /* No register may reach a location where it is not used. Thus
1505 we trim the rr result to the places where it is used. */
1506 bitmap_and (&bb_info
->out
, &bb_info
->gen
, &bb_lr_info
->out
);
1507 bitmap_clear (&bb_info
->in
);
1511 /* Forward confluence function that ignores fake edges. */
1514 df_live_confluence_n (edge e
)
1516 bitmap op1
= &df_live_get_bb_info (e
->dest
->index
)->in
;
1517 bitmap op2
= &df_live_get_bb_info (e
->src
->index
)->out
;
1519 if (e
->flags
& EDGE_FAKE
)
1522 return bitmap_ior_into (op1
, op2
);
1526 /* Transfer function for the forwards must-initialized problem. */
1529 df_live_transfer_function (int bb_index
)
1531 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1532 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1533 bitmap in
= &bb_info
->in
;
1534 bitmap out
= &bb_info
->out
;
1535 bitmap gen
= &bb_info
->gen
;
1536 bitmap kill
= &bb_info
->kill
;
1538 /* We need to use a scratch set here so that the value returned from this
1539 function invocation properly reflects whether the sets changed in a
1540 significant way; i.e. not just because the lr set was anded in. */
1541 bitmap_and (&df_live_scratch
, gen
, &bb_lr_info
->out
);
1542 /* No register may reach a location where it is not used. Thus
1543 we trim the rr result to the places where it is used. */
1544 bitmap_and_into (in
, &bb_lr_info
->in
);
1546 return bitmap_ior_and_compl (out
, &df_live_scratch
, in
, kill
);
1550 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1553 df_live_finalize (bitmap all_blocks
)
1556 if (df_live
->solutions_dirty
)
1559 unsigned int bb_index
;
1561 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1563 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1564 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1566 /* No register may reach a location where it is not used. Thus
1567 we trim the rr result to the places where it is used. */
1568 bitmap_and_into (&bb_live_info
->in
, &bb_lr_info
->in
);
1569 bitmap_and_into (&bb_live_info
->out
, &bb_lr_info
->out
);
1572 df_live
->solutions_dirty
= false;
1577 /* Free all storage associated with the problem. */
1582 struct df_live_problem_data
*problem_data
1583 = (struct df_live_problem_data
*) df_live
->problem_data
;
1584 if (df_live
->block_info
)
1586 df_live
->block_info_size
= 0;
1587 free (df_live
->block_info
);
1588 df_live
->block_info
= NULL
;
1589 bitmap_clear (&df_live_scratch
);
1590 bitmap_obstack_release (&problem_data
->live_bitmaps
);
1591 free (problem_data
);
1592 df_live
->problem_data
= NULL
;
1594 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1599 /* Debugging info at top of bb. */
1602 df_live_top_dump (basic_block bb
, FILE *file
)
1604 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1605 struct df_live_problem_data
*problem_data
;
1610 fprintf (file
, ";; live in \t");
1611 df_print_regset (file
, &bb_info
->in
);
1612 if (df_live
->problem_data
)
1614 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1615 if (problem_data
->in
)
1617 fprintf (file
, ";; old in \t");
1618 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1621 fprintf (file
, ";; live gen \t");
1622 df_print_regset (file
, &bb_info
->gen
);
1623 fprintf (file
, ";; live kill\t");
1624 df_print_regset (file
, &bb_info
->kill
);
1628 /* Debugging info at bottom of bb. */
1631 df_live_bottom_dump (basic_block bb
, FILE *file
)
1633 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1634 struct df_live_problem_data
*problem_data
;
1639 fprintf (file
, ";; live out \t");
1640 df_print_regset (file
, &bb_info
->out
);
1641 if (df_live
->problem_data
)
1643 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1644 if (problem_data
->out
)
1646 fprintf (file
, ";; old out \t");
1647 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1653 /* Build the datastructure to verify that the solution to the dataflow
1654 equations is not dirty. */
1657 df_live_verify_solution_start (void)
1660 struct df_live_problem_data
*problem_data
;
1661 if (df_live
->solutions_dirty
)
1664 /* Set it true so that the solution is recomputed. */
1665 df_live
->solutions_dirty
= true;
1667 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1668 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block
);
1669 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block
);
1673 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->live_bitmaps
);
1674 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->live_bitmaps
);
1675 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1676 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1681 /* Compare the saved datastructure and the new solution to the dataflow
1685 df_live_verify_solution_end (void)
1687 struct df_live_problem_data
*problem_data
;
1690 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1691 if (!problem_data
->out
)
1696 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1697 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
1699 /*df_dump (stderr);*/
1704 /* Cannot delete them immediately because you may want to dump them
1705 if the comparison fails. */
1708 bitmap_clear (&problem_data
->in
[bb
->index
]);
1709 bitmap_clear (&problem_data
->out
[bb
->index
]);
1712 free (problem_data
->in
);
1713 free (problem_data
->out
);
1714 free (problem_data
);
1715 df_live
->problem_data
= NULL
;
1719 /* All of the information associated with every instance of the problem. */
1721 static struct df_problem problem_LIVE
=
1723 DF_LIVE
, /* Problem id. */
1724 DF_FORWARD
, /* Direction. */
1725 df_live_alloc
, /* Allocate the problem specific data. */
1726 df_live_reset
, /* Reset global information. */
1727 df_live_free_bb_info
, /* Free basic block info. */
1728 df_live_local_compute
, /* Local compute function. */
1729 df_live_init
, /* Init the solution specific data. */
1730 df_worklist_dataflow
, /* Worklist solver. */
1731 NULL
, /* Confluence operator 0. */
1732 df_live_confluence_n
, /* Confluence operator n. */
1733 df_live_transfer_function
, /* Transfer function. */
1734 df_live_finalize
, /* Finalize function. */
1735 df_live_free
, /* Free all of the problem information. */
1736 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1737 NULL
, /* Debugging. */
1738 df_live_top_dump
, /* Debugging start block. */
1739 df_live_bottom_dump
, /* Debugging end block. */
1740 df_live_verify_solution_start
,/* Incremental solution verify start. */
1741 df_live_verify_solution_end
, /* Incremental solution verify end. */
1742 &problem_LR
, /* Dependent problem. */
1743 sizeof (struct df_live_bb_info
),/* Size of entry of block_info array. */
1744 TV_DF_LIVE
, /* Timing variable. */
1745 false /* Reset blocks on dropping out of blocks_to_analyze. */
1749 /* Create a new DATAFLOW instance and add it to an existing instance
1750 of DF. The returned structure is what is used to get at the
1754 df_live_add_problem (void)
1756 df_add_problem (&problem_LIVE
);
1757 /* These will be initialized when df_scan_blocks processes each
1759 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1763 /* Set all of the blocks as dirty. This needs to be done if this
1764 problem is added after all of the insns have been scanned. */
1767 df_live_set_all_dirty (void)
1771 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1776 /* Verify that all of the lr related info is consistent and
1780 df_live_verify_transfer_functions (void)
1783 bitmap_head saved_gen
;
1784 bitmap_head saved_kill
;
1785 bitmap_head all_blocks
;
1790 bitmap_initialize (&saved_gen
, &bitmap_default_obstack
);
1791 bitmap_initialize (&saved_kill
, &bitmap_default_obstack
);
1792 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1794 df_grow_insn_info ();
1798 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1799 bitmap_set_bit (&all_blocks
, bb
->index
);
1803 /* Make a copy of the transfer functions and then compute
1804 new ones to see if the transfer functions have
1806 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1809 bitmap_copy (&saved_gen
, &bb_info
->gen
);
1810 bitmap_copy (&saved_kill
, &bb_info
->kill
);
1811 bitmap_clear (&bb_info
->gen
);
1812 bitmap_clear (&bb_info
->kill
);
1814 df_live_bb_local_compute (bb
->index
);
1815 gcc_assert (bitmap_equal_p (&saved_gen
, &bb_info
->gen
));
1816 gcc_assert (bitmap_equal_p (&saved_kill
, &bb_info
->kill
));
1821 /* If we do not have basic block info, the block must be in
1822 the list of dirty blocks or else some one has added a
1823 block behind our backs. */
1824 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1827 /* Make sure no one created a block without following
1829 gcc_assert (df_scan_get_bb_info (bb
->index
));
1832 /* Make sure there are no dirty bits in blocks that have been deleted. */
1833 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1835 bitmap_clear (&saved_gen
);
1836 bitmap_clear (&saved_kill
);
1837 bitmap_clear (&all_blocks
);
1840 /*----------------------------------------------------------------------------
1841 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1843 Link either the defs to the uses and / or the uses to the defs.
1845 These problems are set up like the other dataflow problems so that
1846 they nicely fit into the framework. They are much simpler and only
1847 involve a single traversal of instructions and an examination of
1848 the reaching defs information (the dependent problem).
1849 ----------------------------------------------------------------------------*/
1851 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1853 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1856 df_chain_create (df_ref src
, df_ref dst
)
1858 struct df_link
*head
= DF_REF_CHAIN (src
);
1859 struct df_link
*link
= (struct df_link
*) pool_alloc (df_chain
->block_pool
);
1861 DF_REF_CHAIN (src
) = link
;
1868 /* Delete any du or ud chains that start at REF and point to
1871 df_chain_unlink_1 (df_ref ref
, df_ref target
)
1873 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1874 struct df_link
*prev
= NULL
;
1878 if (chain
->ref
== target
)
1881 prev
->next
= chain
->next
;
1883 DF_REF_CHAIN (ref
) = chain
->next
;
1884 pool_free (df_chain
->block_pool
, chain
);
1888 chain
= chain
->next
;
1893 /* Delete a du or ud chain that leave or point to REF. */
1896 df_chain_unlink (df_ref ref
)
1898 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1901 struct df_link
*next
= chain
->next
;
1902 /* Delete the other side if it exists. */
1903 df_chain_unlink_1 (chain
->ref
, ref
);
1904 pool_free (df_chain
->block_pool
, chain
);
1907 DF_REF_CHAIN (ref
) = NULL
;
1911 /* Copy the du or ud chain starting at FROM_REF and attach it to
1915 df_chain_copy (df_ref to_ref
,
1916 struct df_link
*from_ref
)
1920 df_chain_create (to_ref
, from_ref
->ref
);
1921 from_ref
= from_ref
->next
;
1926 /* Remove this problem from the stack of dataflow problems. */
1929 df_chain_remove_problem (void)
1932 unsigned int bb_index
;
1934 /* Wholesale destruction of the old chains. */
1935 if (df_chain
->block_pool
)
1936 free_alloc_pool (df_chain
->block_pool
);
1938 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1943 basic_block bb
= BASIC_BLOCK (bb_index
);
1945 if (df_chain_problem_p (DF_DU_CHAIN
))
1946 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
1947 DF_REF_CHAIN (*def_rec
) = NULL
;
1948 if (df_chain_problem_p (DF_UD_CHAIN
))
1949 for (use_rec
= df_get_artificial_uses (bb
->index
); *use_rec
; use_rec
++)
1950 DF_REF_CHAIN (*use_rec
) = NULL
;
1952 FOR_BB_INSNS (bb
, insn
)
1954 unsigned int uid
= INSN_UID (insn
);
1958 if (df_chain_problem_p (DF_DU_CHAIN
))
1959 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1960 DF_REF_CHAIN (*def_rec
) = NULL
;
1961 if (df_chain_problem_p (DF_UD_CHAIN
))
1963 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1964 DF_REF_CHAIN (*use_rec
) = NULL
;
1965 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
1966 DF_REF_CHAIN (*use_rec
) = NULL
;
1972 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
1973 df_chain
->block_pool
= NULL
;
1977 /* Remove the chain problem completely. */
1980 df_chain_fully_remove_problem (void)
1982 df_chain_remove_problem ();
1983 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
1988 /* Create def-use or use-def chains. */
1991 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1993 df_chain_remove_problem ();
1994 df_chain
->block_pool
= create_alloc_pool ("df_chain_block pool",
1995 sizeof (struct df_link
), 50);
1996 df_chain
->optional_p
= true;
2000 /* Reset all of the chains when the set of basic blocks changes. */
2003 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2005 df_chain_remove_problem ();
2009 /* Create the chains for a list of USEs. */
2012 df_chain_create_bb_process_use (bitmap local_rd
,
2017 unsigned int def_index
;
2021 df_ref use
= *use_rec
;
2022 unsigned int uregno
= DF_REF_REGNO (use
);
2023 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2024 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2026 /* Do not want to go through this for an uninitialized var. */
2027 int count
= DF_DEFS_COUNT (uregno
);
2030 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2032 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2033 unsigned int last_index
= first_index
+ count
- 1;
2035 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2038 if (def_index
> last_index
)
2041 def
= DF_DEFS_GET (def_index
);
2042 if (df_chain_problem_p (DF_DU_CHAIN
))
2043 df_chain_create (def
, use
);
2044 if (df_chain_problem_p (DF_UD_CHAIN
))
2045 df_chain_create (use
, def
);
2056 /* Create chains from reaching defs bitmaps for basic block BB. */
2059 df_chain_create_bb (unsigned int bb_index
)
2061 basic_block bb
= BASIC_BLOCK (bb_index
);
2062 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2066 bitmap_initialize (&cpy
, &bitmap_default_obstack
);
2067 bitmap_copy (&cpy
, &bb_info
->in
);
2068 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2070 /* Since we are going forwards, process the artificial uses first
2071 then the artificial defs second. */
2074 /* Create the chains for the artificial uses from the EH_USES at the
2075 beginning of the block. */
2077 /* Artificials are only hard regs. */
2078 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2079 df_chain_create_bb_process_use (&cpy
,
2080 df_get_artificial_uses (bb
->index
),
2084 df_rd_simulate_artificial_defs_at_top (bb
, &cpy
);
2086 /* Process the regular instructions next. */
2087 FOR_BB_INSNS (bb
, insn
)
2090 unsigned int uid
= INSN_UID (insn
);
2092 /* First scan the uses and link them up with the defs that remain
2093 in the cpy vector. */
2094 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_USES (uid
), 0);
2095 if (df
->changeable_flags
& DF_EQ_NOTES
)
2096 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2098 /* Since we are going forwards, process the defs second. */
2099 df_rd_simulate_one_insn (bb
, insn
, &cpy
);
2102 /* Create the chains for the artificial uses of the hard registers
2103 at the end of the block. */
2104 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2105 df_chain_create_bb_process_use (&cpy
,
2106 df_get_artificial_uses (bb
->index
),
2109 bitmap_clear (&cpy
);
2112 /* Create def-use chains from reaching use bitmaps for basic blocks
2116 df_chain_finalize (bitmap all_blocks
)
2118 unsigned int bb_index
;
2121 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2123 df_chain_create_bb (bb_index
);
2128 /* Free all storage associated with the problem. */
2131 df_chain_free (void)
2133 free_alloc_pool (df_chain
->block_pool
);
2134 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2139 /* Debugging info. */
2142 df_chain_top_dump (basic_block bb
, FILE *file
)
2144 if (df_chain_problem_p (DF_DU_CHAIN
))
2147 df_ref
*def_rec
= df_get_artificial_defs (bb
->index
);
2151 fprintf (file
, ";; DU chains for artificial defs\n");
2154 df_ref def
= *def_rec
;
2155 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2156 df_chain_dump (DF_REF_CHAIN (def
), file
);
2157 fprintf (file
, "\n");
2162 FOR_BB_INSNS (bb
, insn
)
2166 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2167 def_rec
= DF_INSN_INFO_DEFS (insn_info
);
2170 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2171 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2175 df_ref def
= *def_rec
;
2176 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2177 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
2178 fprintf (file
, "read/write ");
2179 df_chain_dump (DF_REF_CHAIN (def
), file
);
2180 fprintf (file
, "\n");
2191 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2193 if (df_chain_problem_p (DF_UD_CHAIN
))
2196 df_ref
*use_rec
= df_get_artificial_uses (bb
->index
);
2200 fprintf (file
, ";; UD chains for artificial uses\n");
2203 df_ref use
= *use_rec
;
2204 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2205 df_chain_dump (DF_REF_CHAIN (use
), file
);
2206 fprintf (file
, "\n");
2211 FOR_BB_INSNS (bb
, insn
)
2215 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2216 df_ref
*eq_use_rec
= DF_INSN_INFO_EQ_USES (insn_info
);
2217 use_rec
= DF_INSN_INFO_USES (insn_info
);
2218 if (*use_rec
|| *eq_use_rec
)
2220 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2221 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2225 df_ref use
= *use_rec
;
2226 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2227 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
2228 fprintf (file
, "read/write ");
2229 df_chain_dump (DF_REF_CHAIN (use
), file
);
2230 fprintf (file
, "\n");
2235 df_ref use
= *eq_use_rec
;
2236 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2237 df_chain_dump (DF_REF_CHAIN (use
), file
);
2238 fprintf (file
, "\n");
2248 static struct df_problem problem_CHAIN
=
2250 DF_CHAIN
, /* Problem id. */
2251 DF_NONE
, /* Direction. */
2252 df_chain_alloc
, /* Allocate the problem specific data. */
2253 df_chain_reset
, /* Reset global information. */
2254 NULL
, /* Free basic block info. */
2255 NULL
, /* Local compute function. */
2256 NULL
, /* Init the solution specific data. */
2257 NULL
, /* Iterative solver. */
2258 NULL
, /* Confluence operator 0. */
2259 NULL
, /* Confluence operator n. */
2260 NULL
, /* Transfer function. */
2261 df_chain_finalize
, /* Finalize function. */
2262 df_chain_free
, /* Free all of the problem information. */
2263 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2264 NULL
, /* Debugging. */
2265 df_chain_top_dump
, /* Debugging start block. */
2266 df_chain_bottom_dump
, /* Debugging end block. */
2267 NULL
, /* Incremental solution verify start. */
2268 NULL
, /* Incremental solution verify end. */
2269 &problem_RD
, /* Dependent problem. */
2270 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
2271 TV_DF_CHAIN
, /* Timing variable. */
2272 false /* Reset blocks on dropping out of blocks_to_analyze. */
2276 /* Create a new DATAFLOW instance and add it to an existing instance
2277 of DF. The returned structure is what is used to get at the
2281 df_chain_add_problem (unsigned int chain_flags
)
2283 df_add_problem (&problem_CHAIN
);
2284 df_chain
->local_flags
= chain_flags
;
2285 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2288 #undef df_chain_problem_p
2291 /*----------------------------------------------------------------------------
2292 WORD LEVEL LIVE REGISTERS
2294 Find the locations in the function where any use of a pseudo can
2295 reach in the backwards direction. In and out bitvectors are built
2296 for each basic block. We only track pseudo registers that have a
2297 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2298 contain two bits corresponding to each of the subwords.
2300 ----------------------------------------------------------------------------*/
2302 /* Private data used to verify the solution for this problem. */
2303 struct df_word_lr_problem_data
2305 /* An obstack for the bitmaps we need for this problem. */
2306 bitmap_obstack word_lr_bitmaps
;
2310 /* Free basic block info. */
2313 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2316 struct df_word_lr_bb_info
*bb_info
= (struct df_word_lr_bb_info
*) vbb_info
;
2319 bitmap_clear (&bb_info
->use
);
2320 bitmap_clear (&bb_info
->def
);
2321 bitmap_clear (&bb_info
->in
);
2322 bitmap_clear (&bb_info
->out
);
2327 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2328 not touched unless the block is new. */
2331 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2333 unsigned int bb_index
;
2336 struct df_word_lr_problem_data
*problem_data
2337 = XNEW (struct df_word_lr_problem_data
);
2339 df_word_lr
->problem_data
= problem_data
;
2341 df_grow_bb_info (df_word_lr
);
2343 /* Create the mapping from regnos to slots. This does not change
2344 unless the problem is destroyed and recreated. In particular, if
2345 we end up deleting the only insn that used a subreg, we do not
2346 want to redo the mapping because this would invalidate everything
2349 bitmap_obstack_initialize (&problem_data
->word_lr_bitmaps
);
2352 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, bb
->index
);
2354 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
2355 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, EXIT_BLOCK
);
2357 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2359 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2361 /* When bitmaps are already initialized, just clear them. */
2362 if (bb_info
->use
.obstack
)
2364 bitmap_clear (&bb_info
->def
);
2365 bitmap_clear (&bb_info
->use
);
2369 bitmap_initialize (&bb_info
->use
, &problem_data
->word_lr_bitmaps
);
2370 bitmap_initialize (&bb_info
->def
, &problem_data
->word_lr_bitmaps
);
2371 bitmap_initialize (&bb_info
->in
, &problem_data
->word_lr_bitmaps
);
2372 bitmap_initialize (&bb_info
->out
, &problem_data
->word_lr_bitmaps
);
2376 df_word_lr
->optional_p
= true;
2380 /* Reset the global solution for recalculation. */
2383 df_word_lr_reset (bitmap all_blocks
)
2385 unsigned int bb_index
;
2388 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2390 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2391 gcc_assert (bb_info
);
2392 bitmap_clear (&bb_info
->in
);
2393 bitmap_clear (&bb_info
->out
);
2397 /* Examine REF, and if it is for a reg we're interested in, set or
2398 clear the bits corresponding to its subwords from the bitmap
2399 according to IS_SET. LIVE is the bitmap we should update. We do
2400 not track hard regs or pseudos of any size other than 2 *
2402 We return true if we changed the bitmap, or if we encountered a register
2403 we're not tracking. */
2406 df_word_lr_mark_ref (df_ref ref
, bool is_set
, regset live
)
2408 rtx orig_reg
= DF_REF_REG (ref
);
2410 enum machine_mode reg_mode
;
2412 /* Left at -1 for whole accesses. */
2413 int which_subword
= -1;
2414 bool changed
= false;
2416 if (GET_CODE (reg
) == SUBREG
)
2417 reg
= SUBREG_REG (orig_reg
);
2418 regno
= REGNO (reg
);
2419 reg_mode
= GET_MODE (reg
);
2420 if (regno
< FIRST_PSEUDO_REGISTER
2421 || GET_MODE_SIZE (reg_mode
) != 2 * UNITS_PER_WORD
)
2424 if (GET_CODE (orig_reg
) == SUBREG
2425 && df_read_modify_subreg_p (orig_reg
))
2427 gcc_assert (DF_REF_FLAGS_IS_SET (ref
, DF_REF_PARTIAL
));
2428 if (subreg_lowpart_p (orig_reg
))
2435 if (which_subword
!= 1)
2436 changed
|= bitmap_set_bit (live
, regno
* 2);
2437 if (which_subword
!= 0)
2438 changed
|= bitmap_set_bit (live
, regno
* 2 + 1);
2442 if (which_subword
!= 1)
2443 changed
|= bitmap_clear_bit (live
, regno
* 2);
2444 if (which_subword
!= 0)
2445 changed
|= bitmap_clear_bit (live
, regno
* 2 + 1);
2450 /* Compute local live register info for basic block BB. */
2453 df_word_lr_bb_local_compute (unsigned int bb_index
)
2455 basic_block bb
= BASIC_BLOCK (bb_index
);
2456 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2461 /* Ensure that artificial refs don't contain references to pseudos. */
2462 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2464 df_ref def
= *def_rec
;
2465 gcc_assert (DF_REF_REGNO (def
) < FIRST_PSEUDO_REGISTER
);
2468 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2470 df_ref use
= *use_rec
;
2471 gcc_assert (DF_REF_REGNO (use
) < FIRST_PSEUDO_REGISTER
);
2474 FOR_BB_INSNS_REVERSE (bb
, insn
)
2476 unsigned int uid
= INSN_UID (insn
);
2478 if (!NONDEBUG_INSN_P (insn
))
2480 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2482 df_ref def
= *def_rec
;
2483 /* If the def is to only part of the reg, it does
2484 not kill the other defs that reach here. */
2485 if (!(DF_REF_FLAGS (def
) & (DF_REF_CONDITIONAL
)))
2487 df_word_lr_mark_ref (def
, true, &bb_info
->def
);
2488 df_word_lr_mark_ref (def
, false, &bb_info
->use
);
2491 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2493 df_ref use
= *use_rec
;
2494 df_word_lr_mark_ref (use
, true, &bb_info
->use
);
2500 /* Compute local live register info for each basic block within BLOCKS. */
2503 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2505 unsigned int bb_index
;
2508 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2510 if (bb_index
== EXIT_BLOCK
)
2514 EXECUTE_IF_SET_IN_BITMAP (df
->exit_block_uses
, FIRST_PSEUDO_REGISTER
,
2519 df_word_lr_bb_local_compute (bb_index
);
2522 bitmap_clear (df_word_lr
->out_of_date_transfer_functions
);
2526 /* Initialize the solution vectors. */
2529 df_word_lr_init (bitmap all_blocks
)
2531 unsigned int bb_index
;
2534 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2536 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2537 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
2538 bitmap_clear (&bb_info
->out
);
2543 /* Confluence function that ignores fake edges. */
2546 df_word_lr_confluence_n (edge e
)
2548 bitmap op1
= &df_word_lr_get_bb_info (e
->src
->index
)->out
;
2549 bitmap op2
= &df_word_lr_get_bb_info (e
->dest
->index
)->in
;
2551 return bitmap_ior_into (op1
, op2
);
2555 /* Transfer function. */
2558 df_word_lr_transfer_function (int bb_index
)
2560 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2561 bitmap in
= &bb_info
->in
;
2562 bitmap out
= &bb_info
->out
;
2563 bitmap use
= &bb_info
->use
;
2564 bitmap def
= &bb_info
->def
;
2566 return bitmap_ior_and_compl (in
, use
, out
, def
);
2570 /* Free all storage associated with the problem. */
2573 df_word_lr_free (void)
2575 struct df_word_lr_problem_data
*problem_data
2576 = (struct df_word_lr_problem_data
*)df_word_lr
->problem_data
;
2578 if (df_word_lr
->block_info
)
2580 df_word_lr
->block_info_size
= 0;
2581 free (df_word_lr
->block_info
);
2582 df_word_lr
->block_info
= NULL
;
2585 BITMAP_FREE (df_word_lr
->out_of_date_transfer_functions
);
2586 bitmap_obstack_release (&problem_data
->word_lr_bitmaps
);
2587 free (problem_data
);
2592 /* Debugging info at top of bb. */
2595 df_word_lr_top_dump (basic_block bb
, FILE *file
)
2597 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2601 fprintf (file
, ";; blr in \t");
2602 df_print_word_regset (file
, &bb_info
->in
);
2603 fprintf (file
, ";; blr use \t");
2604 df_print_word_regset (file
, &bb_info
->use
);
2605 fprintf (file
, ";; blr def \t");
2606 df_print_word_regset (file
, &bb_info
->def
);
2610 /* Debugging info at bottom of bb. */
2613 df_word_lr_bottom_dump (basic_block bb
, FILE *file
)
2615 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2619 fprintf (file
, ";; blr out \t");
2620 df_print_word_regset (file
, &bb_info
->out
);
2624 /* All of the information associated with every instance of the problem. */
2626 static struct df_problem problem_WORD_LR
=
2628 DF_WORD_LR
, /* Problem id. */
2629 DF_BACKWARD
, /* Direction. */
2630 df_word_lr_alloc
, /* Allocate the problem specific data. */
2631 df_word_lr_reset
, /* Reset global information. */
2632 df_word_lr_free_bb_info
, /* Free basic block info. */
2633 df_word_lr_local_compute
, /* Local compute function. */
2634 df_word_lr_init
, /* Init the solution specific data. */
2635 df_worklist_dataflow
, /* Worklist solver. */
2636 NULL
, /* Confluence operator 0. */
2637 df_word_lr_confluence_n
, /* Confluence operator n. */
2638 df_word_lr_transfer_function
, /* Transfer function. */
2639 NULL
, /* Finalize function. */
2640 df_word_lr_free
, /* Free all of the problem information. */
2641 df_word_lr_free
, /* Remove this problem from the stack of dataflow problems. */
2642 NULL
, /* Debugging. */
2643 df_word_lr_top_dump
, /* Debugging start block. */
2644 df_word_lr_bottom_dump
, /* Debugging end block. */
2645 NULL
, /* Incremental solution verify start. */
2646 NULL
, /* Incremental solution verify end. */
2647 NULL
, /* Dependent problem. */
2648 sizeof (struct df_word_lr_bb_info
),/* Size of entry of block_info array. */
2649 TV_DF_WORD_LR
, /* Timing variable. */
2650 false /* Reset blocks on dropping out of blocks_to_analyze. */
2654 /* Create a new DATAFLOW instance and add it to an existing instance
2655 of DF. The returned structure is what is used to get at the
2659 df_word_lr_add_problem (void)
2661 df_add_problem (&problem_WORD_LR
);
2662 /* These will be initialized when df_scan_blocks processes each
2664 df_word_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2668 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
2669 any bits, which is used by the caller to determine whether a set is
2670 necessary. We also return true if there are other reasons not to delete
2674 df_word_lr_simulate_defs (rtx insn
, bitmap live
)
2676 bool changed
= false;
2678 unsigned int uid
= INSN_UID (insn
);
2680 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2682 df_ref def
= *def_rec
;
2683 if (DF_REF_FLAGS (def
) & DF_REF_CONDITIONAL
)
2686 changed
|= df_word_lr_mark_ref (*def_rec
, false, live
);
2692 /* Simulate the effects of the uses of INSN on LIVE. */
2695 df_word_lr_simulate_uses (rtx insn
, bitmap live
)
2698 unsigned int uid
= INSN_UID (insn
);
2700 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2701 df_word_lr_mark_ref (*use_rec
, true, live
);
2704 /*----------------------------------------------------------------------------
2705 This problem computes REG_DEAD and REG_UNUSED notes.
2706 ----------------------------------------------------------------------------*/
2709 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2711 df_note
->optional_p
= true;
2714 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
2716 df_print_note (const char *prefix
, rtx insn
, rtx note
)
2720 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
2721 print_rtl (dump_file
, note
);
2722 fprintf (dump_file
, "\n");
2727 /* After reg-stack, the x86 floating point stack regs are difficult to
2728 analyze because of all of the pushes, pops and rotations. Thus, we
2729 just leave the notes alone. */
2733 df_ignore_stack_reg (int regno
)
2735 return regstack_completed
2736 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
2740 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
2747 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
2748 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. Remove also
2749 REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2750 as the bitmap of currently live registers. */
2753 df_kill_notes (rtx insn
, bitmap live
)
2755 rtx
*pprev
= ®_NOTES (insn
);
2760 switch (REG_NOTE_KIND (link
))
2763 /* After reg-stack, we need to ignore any unused notes
2764 for the stack registers. */
2765 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2767 pprev
= &XEXP (link
, 1);
2772 rtx next
= XEXP (link
, 1);
2773 if (REG_DEAD_DEBUGGING
)
2774 df_print_note ("deleting: ", insn
, link
);
2775 free_EXPR_LIST_node (link
);
2776 *pprev
= link
= next
;
2781 /* After reg-stack, we need to ignore any unused notes
2782 for the stack registers. */
2783 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2785 pprev
= &XEXP (link
, 1);
2790 rtx next
= XEXP (link
, 1);
2791 if (REG_DEAD_DEBUGGING
)
2792 df_print_note ("deleting: ", insn
, link
);
2793 free_EXPR_LIST_node (link
);
2794 *pprev
= link
= next
;
2801 /* Remove the notes that refer to dead registers. As we have at most
2802 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2803 so we need to purge the complete EQ_USES vector when removing
2804 the note using df_notes_rescan. */
2806 bool deleted
= false;
2808 for (use_rec
= DF_INSN_EQ_USES (insn
); *use_rec
; use_rec
++)
2810 df_ref use
= *use_rec
;
2811 if (DF_REF_REGNO (use
) > FIRST_PSEUDO_REGISTER
2813 && (DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
)
2814 && ! bitmap_bit_p (live
, DF_REF_REGNO (use
))
2815 && loc_mentioned_in_p (DF_REF_LOC (use
), XEXP (link
, 0)))
2824 if (REG_DEAD_DEBUGGING
)
2825 df_print_note ("deleting: ", insn
, link
);
2826 next
= XEXP (link
, 1);
2827 free_EXPR_LIST_node (link
);
2828 *pprev
= link
= next
;
2829 df_notes_rescan (insn
);
2833 pprev
= &XEXP (link
, 1);
2839 pprev
= &XEXP (link
, 1);
2847 /* Set a NOTE_TYPE note for REG in INSN. */
2850 df_set_note (enum reg_note note_type
, rtx insn
, rtx reg
)
2852 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2853 add_reg_note (insn
, note_type
, reg
);
2856 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2857 arguments. Return true if the register value described by MWS's
2858 mw_reg is known to be completely unused, and if mw_reg can therefore
2859 be used in a REG_UNUSED note. */
2862 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
2863 bitmap live
, bitmap artificial_uses
)
2867 /* If MWS describes a partial reference, create REG_UNUSED notes for
2868 individual hard registers. */
2869 if (mws
->flags
& DF_REF_PARTIAL
)
2872 /* Likewise if some part of the register is used. */
2873 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2874 if (bitmap_bit_p (live
, r
)
2875 || bitmap_bit_p (artificial_uses
, r
))
2878 gcc_assert (REG_P (mws
->mw_reg
));
2883 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2884 based on the bits in LIVE. Do not generate notes for registers in
2885 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
2886 not generated if the reg is both read and written by the
2891 df_set_unused_notes_for_mw (rtx insn
, struct df_mw_hardreg
*mws
,
2892 bitmap live
, bitmap do_not_gen
,
2893 bitmap artificial_uses
,
2894 struct dead_debug
*debug
)
2898 if (REG_DEAD_DEBUGGING
&& dump_file
)
2899 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
2900 mws
->start_regno
, mws
->end_regno
);
2902 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
2904 unsigned int regno
= mws
->start_regno
;
2905 df_set_note (REG_UNUSED
, insn
, mws
->mw_reg
);
2906 dead_debug_insert_temp (debug
, regno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
2908 if (REG_DEAD_DEBUGGING
)
2909 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
2911 bitmap_set_bit (do_not_gen
, regno
);
2912 /* Only do this if the value is totally dead. */
2915 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2917 if (!bitmap_bit_p (live
, r
)
2918 && !bitmap_bit_p (artificial_uses
, r
))
2920 df_set_note (REG_UNUSED
, insn
, regno_reg_rtx
[r
]);
2921 dead_debug_insert_temp (debug
, r
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
2922 if (REG_DEAD_DEBUGGING
)
2923 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
2925 bitmap_set_bit (do_not_gen
, r
);
2930 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2931 arguments. Return true if the register value described by MWS's
2932 mw_reg is known to be completely dead, and if mw_reg can therefore
2933 be used in a REG_DEAD note. */
2936 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
2937 bitmap live
, bitmap artificial_uses
,
2942 /* If MWS describes a partial reference, create REG_DEAD notes for
2943 individual hard registers. */
2944 if (mws
->flags
& DF_REF_PARTIAL
)
2947 /* Likewise if some part of the register is not dead. */
2948 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2949 if (bitmap_bit_p (live
, r
)
2950 || bitmap_bit_p (artificial_uses
, r
)
2951 || bitmap_bit_p (do_not_gen
, r
))
2954 gcc_assert (REG_P (mws
->mw_reg
));
2958 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2959 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
2960 from being set if the instruction both reads and writes the
2964 df_set_dead_notes_for_mw (rtx insn
, struct df_mw_hardreg
*mws
,
2965 bitmap live
, bitmap do_not_gen
,
2966 bitmap artificial_uses
, bool *added_notes_p
)
2969 bool is_debug
= *added_notes_p
;
2971 *added_notes_p
= false;
2973 if (REG_DEAD_DEBUGGING
&& dump_file
)
2975 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
2976 mws
->start_regno
, mws
->end_regno
);
2977 df_print_regset (dump_file
, do_not_gen
);
2978 fprintf (dump_file
, " live =");
2979 df_print_regset (dump_file
, live
);
2980 fprintf (dump_file
, " artificial uses =");
2981 df_print_regset (dump_file
, artificial_uses
);
2984 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
2988 *added_notes_p
= true;
2991 /* Add a dead note for the entire multi word register. */
2992 df_set_note (REG_DEAD
, insn
, mws
->mw_reg
);
2993 if (REG_DEAD_DEBUGGING
)
2994 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
2998 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2999 if (!bitmap_bit_p (live
, r
)
3000 && !bitmap_bit_p (artificial_uses
, r
)
3001 && !bitmap_bit_p (do_not_gen
, r
))
3005 *added_notes_p
= true;
3008 df_set_note (REG_DEAD
, insn
, regno_reg_rtx
[r
]);
3009 if (REG_DEAD_DEBUGGING
)
3010 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3017 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3018 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3021 df_create_unused_note (rtx insn
, df_ref def
,
3022 bitmap live
, bitmap artificial_uses
,
3023 struct dead_debug
*debug
)
3025 unsigned int dregno
= DF_REF_REGNO (def
);
3027 if (REG_DEAD_DEBUGGING
&& dump_file
)
3029 fprintf (dump_file
, " regular looking at def ");
3030 df_ref_debug (def
, dump_file
);
3033 if (!((DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3034 || bitmap_bit_p (live
, dregno
)
3035 || bitmap_bit_p (artificial_uses
, dregno
)
3036 || df_ignore_stack_reg (dregno
)))
3038 rtx reg
= (DF_REF_LOC (def
))
3039 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3040 df_set_note (REG_UNUSED
, insn
, reg
);
3041 dead_debug_insert_temp (debug
, dregno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
3042 if (REG_DEAD_DEBUGGING
)
3043 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3050 /* Initialize DEBUG to an empty list, and clear USED, if given. */
3052 dead_debug_init (struct dead_debug
*debug
, bitmap used
)
3056 debug
->to_rescan
= NULL
;
3058 bitmap_clear (used
);
3061 /* Reset all debug uses in HEAD, and clear DEBUG->to_rescan bits of
3062 each reset insn. DEBUG is not otherwise modified. If HEAD is
3063 DEBUG->head, DEBUG->head will be set to NULL at the end.
3064 Otherwise, entries from DEBUG->head that pertain to reset insns
3065 will be removed, and only then rescanned. */
3068 dead_debug_reset_uses (struct dead_debug
*debug
, struct dead_debug_use
*head
)
3070 bool got_head
= (debug
->head
== head
);
3072 struct dead_debug_use
**tailp
= &debug
->head
;
3073 struct dead_debug_use
*cur
;
3080 rescan
= BITMAP_ALLOC (NULL
);
3084 struct dead_debug_use
*next
= head
->next
;
3087 insn
= DF_REF_INSN (head
->use
);
3088 if (!next
|| DF_REF_INSN (next
->use
) != insn
)
3090 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3092 df_insn_rescan_debug_internal (insn
);
3094 bitmap_set_bit (rescan
, INSN_UID (insn
));
3095 if (debug
->to_rescan
)
3096 bitmap_clear_bit (debug
->to_rescan
, INSN_UID (insn
));
3108 while ((cur
= *tailp
))
3109 if (bitmap_bit_p (rescan
, INSN_UID (DF_REF_INSN (cur
->use
))))
3117 EXECUTE_IF_SET_IN_BITMAP (rescan
, 0, uid
, bi
)
3119 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
3121 df_insn_rescan_debug_internal (insn_info
->insn
);
3124 BITMAP_FREE (rescan
);
3127 /* Reset all debug insns with pending uses. Release the bitmap in it,
3128 unless it is USED. USED must be the same bitmap passed to
3131 dead_debug_finish (struct dead_debug
*debug
, bitmap used
)
3133 if (debug
->used
!= used
)
3134 BITMAP_FREE (debug
->used
);
3136 dead_debug_reset_uses (debug
, debug
->head
);
3138 if (debug
->to_rescan
)
3143 EXECUTE_IF_SET_IN_BITMAP (debug
->to_rescan
, 0, uid
, bi
)
3145 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
3147 df_insn_rescan (insn_info
->insn
);
3149 BITMAP_FREE (debug
->to_rescan
);
3153 /* Add USE to DEBUG. It must be a dead reference to UREGNO in a debug
3154 insn. Create a bitmap for DEBUG as needed. */
3156 dead_debug_add (struct dead_debug
*debug
, df_ref use
, unsigned int uregno
)
3158 struct dead_debug_use
*newddu
= XNEW (struct dead_debug_use
);
3161 newddu
->next
= debug
->head
;
3162 debug
->head
= newddu
;
3165 debug
->used
= BITMAP_ALLOC (NULL
);
3167 /* ??? If we dealt with split multi-registers below, we should set
3168 all registers for the used mode in case of hardware
3170 bitmap_set_bit (debug
->used
, uregno
);
3173 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3174 before or after INSN (depending on WHERE), that binds a debug temp
3175 to the widest-mode use of UREGNO, if WHERE is *_WITH_REG, or the
3176 value stored in UREGNO by INSN otherwise, and replace all uses of
3177 UREGNO in DEBUG with uses of the debug temp. INSN must be where
3178 UREGNO dies, if WHERE is *_BEFORE_*, or where it is set otherwise.
3179 Return the number of debug insns emitted. */
3181 dead_debug_insert_temp (struct dead_debug
*debug
, unsigned int uregno
,
3182 rtx insn
, enum debug_temp_where where
)
3184 struct dead_debug_use
**tailp
= &debug
->head
;
3185 struct dead_debug_use
*cur
;
3186 struct dead_debug_use
*uses
= NULL
;
3187 struct dead_debug_use
**usesp
= &uses
;
3193 if (!debug
->used
|| !bitmap_clear_bit (debug
->used
, uregno
))
3196 /* Move all uses of uregno from debug->head to uses, setting mode to
3197 the widest referenced mode. */
3198 while ((cur
= *tailp
))
3200 if (DF_REF_REGNO (cur
->use
) == uregno
)
3207 || (GET_MODE_BITSIZE (GET_MODE (reg
))
3208 < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur
->use
)))))
3209 reg
= *DF_REF_REAL_LOC (cur
->use
);
3212 tailp
= &(*tailp
)->next
;
3215 /* We may have dangling bits in debug->used for registers that were part
3216 of a multi-register use, one component of which has been reset. */
3219 gcc_checking_assert (!uses
);
3223 gcc_checking_assert (uses
);
3226 /* Recover the expression INSN stores in REG. */
3227 if (where
== DEBUG_TEMP_BEFORE_WITH_VALUE
)
3229 rtx set
= single_set (insn
);
3234 dest
= SET_DEST (set
);
3235 src
= SET_SRC (set
);
3236 /* Lose if the REG-setting insn is a CALL. */
3237 if (GET_CODE (src
) == CALL
)
3249 /* ??? Should we try to extract it from a PARALLEL? */
3252 /* Cool, it's the same REG, we can use SRC. */
3253 else if (dest
== reg
)
3254 breg
= copy_rtx (src
);
3255 else if (REG_P (dest
))
3257 /* Hmm... Something's fishy, we should be setting REG here. */
3258 if (REGNO (dest
) != REGNO (reg
))
3260 /* If we're not overwriting all the hardware registers that
3261 setting REG in its mode would, we won't know what to bind
3262 the debug temp to. ??? We could bind the debug_expr to a
3263 CONCAT or PARALLEL with the split multi-registers, and
3264 replace them as we found the corresponding sets. */
3265 else if (REGNO (reg
) < FIRST_PSEUDO_REGISTER
3266 && (hard_regno_nregs
[REGNO (reg
)][GET_MODE (reg
)]
3267 != hard_regno_nregs
[REGNO (reg
)][GET_MODE (dest
)]))
3269 /* Ok, it's the same (hardware) REG, but with a different
3270 mode, so SUBREG it. */
3272 breg
= lowpart_subreg (GET_MODE (reg
), copy_rtx (src
),
3275 else if (GET_CODE (dest
) == SUBREG
)
3277 /* We should be setting REG here. Lose. */
3278 if (REGNO (SUBREG_REG (dest
)) != REGNO (reg
))
3280 /* Lose if we're setting something other than the lowpart of
3282 else if (!subreg_lowpart_p (dest
))
3284 /* If we're not overwriting all the hardware registers that
3285 setting REG in its mode would, we won't know what to bind
3286 the debug temp to. */
3287 else if (REGNO (reg
) < FIRST_PSEUDO_REGISTER
3288 && (hard_regno_nregs
[REGNO (reg
)][GET_MODE (reg
)]
3289 != hard_regno_nregs
[REGNO (reg
)][GET_MODE (dest
)]))
3291 /* Yay, we can use SRC, just adjust its mode. */
3293 breg
= lowpart_subreg (GET_MODE (reg
), copy_rtx (src
),
3296 /* Oh well, we're out of luck. */
3300 /* We couldn't figure out the value stored in REG, so reset all
3301 of its pending debug uses. */
3304 dead_debug_reset_uses (debug
, uses
);
3309 /* If there's a single (debug) use of an otherwise unused REG, and
3310 the debug use is not part of a larger expression, then it
3311 probably doesn't make sense to introduce a new debug temp. */
3312 if (where
== DEBUG_TEMP_AFTER_WITH_REG
&& !uses
->next
)
3314 rtx next
= DF_REF_INSN (uses
->use
);
3316 if (DEBUG_INSN_P (next
) && reg
== INSN_VAR_LOCATION_LOC (next
))
3323 /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL). */
3324 dval
= make_debug_expr_from_rtl (reg
);
3326 /* Emit a debug bind insn before the insn in which reg dies. */
3327 bind
= gen_rtx_VAR_LOCATION (GET_MODE (reg
),
3328 DEBUG_EXPR_TREE_DECL (dval
), breg
,
3329 VAR_INIT_STATUS_INITIALIZED
);
3331 if (where
== DEBUG_TEMP_AFTER_WITH_REG
)
3332 bind
= emit_debug_insn_after (bind
, insn
);
3334 bind
= emit_debug_insn_before (bind
, insn
);
3335 df_insn_rescan (bind
);
3337 /* Adjust all uses. */
3338 while ((cur
= uses
))
3340 if (GET_MODE (*DF_REF_REAL_LOC (cur
->use
)) == GET_MODE (reg
))
3341 *DF_REF_REAL_LOC (cur
->use
) = dval
;
3343 *DF_REF_REAL_LOC (cur
->use
)
3344 = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur
->use
)), dval
);
3345 /* ??? Should we simplify subreg of subreg? */
3346 if (debug
->to_rescan
== NULL
)
3347 debug
->to_rescan
= BITMAP_ALLOC (NULL
);
3348 bitmap_set_bit (debug
->to_rescan
, INSN_UID (DF_REF_INSN (cur
->use
)));
3356 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3357 info: lifetime, bb, and number of defs and uses for basic block
3358 BB. The three bitvectors are scratch regs used here. */
3361 df_note_bb_compute (unsigned int bb_index
,
3362 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3364 basic_block bb
= BASIC_BLOCK (bb_index
);
3368 struct dead_debug debug
;
3370 dead_debug_init (&debug
, NULL
);
3372 bitmap_copy (live
, df_get_live_out (bb
));
3373 bitmap_clear (artificial_uses
);
3375 if (REG_DEAD_DEBUGGING
&& dump_file
)
3377 fprintf (dump_file
, "live at bottom ");
3378 df_print_regset (dump_file
, live
);
3381 /* Process the artificial defs and uses at the bottom of the block
3382 to begin processing. */
3383 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3385 df_ref def
= *def_rec
;
3387 if (REG_DEAD_DEBUGGING
&& dump_file
)
3388 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3390 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3391 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3394 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3396 df_ref use
= *use_rec
;
3397 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3399 unsigned int regno
= DF_REF_REGNO (use
);
3400 bitmap_set_bit (live
, regno
);
3402 /* Notes are not generated for any of the artificial registers
3403 at the bottom of the block. */
3404 bitmap_set_bit (artificial_uses
, regno
);
3408 if (REG_DEAD_DEBUGGING
&& dump_file
)
3410 fprintf (dump_file
, "live before artificials out ");
3411 df_print_regset (dump_file
, live
);
3414 FOR_BB_INSNS_REVERSE (bb
, insn
)
3416 unsigned int uid
= INSN_UID (insn
);
3417 struct df_mw_hardreg
**mws_rec
;
3423 debug_insn
= DEBUG_INSN_P (insn
);
3425 bitmap_clear (do_not_gen
);
3426 df_kill_notes (insn
, live
);
3428 /* Process the defs. */
3431 if (REG_DEAD_DEBUGGING
&& dump_file
)
3433 fprintf (dump_file
, "processing call %d\n live =", INSN_UID (insn
));
3434 df_print_regset (dump_file
, live
);
3437 /* We only care about real sets for calls. Clobbers cannot
3438 be depended on to really die. */
3439 mws_rec
= DF_INSN_UID_MWS (uid
);
3442 struct df_mw_hardreg
*mws
= *mws_rec
;
3443 if ((DF_MWS_REG_DEF_P (mws
))
3444 && !df_ignore_stack_reg (mws
->start_regno
))
3445 df_set_unused_notes_for_mw (insn
,
3446 mws
, live
, do_not_gen
,
3447 artificial_uses
, &debug
);
3451 /* All of the defs except the return value are some sort of
3452 clobber. This code is for the return. */
3453 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3455 df_ref def
= *def_rec
;
3456 unsigned int dregno
= DF_REF_REGNO (def
);
3457 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3459 df_create_unused_note (insn
,
3460 def
, live
, artificial_uses
, &debug
);
3461 bitmap_set_bit (do_not_gen
, dregno
);
3464 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3465 bitmap_clear_bit (live
, dregno
);
3471 mws_rec
= DF_INSN_UID_MWS (uid
);
3474 struct df_mw_hardreg
*mws
= *mws_rec
;
3475 if (DF_MWS_REG_DEF_P (mws
))
3476 df_set_unused_notes_for_mw (insn
,
3477 mws
, live
, do_not_gen
,
3478 artificial_uses
, &debug
);
3482 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3484 df_ref def
= *def_rec
;
3485 unsigned int dregno
= DF_REF_REGNO (def
);
3486 df_create_unused_note (insn
,
3487 def
, live
, artificial_uses
, &debug
);
3489 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3490 bitmap_set_bit (do_not_gen
, dregno
);
3492 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3493 bitmap_clear_bit (live
, dregno
);
3497 /* Process the uses. */
3498 mws_rec
= DF_INSN_UID_MWS (uid
);
3501 struct df_mw_hardreg
*mws
= *mws_rec
;
3502 if (DF_MWS_REG_USE_P (mws
)
3503 && !df_ignore_stack_reg (mws
->start_regno
))
3505 bool really_add_notes
= debug_insn
!= 0;
3507 df_set_dead_notes_for_mw (insn
,
3508 mws
, live
, do_not_gen
,
3512 if (really_add_notes
)
3518 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3520 df_ref use
= *use_rec
;
3521 unsigned int uregno
= DF_REF_REGNO (use
);
3523 if (REG_DEAD_DEBUGGING
&& dump_file
&& !debug_insn
)
3525 fprintf (dump_file
, " regular looking at use ");
3526 df_ref_debug (use
, dump_file
);
3529 if (!bitmap_bit_p (live
, uregno
))
3535 /* We won't add REG_UNUSED or REG_DEAD notes for
3536 these, so we don't have to mess with them in
3537 debug insns either. */
3538 if (!bitmap_bit_p (artificial_uses
, uregno
)
3539 && !df_ignore_stack_reg (uregno
))
3540 dead_debug_add (&debug
, use
, uregno
);
3546 dead_debug_insert_temp (&debug
, uregno
, insn
,
3547 DEBUG_TEMP_BEFORE_WITH_REG
);
3549 if ( (!(DF_REF_FLAGS (use
)
3550 & (DF_REF_MW_HARDREG
| DF_REF_READ_WRITE
)))
3551 && (!bitmap_bit_p (do_not_gen
, uregno
))
3552 && (!bitmap_bit_p (artificial_uses
, uregno
))
3553 && (!df_ignore_stack_reg (uregno
)))
3555 rtx reg
= (DF_REF_LOC (use
))
3556 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3557 df_set_note (REG_DEAD
, insn
, reg
);
3559 if (REG_DEAD_DEBUGGING
)
3560 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3562 /* This register is now live. */
3563 bitmap_set_bit (live
, uregno
);
3567 if (debug_insn
== -1)
3569 /* ??? We could probably do better here, replacing dead
3570 registers with their definitions. */
3571 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3572 df_insn_rescan_debug_internal (insn
);
3576 dead_debug_finish (&debug
, NULL
);
3580 /* Compute register info: lifetime, bb, and number of defs and uses. */
3582 df_note_compute (bitmap all_blocks
)
3584 unsigned int bb_index
;
3586 bitmap_head live
, do_not_gen
, artificial_uses
;
3588 bitmap_initialize (&live
, &df_bitmap_obstack
);
3589 bitmap_initialize (&do_not_gen
, &df_bitmap_obstack
);
3590 bitmap_initialize (&artificial_uses
, &df_bitmap_obstack
);
3592 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3594 df_note_bb_compute (bb_index
, &live
, &do_not_gen
, &artificial_uses
);
3597 bitmap_clear (&live
);
3598 bitmap_clear (&do_not_gen
);
3599 bitmap_clear (&artificial_uses
);
3603 /* Free all storage associated with the problem. */
3612 /* All of the information associated every instance of the problem. */
3614 static struct df_problem problem_NOTE
=
3616 DF_NOTE
, /* Problem id. */
3617 DF_NONE
, /* Direction. */
3618 df_note_alloc
, /* Allocate the problem specific data. */
3619 NULL
, /* Reset global information. */
3620 NULL
, /* Free basic block info. */
3621 df_note_compute
, /* Local compute function. */
3622 NULL
, /* Init the solution specific data. */
3623 NULL
, /* Iterative solver. */
3624 NULL
, /* Confluence operator 0. */
3625 NULL
, /* Confluence operator n. */
3626 NULL
, /* Transfer function. */
3627 NULL
, /* Finalize function. */
3628 df_note_free
, /* Free all of the problem information. */
3629 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3630 NULL
, /* Debugging. */
3631 NULL
, /* Debugging start block. */
3632 NULL
, /* Debugging end block. */
3633 NULL
, /* Incremental solution verify start. */
3634 NULL
, /* Incremental solution verify end. */
3635 &problem_LR
, /* Dependent problem. */
3636 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
3637 TV_DF_NOTE
, /* Timing variable. */
3638 false /* Reset blocks on dropping out of blocks_to_analyze. */
3642 /* Create a new DATAFLOW instance and add it to an existing instance
3643 of DF. The returned structure is what is used to get at the
3647 df_note_add_problem (void)
3649 df_add_problem (&problem_NOTE
);
3655 /*----------------------------------------------------------------------------
3656 Functions for simulating the effects of single insns.
3658 You can either simulate in the forwards direction, starting from
3659 the top of a block or the backwards direction from the end of the
3660 block. If you go backwards, defs are examined first to clear bits,
3661 then uses are examined to set bits. If you go forwards, defs are
3662 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3663 are examined to clear bits. In either case, the result of examining
3664 a def can be undone (respectively by a use or a REG_UNUSED note).
3666 If you start at the top of the block, use one of DF_LIVE_IN or
3667 DF_LR_IN. If you start at the bottom of the block use one of
3668 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3669 THEY WILL BE DESTROYED.
3670 ----------------------------------------------------------------------------*/
3673 /* Find the set of DEFs for INSN. */
3676 df_simulate_find_defs (rtx insn
, bitmap defs
)
3679 unsigned int uid
= INSN_UID (insn
);
3681 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3683 df_ref def
= *def_rec
;
3684 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3688 /* Find the set of uses for INSN. This includes partial defs. */
3691 df_simulate_find_uses (rtx insn
, bitmap uses
)
3694 unsigned int uid
= INSN_UID (insn
);
3696 for (rec
= DF_INSN_UID_DEFS (uid
); *rec
; rec
++)
3699 if (DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3700 bitmap_set_bit (uses
, DF_REF_REGNO (def
));
3702 for (rec
= DF_INSN_UID_USES (uid
); *rec
; rec
++)
3705 bitmap_set_bit (uses
, DF_REF_REGNO (use
));
3709 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3712 df_simulate_find_noclobber_defs (rtx insn
, bitmap defs
)
3715 unsigned int uid
= INSN_UID (insn
);
3717 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3719 df_ref def
= *def_rec
;
3720 if (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
3721 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3726 /* Simulate the effects of the defs of INSN on LIVE. */
3729 df_simulate_defs (rtx insn
, bitmap live
)
3732 unsigned int uid
= INSN_UID (insn
);
3734 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3736 df_ref def
= *def_rec
;
3737 unsigned int dregno
= DF_REF_REGNO (def
);
3739 /* If the def is to only part of the reg, it does
3740 not kill the other defs that reach here. */
3741 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3742 bitmap_clear_bit (live
, dregno
);
3747 /* Simulate the effects of the uses of INSN on LIVE. */
3750 df_simulate_uses (rtx insn
, bitmap live
)
3753 unsigned int uid
= INSN_UID (insn
);
3755 if (DEBUG_INSN_P (insn
))
3758 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3760 df_ref use
= *use_rec
;
3761 /* Add use to set of uses in this BB. */
3762 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3767 /* Add back the always live regs in BB to LIVE. */
3770 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3772 /* These regs are considered always live so if they end up dying
3773 because of some def, we need to bring the back again. */
3774 if (bb_has_eh_pred (bb
))
3775 bitmap_ior_into (live
, &df
->eh_block_artificial_uses
);
3777 bitmap_ior_into (live
, &df
->regular_block_artificial_uses
);
3781 /*----------------------------------------------------------------------------
3782 The following three functions are used only for BACKWARDS scanning:
3783 i.e. they process the defs before the uses.
3785 df_simulate_initialize_backwards should be called first with a
3786 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3787 df_simulate_one_insn_backwards should be called for each insn in
3788 the block, starting with the last one. Finally,
3789 df_simulate_finalize_backwards can be called to get a new value
3790 of the sets at the top of the block (this is rarely used).
3791 ----------------------------------------------------------------------------*/
3793 /* Apply the artificial uses and defs at the end of BB in a backwards
3797 df_simulate_initialize_backwards (basic_block bb
, bitmap live
)
3801 int bb_index
= bb
->index
;
3803 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3805 df_ref def
= *def_rec
;
3806 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3807 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3810 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3812 df_ref use
= *use_rec
;
3813 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3814 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3819 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3822 df_simulate_one_insn_backwards (basic_block bb
, rtx insn
, bitmap live
)
3824 if (!NONDEBUG_INSN_P (insn
))
3827 df_simulate_defs (insn
, live
);
3828 df_simulate_uses (insn
, live
);
3829 df_simulate_fixup_sets (bb
, live
);
3833 /* Apply the artificial uses and defs at the top of BB in a backwards
3837 df_simulate_finalize_backwards (basic_block bb
, bitmap live
)
3843 int bb_index
= bb
->index
;
3845 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3847 df_ref def
= *def_rec
;
3848 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3849 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3853 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3855 df_ref use
= *use_rec
;
3856 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3857 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3861 /*----------------------------------------------------------------------------
3862 The following three functions are used only for FORWARDS scanning:
3863 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3864 Thus it is important to add the DF_NOTES problem to the stack of
3865 problems computed before using these functions.
3867 df_simulate_initialize_forwards should be called first with a
3868 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3869 df_simulate_one_insn_forwards should be called for each insn in
3870 the block, starting with the first one.
3871 ----------------------------------------------------------------------------*/
3873 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3874 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3878 df_simulate_initialize_forwards (basic_block bb
, bitmap live
)
3881 int bb_index
= bb
->index
;
3883 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3885 df_ref def
= *def_rec
;
3886 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3887 bitmap_set_bit (live
, DF_REF_REGNO (def
));
3891 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3894 df_simulate_one_insn_forwards (basic_block bb
, rtx insn
, bitmap live
)
3897 if (! INSN_P (insn
))
3900 /* Make sure that DF_NOTE really is an active df problem. */
3901 gcc_assert (df_note
);
3903 /* Note that this is the opposite as how the problem is defined, because
3904 in the LR problem defs _kill_ liveness. However, they do so backwards,
3905 while here the scan is performed forwards! So, first assume that the
3906 def is live, and if this is not true REG_UNUSED notes will rectify the
3908 df_simulate_find_noclobber_defs (insn
, live
);
3910 /* Clear all of the registers that go dead. */
3911 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3913 switch (REG_NOTE_KIND (link
))
3918 rtx reg
= XEXP (link
, 0);
3919 int regno
= REGNO (reg
);
3920 if (HARD_REGISTER_NUM_P (regno
))
3921 bitmap_clear_range (live
, regno
,
3922 hard_regno_nregs
[regno
][GET_MODE (reg
)]);
3924 bitmap_clear_bit (live
, regno
);
3931 df_simulate_fixup_sets (bb
, live
);
3934 /* Used by the next two functions to encode information about the
3935 memory references we found. */
3936 #define MEMREF_NORMAL 1
3937 #define MEMREF_VOLATILE 2
3939 /* A subroutine of can_move_insns_across_p called through for_each_rtx.
3940 Return either MEMREF_NORMAL or MEMREF_VOLATILE if a memory is found. */
3943 find_memory (rtx
*px
, void *data ATTRIBUTE_UNUSED
)
3947 if (GET_CODE (x
) == ASM_OPERANDS
&& MEM_VOLATILE_P (x
))
3948 return MEMREF_VOLATILE
;
3952 if (MEM_VOLATILE_P (x
))
3953 return MEMREF_VOLATILE
;
3954 if (MEM_READONLY_P (x
))
3957 return MEMREF_NORMAL
;
3960 /* A subroutine of can_move_insns_across_p called through note_stores.
3961 DATA points to an integer in which we set either the bit for
3962 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3966 find_memory_stores (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
,
3967 void *data ATTRIBUTE_UNUSED
)
3969 int *pflags
= (int *)data
;
3970 if (GET_CODE (x
) == SUBREG
)
3972 /* Treat stores to SP as stores to memory, this will prevent problems
3973 when there are references to the stack frame. */
3974 if (x
== stack_pointer_rtx
)
3975 *pflags
|= MEMREF_VOLATILE
;
3978 *pflags
|= MEM_VOLATILE_P (x
) ? MEMREF_VOLATILE
: MEMREF_NORMAL
;
3981 /* Scan BB backwards, using df_simulate functions to keep track of
3982 lifetimes, up to insn POINT. The result is stored in LIVE. */
3985 simulate_backwards_to_point (basic_block bb
, regset live
, rtx point
)
3988 bitmap_copy (live
, df_get_live_out (bb
));
3989 df_simulate_initialize_backwards (bb
, live
);
3991 /* Scan and update life information until we reach the point we're
3993 for (insn
= BB_END (bb
); insn
!= point
; insn
= PREV_INSN (insn
))
3994 df_simulate_one_insn_backwards (bb
, insn
, live
);
3997 /* Return true if it is safe to move a group of insns, described by
3998 the range FROM to TO, backwards across another group of insns,
3999 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4000 are no insns between ACROSS_TO and FROM, but they may be in
4001 different basic blocks; MERGE_BB is the block from which the
4002 insns will be moved. The caller must pass in a regset MERGE_LIVE
4003 which specifies the registers live after TO.
4005 This function may be called in one of two cases: either we try to
4006 move identical instructions from all successor blocks into their
4007 predecessor, or we try to move from only one successor block. If
4008 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4009 the second case. It should contain a set of registers live at the
4010 end of ACROSS_TO which must not be clobbered by moving the insns.
4011 In that case, we're also more careful about moving memory references
4014 We return false if it is not safe to move the entire group, but it
4015 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4016 is set to point at the last moveable insn in such a case. */
4019 can_move_insns_across (rtx from
, rtx to
, rtx across_from
, rtx across_to
,
4020 basic_block merge_bb
, regset merge_live
,
4021 regset other_branch_live
, rtx
*pmove_upto
)
4023 rtx insn
, next
, max_to
;
4024 bitmap merge_set
, merge_use
, local_merge_live
;
4025 bitmap test_set
, test_use
;
4026 unsigned i
, fail
= 0;
4028 int memrefs_in_across
= 0;
4029 int mem_sets_in_across
= 0;
4030 bool trapping_insns_in_across
= false;
4032 if (pmove_upto
!= NULL
)
4033 *pmove_upto
= NULL_RTX
;
4035 /* Find real bounds, ignoring debug insns. */
4036 while (!NONDEBUG_INSN_P (from
) && from
!= to
)
4037 from
= NEXT_INSN (from
);
4038 while (!NONDEBUG_INSN_P (to
) && from
!= to
)
4039 to
= PREV_INSN (to
);
4041 for (insn
= across_to
; ; insn
= next
)
4045 if (RTL_CONST_OR_PURE_CALL_P (insn
))
4046 /* Pure functions can read from memory. Const functions can
4047 read from arguments that the ABI has forced onto the stack.
4048 Neither sort of read can be volatile. */
4049 memrefs_in_across
|= MEMREF_NORMAL
;
4052 memrefs_in_across
|= MEMREF_VOLATILE
;
4053 mem_sets_in_across
|= MEMREF_VOLATILE
;
4056 if (NONDEBUG_INSN_P (insn
))
4058 memrefs_in_across
|= for_each_rtx (&PATTERN (insn
), find_memory
,
4060 note_stores (PATTERN (insn
), find_memory_stores
,
4061 &mem_sets_in_across
);
4062 /* This is used just to find sets of the stack pointer. */
4063 memrefs_in_across
|= mem_sets_in_across
;
4064 trapping_insns_in_across
|= may_trap_p (PATTERN (insn
));
4066 next
= PREV_INSN (insn
);
4067 if (insn
== across_from
)
4072 MERGE_SET = set of registers set in MERGE_BB
4073 MERGE_USE = set of registers used in MERGE_BB and live at its top
4074 MERGE_LIVE = set of registers live at the point inside the MERGE
4075 range that we've reached during scanning
4076 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4077 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4078 and live before ACROSS_FROM. */
4080 merge_set
= BITMAP_ALLOC (®_obstack
);
4081 merge_use
= BITMAP_ALLOC (®_obstack
);
4082 local_merge_live
= BITMAP_ALLOC (®_obstack
);
4083 test_set
= BITMAP_ALLOC (®_obstack
);
4084 test_use
= BITMAP_ALLOC (®_obstack
);
4086 /* Compute the set of registers set and used in the ACROSS range. */
4087 if (other_branch_live
!= NULL
)
4088 bitmap_copy (test_use
, other_branch_live
);
4089 df_simulate_initialize_backwards (merge_bb
, test_use
);
4090 for (insn
= across_to
; ; insn
= next
)
4092 if (NONDEBUG_INSN_P (insn
))
4094 df_simulate_find_defs (insn
, test_set
);
4095 df_simulate_defs (insn
, test_use
);
4096 df_simulate_uses (insn
, test_use
);
4098 next
= PREV_INSN (insn
);
4099 if (insn
== across_from
)
4103 /* Compute an upper bound for the amount of insns moved, by finding
4104 the first insn in MERGE that sets a register in TEST_USE, or uses
4105 a register in TEST_SET. We also check for calls, trapping operations,
4106 and memory references. */
4108 for (insn
= from
; ; insn
= next
)
4112 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
4114 if (NONDEBUG_INSN_P (insn
))
4116 if (may_trap_or_fault_p (PATTERN (insn
))
4117 && (trapping_insns_in_across
|| other_branch_live
!= NULL
))
4120 /* We cannot move memory stores past each other, or move memory
4121 reads past stores, at least not without tracking them and
4122 calling true_dependence on every pair.
4124 If there is no other branch and no memory references or
4125 sets in the ACROSS range, we can move memory references
4126 freely, even volatile ones.
4128 Otherwise, the rules are as follows: volatile memory
4129 references and stores can't be moved at all, and any type
4130 of memory reference can't be moved if there are volatile
4131 accesses or stores in the ACROSS range. That leaves
4132 normal reads, which can be moved, as the trapping case is
4133 dealt with elsewhere. */
4134 if (other_branch_live
!= NULL
|| memrefs_in_across
!= 0)
4136 int mem_ref_flags
= 0;
4137 int mem_set_flags
= 0;
4138 note_stores (PATTERN (insn
), find_memory_stores
, &mem_set_flags
);
4139 mem_ref_flags
= for_each_rtx (&PATTERN (insn
), find_memory
,
4141 /* Catch sets of the stack pointer. */
4142 mem_ref_flags
|= mem_set_flags
;
4144 if ((mem_ref_flags
| mem_set_flags
) & MEMREF_VOLATILE
)
4146 if ((memrefs_in_across
& MEMREF_VOLATILE
) && mem_ref_flags
!= 0)
4148 if (mem_set_flags
!= 0
4149 || (mem_sets_in_across
!= 0 && mem_ref_flags
!= 0))
4152 df_simulate_find_uses (insn
, merge_use
);
4153 /* We're only interested in uses which use a value live at
4154 the top, not one previously set in this block. */
4155 bitmap_and_compl_into (merge_use
, merge_set
);
4156 df_simulate_find_defs (insn
, merge_set
);
4157 if (bitmap_intersect_p (merge_set
, test_use
)
4158 || bitmap_intersect_p (merge_use
, test_set
))
4161 if (!sets_cc0_p (insn
))
4165 next
= NEXT_INSN (insn
);
4172 if (max_to
== NULL_RTX
|| (fail
&& pmove_upto
== NULL
))
4175 /* Now, lower this upper bound by also taking into account that
4176 a range of insns moved across ACROSS must not leave a register
4177 live at the end that will be clobbered in ACROSS. We need to
4178 find a point where TEST_SET & LIVE == 0.
4180 Insns in the MERGE range that set registers which are also set
4181 in the ACROSS range may still be moved as long as we also move
4182 later insns which use the results of the set, and make the
4183 register dead again. This is verified by the condition stated
4184 above. We only need to test it for registers that are set in
4187 MERGE_LIVE is provided by the caller and holds live registers after
4189 bitmap_copy (local_merge_live
, merge_live
);
4190 for (insn
= to
; insn
!= max_to
; insn
= PREV_INSN (insn
))
4191 df_simulate_one_insn_backwards (merge_bb
, insn
, local_merge_live
);
4193 /* We're not interested in registers that aren't set in the moved
4195 bitmap_and_into (local_merge_live
, merge_set
);
4198 if (NONDEBUG_INSN_P (insn
))
4200 if (!bitmap_intersect_p (test_set
, local_merge_live
)
4202 && !sets_cc0_p (insn
)
4210 df_simulate_one_insn_backwards (merge_bb
, insn
,
4218 insn
= PREV_INSN (insn
);
4225 *pmove_upto
= max_to
;
4227 /* For small register class machines, don't lengthen lifetimes of
4228 hard registers before reload. */
4229 if (! reload_completed
4230 && targetm
.small_register_classes_for_mode_p (VOIDmode
))
4232 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
4234 if (i
< FIRST_PSEUDO_REGISTER
4236 && ! global_regs
[i
])
4242 BITMAP_FREE (merge_set
);
4243 BITMAP_FREE (merge_use
);
4244 BITMAP_FREE (local_merge_live
);
4245 BITMAP_FREE (test_set
);
4246 BITMAP_FREE (test_use
);
4252 /*----------------------------------------------------------------------------
4253 MULTIPLE DEFINITIONS
4255 Find the locations in the function reached by multiple definition sites
4256 for a live pseudo. In and out bitvectors are built for each basic
4257 block. They are restricted for efficiency to live registers.
4259 The gen and kill sets for the problem are obvious. Together they
4260 include all defined registers in a basic block; the gen set includes
4261 registers where a partial or conditional or may-clobber definition is
4262 last in the BB, while the kill set includes registers with a complete
4263 definition coming last. However, the computation of the dataflow
4264 itself is interesting.
4266 The idea behind it comes from SSA form's iterated dominance frontier
4267 criterion for inserting PHI functions. Just like in that case, we can use
4268 the dominance frontier to find places where multiple definitions meet;
4269 a register X defined in a basic block BB1 has multiple definitions in
4270 basic blocks in BB1's dominance frontier.
4272 So, the in-set of a basic block BB2 is not just the union of the
4273 out-sets of BB2's predecessors, but includes some more bits that come
4274 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4275 the previous paragraph). I called this set the init-set of BB2.
4277 (Note: I actually use the kill-set only to build the init-set.
4278 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4280 For example, if you have
4284 if <...> goto BB2 else goto BB3;
4292 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4293 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4294 not need to iterate the dominance frontier, because we do not insert
4295 anything like PHI functions there! Instead, dataflow will take care of
4296 propagating the information to BB3's successors.
4297 ---------------------------------------------------------------------------*/
4299 /* Private data used to verify the solution for this problem. */
4300 struct df_md_problem_data
4302 /* An obstack for the bitmaps we need for this problem. */
4303 bitmap_obstack md_bitmaps
;
4306 /* Scratch var used by transfer functions. This is used to do md analysis
4307 only for live registers. */
4308 static bitmap_head df_md_scratch
;
4312 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
4315 struct df_md_bb_info
*bb_info
= (struct df_md_bb_info
*) vbb_info
;
4318 bitmap_clear (&bb_info
->kill
);
4319 bitmap_clear (&bb_info
->gen
);
4320 bitmap_clear (&bb_info
->init
);
4321 bitmap_clear (&bb_info
->in
);
4322 bitmap_clear (&bb_info
->out
);
4327 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4328 not touched unless the block is new. */
4331 df_md_alloc (bitmap all_blocks
)
4333 unsigned int bb_index
;
4335 struct df_md_problem_data
*problem_data
;
4337 df_grow_bb_info (df_md
);
4338 if (df_md
->problem_data
)
4339 problem_data
= (struct df_md_problem_data
*) df_md
->problem_data
;
4342 problem_data
= XNEW (struct df_md_problem_data
);
4343 df_md
->problem_data
= problem_data
;
4344 bitmap_obstack_initialize (&problem_data
->md_bitmaps
);
4346 bitmap_initialize (&df_md_scratch
, &problem_data
->md_bitmaps
);
4348 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4350 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4351 /* When bitmaps are already initialized, just clear them. */
4352 if (bb_info
->init
.obstack
)
4354 bitmap_clear (&bb_info
->init
);
4355 bitmap_clear (&bb_info
->gen
);
4356 bitmap_clear (&bb_info
->kill
);
4357 bitmap_clear (&bb_info
->in
);
4358 bitmap_clear (&bb_info
->out
);
4362 bitmap_initialize (&bb_info
->init
, &problem_data
->md_bitmaps
);
4363 bitmap_initialize (&bb_info
->gen
, &problem_data
->md_bitmaps
);
4364 bitmap_initialize (&bb_info
->kill
, &problem_data
->md_bitmaps
);
4365 bitmap_initialize (&bb_info
->in
, &problem_data
->md_bitmaps
);
4366 bitmap_initialize (&bb_info
->out
, &problem_data
->md_bitmaps
);
4370 df_md
->optional_p
= true;
4373 /* Add the effect of the top artificial defs of BB to the multiple definitions
4377 df_md_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_md
)
4379 int bb_index
= bb
->index
;
4381 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4383 df_ref def
= *def_rec
;
4384 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4386 unsigned int dregno
= DF_REF_REGNO (def
);
4387 if (DF_REF_FLAGS (def
)
4388 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4389 bitmap_set_bit (local_md
, dregno
);
4391 bitmap_clear_bit (local_md
, dregno
);
4397 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4401 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
4404 unsigned uid
= INSN_UID (insn
);
4407 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4409 df_ref def
= *def_rec
;
4410 unsigned int dregno
= DF_REF_REGNO (def
);
4411 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4412 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4414 if (DF_REF_FLAGS (def
)
4415 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4416 bitmap_set_bit (local_md
, DF_REF_ID (def
));
4418 bitmap_clear_bit (local_md
, DF_REF_ID (def
));
4424 df_md_bb_local_compute_process_def (struct df_md_bb_info
*bb_info
,
4429 bitmap_clear (&seen_in_insn
);
4431 while ((def
= *def_rec
++) != NULL
)
4433 unsigned int dregno
= DF_REF_REGNO (def
);
4434 if (((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4435 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4436 && top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
4438 if (!bitmap_bit_p (&seen_in_insn
, dregno
))
4440 if (DF_REF_FLAGS (def
)
4441 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4443 bitmap_set_bit (&bb_info
->gen
, dregno
);
4444 bitmap_clear_bit (&bb_info
->kill
, dregno
);
4448 /* When we find a clobber and a regular def,
4449 make sure the regular def wins. */
4450 bitmap_set_bit (&seen_in_insn
, dregno
);
4451 bitmap_set_bit (&bb_info
->kill
, dregno
);
4452 bitmap_clear_bit (&bb_info
->gen
, dregno
);
4460 /* Compute local multiple def info for basic block BB. */
4463 df_md_bb_local_compute (unsigned int bb_index
)
4465 basic_block bb
= BASIC_BLOCK (bb_index
);
4466 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4469 /* Artificials are only hard regs. */
4470 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4471 df_md_bb_local_compute_process_def (bb_info
,
4472 df_get_artificial_defs (bb_index
),
4475 FOR_BB_INSNS (bb
, insn
)
4477 unsigned int uid
= INSN_UID (insn
);
4481 df_md_bb_local_compute_process_def (bb_info
, DF_INSN_UID_DEFS (uid
), 0);
4484 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4485 df_md_bb_local_compute_process_def (bb_info
,
4486 df_get_artificial_defs (bb_index
),
4490 /* Compute local reaching def info for each basic block within BLOCKS. */
4493 df_md_local_compute (bitmap all_blocks
)
4495 unsigned int bb_index
, df_bb_index
;
4496 bitmap_iterator bi1
, bi2
;
4498 bitmap_head
*frontiers
;
4500 bitmap_initialize (&seen_in_insn
, &bitmap_default_obstack
);
4502 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4504 df_md_bb_local_compute (bb_index
);
4507 bitmap_clear (&seen_in_insn
);
4509 frontiers
= XNEWVEC (bitmap_head
, last_basic_block
);
4511 bitmap_initialize (&frontiers
[bb
->index
], &bitmap_default_obstack
);
4513 compute_dominance_frontiers (frontiers
);
4515 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4516 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4518 bitmap kill
= &df_md_get_bb_info (bb_index
)->kill
;
4519 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[bb_index
], 0, df_bb_index
, bi2
)
4521 basic_block bb
= BASIC_BLOCK (df_bb_index
);
4522 if (bitmap_bit_p (all_blocks
, df_bb_index
))
4523 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index
)->init
, kill
,
4524 df_get_live_in (bb
));
4529 bitmap_clear (&frontiers
[bb
->index
]);
4534 /* Reset the global solution for recalculation. */
4537 df_md_reset (bitmap all_blocks
)
4539 unsigned int bb_index
;
4542 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4544 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4545 gcc_assert (bb_info
);
4546 bitmap_clear (&bb_info
->in
);
4547 bitmap_clear (&bb_info
->out
);
4552 df_md_transfer_function (int bb_index
)
4554 basic_block bb
= BASIC_BLOCK (bb_index
);
4555 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4556 bitmap in
= &bb_info
->in
;
4557 bitmap out
= &bb_info
->out
;
4558 bitmap gen
= &bb_info
->gen
;
4559 bitmap kill
= &bb_info
->kill
;
4561 /* We need to use a scratch set here so that the value returned from this
4562 function invocation properly reflects whether the sets changed in a
4563 significant way; i.e. not just because the live set was anded in. */
4564 bitmap_and (&df_md_scratch
, gen
, df_get_live_out (bb
));
4566 /* Multiple definitions of a register are not relevant if it is not
4567 live. Thus we trim the result to the places where it is live. */
4568 bitmap_and_into (in
, df_get_live_in (bb
));
4570 return bitmap_ior_and_compl (out
, &df_md_scratch
, in
, kill
);
4573 /* Initialize the solution bit vectors for problem. */
4576 df_md_init (bitmap all_blocks
)
4578 unsigned int bb_index
;
4581 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4583 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4585 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4586 df_md_transfer_function (bb_index
);
4591 df_md_confluence_0 (basic_block bb
)
4593 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4594 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4597 /* In of target gets or of out of source. */
4600 df_md_confluence_n (edge e
)
4602 bitmap op1
= &df_md_get_bb_info (e
->dest
->index
)->in
;
4603 bitmap op2
= &df_md_get_bb_info (e
->src
->index
)->out
;
4605 if (e
->flags
& EDGE_FAKE
)
4608 if (e
->flags
& EDGE_EH
)
4609 return bitmap_ior_and_compl_into (op1
, op2
,
4610 regs_invalidated_by_call_regset
);
4612 return bitmap_ior_into (op1
, op2
);
4615 /* Free all storage associated with the problem. */
4620 struct df_md_problem_data
*problem_data
4621 = (struct df_md_problem_data
*) df_md
->problem_data
;
4623 bitmap_obstack_release (&problem_data
->md_bitmaps
);
4624 free (problem_data
);
4625 df_md
->problem_data
= NULL
;
4627 df_md
->block_info_size
= 0;
4628 free (df_md
->block_info
);
4629 df_md
->block_info
= NULL
;
4634 /* Debugging info at top of bb. */
4637 df_md_top_dump (basic_block bb
, FILE *file
)
4639 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4643 fprintf (file
, ";; md in \t");
4644 df_print_regset (file
, &bb_info
->in
);
4645 fprintf (file
, ";; md init \t");
4646 df_print_regset (file
, &bb_info
->init
);
4647 fprintf (file
, ";; md gen \t");
4648 df_print_regset (file
, &bb_info
->gen
);
4649 fprintf (file
, ";; md kill \t");
4650 df_print_regset (file
, &bb_info
->kill
);
4653 /* Debugging info at bottom of bb. */
4656 df_md_bottom_dump (basic_block bb
, FILE *file
)
4658 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4662 fprintf (file
, ";; md out \t");
4663 df_print_regset (file
, &bb_info
->out
);
4666 static struct df_problem problem_MD
=
4668 DF_MD
, /* Problem id. */
4669 DF_FORWARD
, /* Direction. */
4670 df_md_alloc
, /* Allocate the problem specific data. */
4671 df_md_reset
, /* Reset global information. */
4672 df_md_free_bb_info
, /* Free basic block info. */
4673 df_md_local_compute
, /* Local compute function. */
4674 df_md_init
, /* Init the solution specific data. */
4675 df_worklist_dataflow
, /* Worklist solver. */
4676 df_md_confluence_0
, /* Confluence operator 0. */
4677 df_md_confluence_n
, /* Confluence operator n. */
4678 df_md_transfer_function
, /* Transfer function. */
4679 NULL
, /* Finalize function. */
4680 df_md_free
, /* Free all of the problem information. */
4681 df_md_free
, /* Remove this problem from the stack of dataflow problems. */
4682 NULL
, /* Debugging. */
4683 df_md_top_dump
, /* Debugging start block. */
4684 df_md_bottom_dump
, /* Debugging end block. */
4685 NULL
, /* Incremental solution verify start. */
4686 NULL
, /* Incremental solution verify end. */
4687 NULL
, /* Dependent problem. */
4688 sizeof (struct df_md_bb_info
),/* Size of entry of block_info array. */
4689 TV_DF_MD
, /* Timing variable. */
4690 false /* Reset blocks on dropping out of blocks_to_analyze. */
4693 /* Create a new MD instance and add it to the existing instance
4697 df_md_add_problem (void)
4699 df_add_problem (&problem_MD
);