1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2015 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
30 #include "insn-config.h"
36 #include "hard-reg-set.h"
40 #include "alloc-pool.h"
43 #include "dominance.h"
46 #include "basic-block.h"
58 /* Note that turning REG_DEAD_DEBUGGING on will cause
59 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
60 addresses in the dumps. */
61 #define REG_DEAD_DEBUGGING 0
63 #define DF_SPARSE_THRESHOLD 32
65 static bitmap_head seen_in_block
;
66 static bitmap_head seen_in_insn
;
68 /*----------------------------------------------------------------------------
70 ----------------------------------------------------------------------------*/
72 /* Generic versions to get the void* version of the block info. Only
73 used inside the problem instance vectors. */
75 /* Dump a def-use or use-def chain for REF to FILE. */
78 df_chain_dump (struct df_link
*link
, FILE *file
)
81 for (; link
; link
= link
->next
)
83 fprintf (file
, "%c%d(bb %d insn %d) ",
84 DF_REF_REG_DEF_P (link
->ref
)
86 : (DF_REF_FLAGS (link
->ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
87 DF_REF_ID (link
->ref
),
88 DF_REF_BBNO (link
->ref
),
89 DF_REF_IS_ARTIFICIAL (link
->ref
)
90 ? -1 : DF_REF_INSN_UID (link
->ref
));
96 /* Print some basic block info as part of df_dump. */
99 df_print_bb_index (basic_block bb
, FILE *file
)
104 fprintf (file
, "\n( ");
105 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
107 basic_block pred
= e
->src
;
108 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
110 fprintf (file
, ")->[%d]->( ", bb
->index
);
111 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
113 basic_block succ
= e
->dest
;
114 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
116 fprintf (file
, ")\n");
120 /*----------------------------------------------------------------------------
123 Find the locations in the function where each definition site for a
124 pseudo reaches. In and out bitvectors are built for each basic
125 block. The id field in the ref is used to index into these sets.
126 See df.h for details.
128 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
129 existing uses are included in the global reaching DEFs set, or in other
130 words only DEFs that are still live. This is a kind of pruned version
131 of the traditional reaching definitions problem that is much less
132 complex to compute and produces enough information to compute UD-chains.
133 In this context, live must be interpreted in the DF_LR sense: Uses that
134 are upward exposed but maybe not initialized on all paths through the
135 CFG. For a USE that is not reached by a DEF on all paths, we still want
136 to make those DEFs that do reach the USE visible, and pruning based on
137 DF_LIVE would make that impossible.
138 ----------------------------------------------------------------------------*/
140 /* This problem plays a large number of games for the sake of
143 1) The order of the bits in the bitvectors. After the scanning
144 phase, all of the defs are sorted. All of the defs for the reg 0
145 are first, followed by all defs for reg 1 and so on.
147 2) There are two kill sets, one if the number of defs is less or
148 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
151 <= : Data is built directly in the kill set.
153 > : One level of indirection is used to keep from generating long
154 strings of 1 bits in the kill sets. Bitvectors that are indexed
155 by the regnum are used to represent that there is a killing def
156 for the register. The confluence and transfer functions use
157 these along with the bitmap_clear_range call to remove ranges of
158 bits without actually generating a knockout vector.
160 The kill and sparse_kill and the dense_invalidated_by_call and
161 sparse_invalidated_by_call both play this game. */
163 /* Private data used to compute the solution for this problem. These
164 data structures are not accessible outside of this module. */
165 struct df_rd_problem_data
167 /* The set of defs to regs invalidated by call. */
168 bitmap_head sparse_invalidated_by_call
;
169 /* The set of defs to regs invalidate by call for rd. */
170 bitmap_head dense_invalidated_by_call
;
171 /* An obstack for the bitmaps we need for this problem. */
172 bitmap_obstack rd_bitmaps
;
176 /* Free basic block info. */
179 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
182 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
185 bitmap_clear (&bb_info
->kill
);
186 bitmap_clear (&bb_info
->sparse_kill
);
187 bitmap_clear (&bb_info
->gen
);
188 bitmap_clear (&bb_info
->in
);
189 bitmap_clear (&bb_info
->out
);
194 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
195 not touched unless the block is new. */
198 df_rd_alloc (bitmap all_blocks
)
200 unsigned int bb_index
;
202 struct df_rd_problem_data
*problem_data
;
204 if (df_rd
->problem_data
)
206 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
207 bitmap_clear (&problem_data
->sparse_invalidated_by_call
);
208 bitmap_clear (&problem_data
->dense_invalidated_by_call
);
212 problem_data
= XNEW (struct df_rd_problem_data
);
213 df_rd
->problem_data
= problem_data
;
215 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
216 bitmap_initialize (&problem_data
->sparse_invalidated_by_call
,
217 &problem_data
->rd_bitmaps
);
218 bitmap_initialize (&problem_data
->dense_invalidated_by_call
,
219 &problem_data
->rd_bitmaps
);
222 df_grow_bb_info (df_rd
);
224 /* Because of the clustering of all use sites for the same pseudo,
225 we have to process all of the blocks before doing the analysis. */
227 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
229 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
231 /* When bitmaps are already initialized, just clear them. */
232 if (bb_info
->kill
.obstack
)
234 bitmap_clear (&bb_info
->kill
);
235 bitmap_clear (&bb_info
->sparse_kill
);
236 bitmap_clear (&bb_info
->gen
);
240 bitmap_initialize (&bb_info
->kill
, &problem_data
->rd_bitmaps
);
241 bitmap_initialize (&bb_info
->sparse_kill
, &problem_data
->rd_bitmaps
);
242 bitmap_initialize (&bb_info
->gen
, &problem_data
->rd_bitmaps
);
243 bitmap_initialize (&bb_info
->in
, &problem_data
->rd_bitmaps
);
244 bitmap_initialize (&bb_info
->out
, &problem_data
->rd_bitmaps
);
247 df_rd
->optional_p
= true;
251 /* Add the effect of the top artificial defs of BB to the reaching definitions
255 df_rd_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_rd
)
257 int bb_index
= bb
->index
;
259 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
260 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
262 unsigned int dregno
= DF_REF_REGNO (def
);
263 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
264 bitmap_clear_range (local_rd
,
265 DF_DEFS_BEGIN (dregno
),
266 DF_DEFS_COUNT (dregno
));
267 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
271 /* Add the effect of the defs of INSN to the reaching definitions bitmap
275 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx_insn
*insn
,
280 FOR_EACH_INSN_DEF (def
, insn
)
282 unsigned int dregno
= DF_REF_REGNO (def
);
283 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
284 || (dregno
>= FIRST_PSEUDO_REGISTER
))
286 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
287 bitmap_clear_range (local_rd
,
288 DF_DEFS_BEGIN (dregno
),
289 DF_DEFS_COUNT (dregno
));
290 if (!(DF_REF_FLAGS (def
)
291 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
292 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
297 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
298 more complicated than just simulating, because we must produce the
299 gen and kill sets and hence deal with the two possible representations
303 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
307 for (; def
; def
= DF_REF_NEXT_LOC (def
))
309 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
311 unsigned int regno
= DF_REF_REGNO (def
);
312 unsigned int begin
= DF_DEFS_BEGIN (regno
);
313 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
315 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
316 || (regno
>= FIRST_PSEUDO_REGISTER
))
318 /* Only the last def(s) for a regno in the block has any
320 if (!bitmap_bit_p (&seen_in_block
, regno
))
322 /* The first def for regno in insn gets to knock out the
323 defs from other instructions. */
324 if ((!bitmap_bit_p (&seen_in_insn
, regno
))
325 /* If the def is to only part of the reg, it does
326 not kill the other defs that reach here. */
327 && (!(DF_REF_FLAGS (def
) &
328 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
330 if (n_defs
> DF_SPARSE_THRESHOLD
)
332 bitmap_set_bit (&bb_info
->sparse_kill
, regno
);
333 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
337 bitmap_set_range (&bb_info
->kill
, begin
, n_defs
);
338 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
342 bitmap_set_bit (&seen_in_insn
, regno
);
343 /* All defs for regno in the instruction may be put into
345 if (!(DF_REF_FLAGS (def
)
346 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
347 bitmap_set_bit (&bb_info
->gen
, DF_REF_ID (def
));
354 /* Compute local reaching def info for basic block BB. */
357 df_rd_bb_local_compute (unsigned int bb_index
)
359 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
360 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
363 bitmap_clear (&seen_in_block
);
364 bitmap_clear (&seen_in_insn
);
366 /* Artificials are only hard regs. */
367 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
368 df_rd_bb_local_compute_process_def (bb_info
,
369 df_get_artificial_defs (bb_index
),
372 FOR_BB_INSNS_REVERSE (bb
, insn
)
374 unsigned int uid
= INSN_UID (insn
);
379 df_rd_bb_local_compute_process_def (bb_info
,
380 DF_INSN_UID_DEFS (uid
), 0);
382 /* This complex dance with the two bitmaps is required because
383 instructions can assign twice to the same pseudo. This
384 generally happens with calls that will have one def for the
385 result and another def for the clobber. If only one vector
386 is used and the clobber goes first, the result will be
388 bitmap_ior_into (&seen_in_block
, &seen_in_insn
);
389 bitmap_clear (&seen_in_insn
);
392 /* Process the artificial defs at the top of the block last since we
393 are going backwards through the block and these are logically at
395 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
396 df_rd_bb_local_compute_process_def (bb_info
,
397 df_get_artificial_defs (bb_index
),
402 /* Compute local reaching def info for each basic block within BLOCKS. */
405 df_rd_local_compute (bitmap all_blocks
)
407 unsigned int bb_index
;
410 struct df_rd_problem_data
*problem_data
411 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
412 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
413 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
415 bitmap_initialize (&seen_in_block
, &df_bitmap_obstack
);
416 bitmap_initialize (&seen_in_insn
, &df_bitmap_obstack
);
418 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
420 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
422 df_rd_bb_local_compute (bb_index
);
425 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
426 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset
, 0, regno
, bi
)
428 if (! HARD_REGISTER_NUM_P (regno
)
429 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
431 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
432 bitmap_set_bit (sparse_invalidated
, regno
);
434 bitmap_set_range (dense_invalidated
,
435 DF_DEFS_BEGIN (regno
),
436 DF_DEFS_COUNT (regno
));
440 bitmap_clear (&seen_in_block
);
441 bitmap_clear (&seen_in_insn
);
445 /* Initialize the solution bit vectors for problem. */
448 df_rd_init_solution (bitmap all_blocks
)
450 unsigned int bb_index
;
453 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
455 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
457 bitmap_copy (&bb_info
->out
, &bb_info
->gen
);
458 bitmap_clear (&bb_info
->in
);
462 /* In of target gets or of out of source. */
465 df_rd_confluence_n (edge e
)
467 bitmap op1
= &df_rd_get_bb_info (e
->dest
->index
)->in
;
468 bitmap op2
= &df_rd_get_bb_info (e
->src
->index
)->out
;
469 bool changed
= false;
471 if (e
->flags
& EDGE_FAKE
)
474 if (e
->flags
& EDGE_EH
)
476 struct df_rd_problem_data
*problem_data
477 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
478 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
479 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
484 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
485 bitmap_and_compl (&tmp
, op2
, dense_invalidated
);
487 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
489 bitmap_clear_range (&tmp
,
490 DF_DEFS_BEGIN (regno
),
491 DF_DEFS_COUNT (regno
));
493 changed
|= bitmap_ior_into (op1
, &tmp
);
498 return bitmap_ior_into (op1
, op2
);
502 /* Transfer function. */
505 df_rd_transfer_function (int bb_index
)
507 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
510 bitmap in
= &bb_info
->in
;
511 bitmap out
= &bb_info
->out
;
512 bitmap gen
= &bb_info
->gen
;
513 bitmap kill
= &bb_info
->kill
;
514 bitmap sparse_kill
= &bb_info
->sparse_kill
;
515 bool changed
= false;
517 if (bitmap_empty_p (sparse_kill
))
518 changed
= bitmap_ior_and_compl (out
, gen
, in
, kill
);
521 struct df_rd_problem_data
*problem_data
;
524 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
525 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
526 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
527 bitmap_initialize (&tmp
, &problem_data
->rd_bitmaps
);
529 bitmap_and_compl (&tmp
, in
, kill
);
530 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
532 bitmap_clear_range (&tmp
,
533 DF_DEFS_BEGIN (regno
),
534 DF_DEFS_COUNT (regno
));
536 bitmap_ior_into (&tmp
, gen
);
537 changed
= !bitmap_equal_p (&tmp
, out
);
547 if (df
->changeable_flags
& DF_RD_PRUNE_DEAD_DEFS
)
549 /* Create a mask of DEFs for all registers live at the end of this
550 basic block, and mask out DEFs of registers that are not live.
551 Computing the mask looks costly, but the benefit of the pruning
552 outweighs the cost. */
553 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
554 bitmap regs_live_out
= &df_lr_get_bb_info (bb_index
)->out
;
555 bitmap live_defs
= BITMAP_ALLOC (&df_bitmap_obstack
);
559 EXECUTE_IF_SET_IN_BITMAP (regs_live_out
, 0, regno
, bi
)
560 bitmap_set_range (live_defs
,
561 DF_DEFS_BEGIN (regno
),
562 DF_DEFS_COUNT (regno
));
563 changed
|= bitmap_and_into (&bb_info
->out
, live_defs
);
564 BITMAP_FREE (live_defs
);
570 /* Free all storage associated with the problem. */
575 struct df_rd_problem_data
*problem_data
576 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
580 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
582 df_rd
->block_info_size
= 0;
583 free (df_rd
->block_info
);
584 df_rd
->block_info
= NULL
;
585 free (df_rd
->problem_data
);
591 /* Debugging info. */
594 df_rd_start_dump (FILE *file
)
596 struct df_rd_problem_data
*problem_data
597 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
598 unsigned int m
= DF_REG_SIZE (df
);
601 if (!df_rd
->block_info
)
604 fprintf (file
, ";; Reaching defs:\n");
606 fprintf (file
, ";; sparse invalidated \t");
607 dump_bitmap (file
, &problem_data
->sparse_invalidated_by_call
);
608 fprintf (file
, ";; dense invalidated \t");
609 dump_bitmap (file
, &problem_data
->dense_invalidated_by_call
);
611 fprintf (file
, ";; reg->defs[] map:\t");
612 for (regno
= 0; regno
< m
; regno
++)
613 if (DF_DEFS_COUNT (regno
))
614 fprintf (file
, "%d[%d,%d] ", regno
,
615 DF_DEFS_BEGIN (regno
),
616 DF_DEFS_BEGIN (regno
) + DF_DEFS_COUNT (regno
) - 1);
617 fprintf (file
, "\n");
622 df_rd_dump_defs_set (bitmap defs_set
, const char *prefix
, FILE *file
)
626 unsigned int m
= DF_REG_SIZE (df
);
627 bool first_reg
= true;
629 fprintf (file
, "%s\t(%d) ", prefix
, (int) bitmap_count_bits (defs_set
));
631 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
632 for (regno
= 0; regno
< m
; regno
++)
634 if (HARD_REGISTER_NUM_P (regno
)
635 && (df
->changeable_flags
& DF_NO_HARD_REGS
))
637 bitmap_set_range (&tmp
, DF_DEFS_BEGIN (regno
), DF_DEFS_COUNT (regno
));
638 bitmap_and_into (&tmp
, defs_set
);
639 if (! bitmap_empty_p (&tmp
))
643 bool first_def
= true;
649 fprintf (file
, "%u[", regno
);
650 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, ix
, bi
)
652 fprintf (file
, "%s%u", first_def
? "" : ",", ix
);
660 fprintf (file
, "\n");
664 /* Debugging info at top of bb. */
667 df_rd_top_dump (basic_block bb
, FILE *file
)
669 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
673 df_rd_dump_defs_set (&bb_info
->in
, ";; rd in ", file
);
674 df_rd_dump_defs_set (&bb_info
->gen
, ";; rd gen ", file
);
675 df_rd_dump_defs_set (&bb_info
->kill
, ";; rd kill", file
);
679 /* Debugging info at bottom of bb. */
682 df_rd_bottom_dump (basic_block bb
, FILE *file
)
684 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
688 df_rd_dump_defs_set (&bb_info
->out
, ";; rd out ", file
);
691 /* All of the information associated with every instance of the problem. */
693 static struct df_problem problem_RD
=
695 DF_RD
, /* Problem id. */
696 DF_FORWARD
, /* Direction. */
697 df_rd_alloc
, /* Allocate the problem specific data. */
698 NULL
, /* Reset global information. */
699 df_rd_free_bb_info
, /* Free basic block info. */
700 df_rd_local_compute
, /* Local compute function. */
701 df_rd_init_solution
, /* Init the solution specific data. */
702 df_worklist_dataflow
, /* Worklist solver. */
703 NULL
, /* Confluence operator 0. */
704 df_rd_confluence_n
, /* Confluence operator n. */
705 df_rd_transfer_function
, /* Transfer function. */
706 NULL
, /* Finalize function. */
707 df_rd_free
, /* Free all of the problem information. */
708 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
709 df_rd_start_dump
, /* Debugging. */
710 df_rd_top_dump
, /* Debugging start block. */
711 df_rd_bottom_dump
, /* Debugging end block. */
712 NULL
, /* Debugging start insn. */
713 NULL
, /* Debugging end insn. */
714 NULL
, /* Incremental solution verify start. */
715 NULL
, /* Incremental solution verify end. */
716 NULL
, /* Dependent problem. */
717 sizeof (struct df_rd_bb_info
),/* Size of entry of block_info array. */
718 TV_DF_RD
, /* Timing variable. */
719 true /* Reset blocks on dropping out of blocks_to_analyze. */
724 /* Create a new RD instance and add it to the existing instance
728 df_rd_add_problem (void)
730 df_add_problem (&problem_RD
);
735 /*----------------------------------------------------------------------------
738 Find the locations in the function where any use of a pseudo can
739 reach in the backwards direction. In and out bitvectors are built
740 for each basic block. The regno is used to index into these sets.
741 See df.h for details.
742 ----------------------------------------------------------------------------*/
744 /* Private data used to verify the solution for this problem. */
745 struct df_lr_problem_data
749 /* An obstack for the bitmaps we need for this problem. */
750 bitmap_obstack lr_bitmaps
;
753 /* Free basic block info. */
756 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
759 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
762 bitmap_clear (&bb_info
->use
);
763 bitmap_clear (&bb_info
->def
);
764 bitmap_clear (&bb_info
->in
);
765 bitmap_clear (&bb_info
->out
);
770 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
771 not touched unless the block is new. */
774 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
776 unsigned int bb_index
;
778 struct df_lr_problem_data
*problem_data
;
780 df_grow_bb_info (df_lr
);
781 if (df_lr
->problem_data
)
782 problem_data
= (struct df_lr_problem_data
*) df_lr
->problem_data
;
785 problem_data
= XNEW (struct df_lr_problem_data
);
786 df_lr
->problem_data
= problem_data
;
788 problem_data
->out
= NULL
;
789 problem_data
->in
= NULL
;
790 bitmap_obstack_initialize (&problem_data
->lr_bitmaps
);
793 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
795 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
797 /* When bitmaps are already initialized, just clear them. */
798 if (bb_info
->use
.obstack
)
800 bitmap_clear (&bb_info
->def
);
801 bitmap_clear (&bb_info
->use
);
805 bitmap_initialize (&bb_info
->use
, &problem_data
->lr_bitmaps
);
806 bitmap_initialize (&bb_info
->def
, &problem_data
->lr_bitmaps
);
807 bitmap_initialize (&bb_info
->in
, &problem_data
->lr_bitmaps
);
808 bitmap_initialize (&bb_info
->out
, &problem_data
->lr_bitmaps
);
812 df_lr
->optional_p
= false;
816 /* Reset the global solution for recalculation. */
819 df_lr_reset (bitmap all_blocks
)
821 unsigned int bb_index
;
824 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
826 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
827 gcc_assert (bb_info
);
828 bitmap_clear (&bb_info
->in
);
829 bitmap_clear (&bb_info
->out
);
834 /* Compute local live register info for basic block BB. */
837 df_lr_bb_local_compute (unsigned int bb_index
)
839 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
840 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
844 /* Process the registers set in an exception handler. */
845 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
846 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
848 unsigned int dregno
= DF_REF_REGNO (def
);
849 bitmap_set_bit (&bb_info
->def
, dregno
);
850 bitmap_clear_bit (&bb_info
->use
, dregno
);
853 /* Process the hardware registers that are always live. */
854 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
855 /* Add use to set of uses in this BB. */
856 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
857 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
859 FOR_BB_INSNS_REVERSE (bb
, insn
)
861 if (!NONDEBUG_INSN_P (insn
))
864 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
865 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
866 /* If the def is to only part of the reg, it does
867 not kill the other defs that reach here. */
868 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
870 unsigned int dregno
= DF_REF_REGNO (def
);
871 bitmap_set_bit (&bb_info
->def
, dregno
);
872 bitmap_clear_bit (&bb_info
->use
, dregno
);
875 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
876 /* Add use to set of uses in this BB. */
877 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
880 /* Process the registers set in an exception handler or the hard
881 frame pointer if this block is the target of a non local
883 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
884 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
886 unsigned int dregno
= DF_REF_REGNO (def
);
887 bitmap_set_bit (&bb_info
->def
, dregno
);
888 bitmap_clear_bit (&bb_info
->use
, dregno
);
892 /* Process the uses that are live into an exception handler. */
893 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
894 /* Add use to set of uses in this BB. */
895 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
896 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
899 /* If the df_live problem is not defined, such as at -O0 and -O1, we
900 still need to keep the luids up to date. This is normally done
901 in the df_live problem since this problem has a forwards
904 df_recompute_luids (bb
);
908 /* Compute local live register info for each basic block within BLOCKS. */
911 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
913 unsigned int bb_index
, i
;
916 bitmap_clear (&df
->hardware_regs_used
);
918 /* The all-important stack pointer must always be live. */
919 bitmap_set_bit (&df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
921 /* Global regs are always live, too. */
922 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
924 bitmap_set_bit (&df
->hardware_regs_used
, i
);
926 /* Before reload, there are a few registers that must be forced
927 live everywhere -- which might not already be the case for
928 blocks within infinite loops. */
929 if (!reload_completed
)
931 unsigned int pic_offset_table_regnum
= PIC_OFFSET_TABLE_REGNUM
;
932 /* Any reference to any pseudo before reload is a potential
933 reference of the frame pointer. */
934 bitmap_set_bit (&df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
936 /* Pseudos with argument area equivalences may require
937 reloading via the argument pointer. */
938 if (FRAME_POINTER_REGNUM
!= ARG_POINTER_REGNUM
939 && fixed_regs
[ARG_POINTER_REGNUM
])
940 bitmap_set_bit (&df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
942 /* Any constant, or pseudo with constant equivalences, may
943 require reloading from memory using the pic register. */
944 if (pic_offset_table_regnum
!= INVALID_REGNUM
945 && fixed_regs
[pic_offset_table_regnum
])
946 bitmap_set_bit (&df
->hardware_regs_used
, pic_offset_table_regnum
);
949 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
951 if (bb_index
== EXIT_BLOCK
)
953 /* The exit block is special for this problem and its bits are
954 computed from thin air. */
955 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
956 bitmap_copy (&bb_info
->use
, df
->exit_block_uses
);
959 df_lr_bb_local_compute (bb_index
);
962 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
966 /* Initialize the solution vectors. */
969 df_lr_init (bitmap all_blocks
)
971 unsigned int bb_index
;
974 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
976 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
977 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
978 bitmap_clear (&bb_info
->out
);
983 /* Confluence function that processes infinite loops. This might be a
984 noreturn function that throws. And even if it isn't, getting the
985 unwind info right helps debugging. */
987 df_lr_confluence_0 (basic_block bb
)
989 bitmap op1
= &df_lr_get_bb_info (bb
->index
)->out
;
990 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
991 bitmap_copy (op1
, &df
->hardware_regs_used
);
995 /* Confluence function that ignores fake edges. */
998 df_lr_confluence_n (edge e
)
1000 bitmap op1
= &df_lr_get_bb_info (e
->src
->index
)->out
;
1001 bitmap op2
= &df_lr_get_bb_info (e
->dest
->index
)->in
;
1002 bool changed
= false;
1004 /* Call-clobbered registers die across exception and call edges. */
1005 /* ??? Abnormal call edges ignored for the moment, as this gets
1006 confused by sibling call edges, which crashes reg-stack. */
1007 if (e
->flags
& EDGE_EH
)
1008 changed
= bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
1010 changed
= bitmap_ior_into (op1
, op2
);
1012 changed
|= bitmap_ior_into (op1
, &df
->hardware_regs_used
);
1017 /* Transfer function. */
1020 df_lr_transfer_function (int bb_index
)
1022 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1023 bitmap in
= &bb_info
->in
;
1024 bitmap out
= &bb_info
->out
;
1025 bitmap use
= &bb_info
->use
;
1026 bitmap def
= &bb_info
->def
;
1028 return bitmap_ior_and_compl (in
, use
, out
, def
);
1032 /* Run the fast dce as a side effect of building LR. */
1035 df_lr_finalize (bitmap all_blocks
)
1037 df_lr
->solutions_dirty
= false;
1038 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1042 /* If dce deletes some instructions, we need to recompute the lr
1043 solution before proceeding further. The problem is that fast
1044 dce is a pessimestic dataflow algorithm. In the case where
1045 it deletes a statement S inside of a loop, the uses inside of
1046 S may not be deleted from the dataflow solution because they
1047 were carried around the loop. While it is conservatively
1048 correct to leave these extra bits, the standards of df
1049 require that we maintain the best possible (least fixed
1050 point) solution. The only way to do that is to redo the
1051 iteration from the beginning. See PR35805 for an
1053 if (df_lr
->solutions_dirty
)
1055 df_clear_flags (DF_LR_RUN_DCE
);
1056 df_lr_alloc (all_blocks
);
1057 df_lr_local_compute (all_blocks
);
1058 df_worklist_dataflow (df_lr
, all_blocks
, df
->postorder
, df
->n_blocks
);
1059 df_lr_finalize (all_blocks
);
1060 df_set_flags (DF_LR_RUN_DCE
);
1066 /* Free all storage associated with the problem. */
1071 struct df_lr_problem_data
*problem_data
1072 = (struct df_lr_problem_data
*) df_lr
->problem_data
;
1073 if (df_lr
->block_info
)
1076 df_lr
->block_info_size
= 0;
1077 free (df_lr
->block_info
);
1078 df_lr
->block_info
= NULL
;
1079 bitmap_obstack_release (&problem_data
->lr_bitmaps
);
1080 free (df_lr
->problem_data
);
1081 df_lr
->problem_data
= NULL
;
1084 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1089 /* Debugging info at top of bb. */
1092 df_lr_top_dump (basic_block bb
, FILE *file
)
1094 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1095 struct df_lr_problem_data
*problem_data
;
1099 fprintf (file
, ";; lr in \t");
1100 df_print_regset (file
, &bb_info
->in
);
1101 if (df_lr
->problem_data
)
1103 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1104 if (problem_data
->in
)
1106 fprintf (file
, ";; old in \t");
1107 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1110 fprintf (file
, ";; lr use \t");
1111 df_print_regset (file
, &bb_info
->use
);
1112 fprintf (file
, ";; lr def \t");
1113 df_print_regset (file
, &bb_info
->def
);
1117 /* Debugging info at bottom of bb. */
1120 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1122 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1123 struct df_lr_problem_data
*problem_data
;
1127 fprintf (file
, ";; lr out \t");
1128 df_print_regset (file
, &bb_info
->out
);
1129 if (df_lr
->problem_data
)
1131 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1132 if (problem_data
->out
)
1134 fprintf (file
, ";; old out \t");
1135 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1141 /* Build the datastructure to verify that the solution to the dataflow
1142 equations is not dirty. */
1145 df_lr_verify_solution_start (void)
1148 struct df_lr_problem_data
*problem_data
;
1149 if (df_lr
->solutions_dirty
)
1152 /* Set it true so that the solution is recomputed. */
1153 df_lr
->solutions_dirty
= true;
1155 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1156 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1157 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1159 FOR_ALL_BB_FN (bb
, cfun
)
1161 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->lr_bitmaps
);
1162 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->lr_bitmaps
);
1163 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1164 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1169 /* Compare the saved datastructure and the new solution to the dataflow
1173 df_lr_verify_solution_end (void)
1175 struct df_lr_problem_data
*problem_data
;
1178 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1180 if (!problem_data
->out
)
1183 if (df_lr
->solutions_dirty
)
1184 /* Do not check if the solution is still dirty. See the comment
1185 in df_lr_finalize for details. */
1186 df_lr
->solutions_dirty
= false;
1188 FOR_ALL_BB_FN (bb
, cfun
)
1190 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1191 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1193 /*df_dump (stderr);*/
1198 /* Cannot delete them immediately because you may want to dump them
1199 if the comparison fails. */
1200 FOR_ALL_BB_FN (bb
, cfun
)
1202 bitmap_clear (&problem_data
->in
[bb
->index
]);
1203 bitmap_clear (&problem_data
->out
[bb
->index
]);
1206 free (problem_data
->in
);
1207 free (problem_data
->out
);
1208 problem_data
->in
= NULL
;
1209 problem_data
->out
= NULL
;
1213 /* All of the information associated with every instance of the problem. */
1215 static struct df_problem problem_LR
=
1217 DF_LR
, /* Problem id. */
1218 DF_BACKWARD
, /* Direction. */
1219 df_lr_alloc
, /* Allocate the problem specific data. */
1220 df_lr_reset
, /* Reset global information. */
1221 df_lr_free_bb_info
, /* Free basic block info. */
1222 df_lr_local_compute
, /* Local compute function. */
1223 df_lr_init
, /* Init the solution specific data. */
1224 df_worklist_dataflow
, /* Worklist solver. */
1225 df_lr_confluence_0
, /* Confluence operator 0. */
1226 df_lr_confluence_n
, /* Confluence operator n. */
1227 df_lr_transfer_function
, /* Transfer function. */
1228 df_lr_finalize
, /* Finalize function. */
1229 df_lr_free
, /* Free all of the problem information. */
1230 NULL
, /* Remove this problem from the stack of dataflow problems. */
1231 NULL
, /* Debugging. */
1232 df_lr_top_dump
, /* Debugging start block. */
1233 df_lr_bottom_dump
, /* Debugging end block. */
1234 NULL
, /* Debugging start insn. */
1235 NULL
, /* Debugging end insn. */
1236 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1237 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1238 NULL
, /* Dependent problem. */
1239 sizeof (struct df_lr_bb_info
),/* Size of entry of block_info array. */
1240 TV_DF_LR
, /* Timing variable. */
1241 false /* Reset blocks on dropping out of blocks_to_analyze. */
1245 /* Create a new DATAFLOW instance and add it to an existing instance
1246 of DF. The returned structure is what is used to get at the
1250 df_lr_add_problem (void)
1252 df_add_problem (&problem_LR
);
1253 /* These will be initialized when df_scan_blocks processes each
1255 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
1259 /* Verify that all of the lr related info is consistent and
1263 df_lr_verify_transfer_functions (void)
1266 bitmap_head saved_def
;
1267 bitmap_head saved_use
;
1268 bitmap_head all_blocks
;
1273 bitmap_initialize (&saved_def
, &bitmap_default_obstack
);
1274 bitmap_initialize (&saved_use
, &bitmap_default_obstack
);
1275 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1277 FOR_ALL_BB_FN (bb
, cfun
)
1279 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1280 bitmap_set_bit (&all_blocks
, bb
->index
);
1284 /* Make a copy of the transfer functions and then compute
1285 new ones to see if the transfer functions have
1287 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1290 bitmap_copy (&saved_def
, &bb_info
->def
);
1291 bitmap_copy (&saved_use
, &bb_info
->use
);
1292 bitmap_clear (&bb_info
->def
);
1293 bitmap_clear (&bb_info
->use
);
1295 df_lr_bb_local_compute (bb
->index
);
1296 gcc_assert (bitmap_equal_p (&saved_def
, &bb_info
->def
));
1297 gcc_assert (bitmap_equal_p (&saved_use
, &bb_info
->use
));
1302 /* If we do not have basic block info, the block must be in
1303 the list of dirty blocks or else some one has added a
1304 block behind our backs. */
1305 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1308 /* Make sure no one created a block without following
1310 gcc_assert (df_scan_get_bb_info (bb
->index
));
1313 /* Make sure there are no dirty bits in blocks that have been deleted. */
1314 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1317 bitmap_clear (&saved_def
);
1318 bitmap_clear (&saved_use
);
1319 bitmap_clear (&all_blocks
);
1324 /*----------------------------------------------------------------------------
1325 LIVE AND MUST-INITIALIZED REGISTERS.
1327 This problem first computes the IN and OUT bitvectors for the
1328 must-initialized registers problems, which is a forward problem.
1329 It gives the set of registers for which we MUST have an available
1330 definition on any path from the entry block to the entry/exit of
1331 a basic block. Sets generate a definition, while clobbers kill
1334 In and out bitvectors are built for each basic block and are indexed by
1335 regnum (see df.h for details). In and out bitvectors in struct
1336 df_live_bb_info actually refers to the must-initialized problem;
1338 Then, the in and out sets for the LIVE problem itself are computed.
1339 These are the logical AND of the IN and OUT sets from the LR problem
1340 and the must-initialized problem.
1341 ----------------------------------------------------------------------------*/
1343 /* Private data used to verify the solution for this problem. */
1344 struct df_live_problem_data
1348 /* An obstack for the bitmaps we need for this problem. */
1349 bitmap_obstack live_bitmaps
;
1352 /* Scratch var used by transfer functions. This is used to implement
1353 an optimization to reduce the amount of space used to compute the
1354 combined lr and live analysis. */
1355 static bitmap_head df_live_scratch
;
1358 /* Free basic block info. */
1361 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1364 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1367 bitmap_clear (&bb_info
->gen
);
1368 bitmap_clear (&bb_info
->kill
);
1369 bitmap_clear (&bb_info
->in
);
1370 bitmap_clear (&bb_info
->out
);
1375 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1376 not touched unless the block is new. */
1379 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1381 unsigned int bb_index
;
1383 struct df_live_problem_data
*problem_data
;
1385 if (df_live
->problem_data
)
1386 problem_data
= (struct df_live_problem_data
*) df_live
->problem_data
;
1389 problem_data
= XNEW (struct df_live_problem_data
);
1390 df_live
->problem_data
= problem_data
;
1392 problem_data
->out
= NULL
;
1393 problem_data
->in
= NULL
;
1394 bitmap_obstack_initialize (&problem_data
->live_bitmaps
);
1395 bitmap_initialize (&df_live_scratch
, &problem_data
->live_bitmaps
);
1398 df_grow_bb_info (df_live
);
1400 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1402 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1404 /* When bitmaps are already initialized, just clear them. */
1405 if (bb_info
->kill
.obstack
)
1407 bitmap_clear (&bb_info
->kill
);
1408 bitmap_clear (&bb_info
->gen
);
1412 bitmap_initialize (&bb_info
->kill
, &problem_data
->live_bitmaps
);
1413 bitmap_initialize (&bb_info
->gen
, &problem_data
->live_bitmaps
);
1414 bitmap_initialize (&bb_info
->in
, &problem_data
->live_bitmaps
);
1415 bitmap_initialize (&bb_info
->out
, &problem_data
->live_bitmaps
);
1418 df_live
->optional_p
= (optimize
<= 1);
1422 /* Reset the global solution for recalculation. */
1425 df_live_reset (bitmap all_blocks
)
1427 unsigned int bb_index
;
1430 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1432 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1433 gcc_assert (bb_info
);
1434 bitmap_clear (&bb_info
->in
);
1435 bitmap_clear (&bb_info
->out
);
1440 /* Compute local uninitialized register info for basic block BB. */
1443 df_live_bb_local_compute (unsigned int bb_index
)
1445 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
1446 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1451 FOR_BB_INSNS (bb
, insn
)
1453 unsigned int uid
= INSN_UID (insn
);
1454 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1456 /* Inserting labels does not always trigger the incremental
1460 gcc_assert (!INSN_P (insn
));
1461 insn_info
= df_insn_create_insn_record (insn
);
1464 DF_INSN_INFO_LUID (insn_info
) = luid
;
1469 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1471 unsigned int regno
= DF_REF_REGNO (def
);
1473 if (DF_REF_FLAGS_IS_SET (def
,
1474 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1475 /* All partial or conditional def
1476 seen are included in the gen set. */
1477 bitmap_set_bit (&bb_info
->gen
, regno
);
1478 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1479 /* Only must clobbers for the entire reg destroy the
1481 bitmap_set_bit (&bb_info
->kill
, regno
);
1482 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1483 bitmap_set_bit (&bb_info
->gen
, regno
);
1487 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
1488 bitmap_set_bit (&bb_info
->gen
, DF_REF_REGNO (def
));
1492 /* Compute local uninitialized register info. */
1495 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1497 unsigned int bb_index
;
1500 df_grow_insn_info ();
1502 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1505 df_live_bb_local_compute (bb_index
);
1508 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1512 /* Initialize the solution vectors. */
1515 df_live_init (bitmap all_blocks
)
1517 unsigned int bb_index
;
1520 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1522 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1523 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1525 /* No register may reach a location where it is not used. Thus
1526 we trim the rr result to the places where it is used. */
1527 bitmap_and (&bb_info
->out
, &bb_info
->gen
, &bb_lr_info
->out
);
1528 bitmap_clear (&bb_info
->in
);
1532 /* Forward confluence function that ignores fake edges. */
1535 df_live_confluence_n (edge e
)
1537 bitmap op1
= &df_live_get_bb_info (e
->dest
->index
)->in
;
1538 bitmap op2
= &df_live_get_bb_info (e
->src
->index
)->out
;
1540 if (e
->flags
& EDGE_FAKE
)
1543 return bitmap_ior_into (op1
, op2
);
1547 /* Transfer function for the forwards must-initialized problem. */
1550 df_live_transfer_function (int bb_index
)
1552 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1553 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1554 bitmap in
= &bb_info
->in
;
1555 bitmap out
= &bb_info
->out
;
1556 bitmap gen
= &bb_info
->gen
;
1557 bitmap kill
= &bb_info
->kill
;
1559 /* We need to use a scratch set here so that the value returned from this
1560 function invocation properly reflects whether the sets changed in a
1561 significant way; i.e. not just because the lr set was anded in. */
1562 bitmap_and (&df_live_scratch
, gen
, &bb_lr_info
->out
);
1563 /* No register may reach a location where it is not used. Thus
1564 we trim the rr result to the places where it is used. */
1565 bitmap_and_into (in
, &bb_lr_info
->in
);
1567 return bitmap_ior_and_compl (out
, &df_live_scratch
, in
, kill
);
1571 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1574 df_live_finalize (bitmap all_blocks
)
1577 if (df_live
->solutions_dirty
)
1580 unsigned int bb_index
;
1582 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1584 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1585 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1587 /* No register may reach a location where it is not used. Thus
1588 we trim the rr result to the places where it is used. */
1589 bitmap_and_into (&bb_live_info
->in
, &bb_lr_info
->in
);
1590 bitmap_and_into (&bb_live_info
->out
, &bb_lr_info
->out
);
1593 df_live
->solutions_dirty
= false;
1598 /* Free all storage associated with the problem. */
1603 struct df_live_problem_data
*problem_data
1604 = (struct df_live_problem_data
*) df_live
->problem_data
;
1605 if (df_live
->block_info
)
1607 df_live
->block_info_size
= 0;
1608 free (df_live
->block_info
);
1609 df_live
->block_info
= NULL
;
1610 bitmap_clear (&df_live_scratch
);
1611 bitmap_obstack_release (&problem_data
->live_bitmaps
);
1612 free (problem_data
);
1613 df_live
->problem_data
= NULL
;
1615 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1620 /* Debugging info at top of bb. */
1623 df_live_top_dump (basic_block bb
, FILE *file
)
1625 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1626 struct df_live_problem_data
*problem_data
;
1631 fprintf (file
, ";; live in \t");
1632 df_print_regset (file
, &bb_info
->in
);
1633 if (df_live
->problem_data
)
1635 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1636 if (problem_data
->in
)
1638 fprintf (file
, ";; old in \t");
1639 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1642 fprintf (file
, ";; live gen \t");
1643 df_print_regset (file
, &bb_info
->gen
);
1644 fprintf (file
, ";; live kill\t");
1645 df_print_regset (file
, &bb_info
->kill
);
1649 /* Debugging info at bottom of bb. */
1652 df_live_bottom_dump (basic_block bb
, FILE *file
)
1654 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1655 struct df_live_problem_data
*problem_data
;
1660 fprintf (file
, ";; live out \t");
1661 df_print_regset (file
, &bb_info
->out
);
1662 if (df_live
->problem_data
)
1664 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1665 if (problem_data
->out
)
1667 fprintf (file
, ";; old out \t");
1668 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1674 /* Build the datastructure to verify that the solution to the dataflow
1675 equations is not dirty. */
1678 df_live_verify_solution_start (void)
1681 struct df_live_problem_data
*problem_data
;
1682 if (df_live
->solutions_dirty
)
1685 /* Set it true so that the solution is recomputed. */
1686 df_live
->solutions_dirty
= true;
1688 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1689 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1690 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1692 FOR_ALL_BB_FN (bb
, cfun
)
1694 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->live_bitmaps
);
1695 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->live_bitmaps
);
1696 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1697 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1702 /* Compare the saved datastructure and the new solution to the dataflow
1706 df_live_verify_solution_end (void)
1708 struct df_live_problem_data
*problem_data
;
1711 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1712 if (!problem_data
->out
)
1715 FOR_ALL_BB_FN (bb
, cfun
)
1717 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1718 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
1720 /*df_dump (stderr);*/
1725 /* Cannot delete them immediately because you may want to dump them
1726 if the comparison fails. */
1727 FOR_ALL_BB_FN (bb
, cfun
)
1729 bitmap_clear (&problem_data
->in
[bb
->index
]);
1730 bitmap_clear (&problem_data
->out
[bb
->index
]);
1733 free (problem_data
->in
);
1734 free (problem_data
->out
);
1735 free (problem_data
);
1736 df_live
->problem_data
= NULL
;
1740 /* All of the information associated with every instance of the problem. */
1742 static struct df_problem problem_LIVE
=
1744 DF_LIVE
, /* Problem id. */
1745 DF_FORWARD
, /* Direction. */
1746 df_live_alloc
, /* Allocate the problem specific data. */
1747 df_live_reset
, /* Reset global information. */
1748 df_live_free_bb_info
, /* Free basic block info. */
1749 df_live_local_compute
, /* Local compute function. */
1750 df_live_init
, /* Init the solution specific data. */
1751 df_worklist_dataflow
, /* Worklist solver. */
1752 NULL
, /* Confluence operator 0. */
1753 df_live_confluence_n
, /* Confluence operator n. */
1754 df_live_transfer_function
, /* Transfer function. */
1755 df_live_finalize
, /* Finalize function. */
1756 df_live_free
, /* Free all of the problem information. */
1757 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1758 NULL
, /* Debugging. */
1759 df_live_top_dump
, /* Debugging start block. */
1760 df_live_bottom_dump
, /* Debugging end block. */
1761 NULL
, /* Debugging start insn. */
1762 NULL
, /* Debugging end insn. */
1763 df_live_verify_solution_start
,/* Incremental solution verify start. */
1764 df_live_verify_solution_end
, /* Incremental solution verify end. */
1765 &problem_LR
, /* Dependent problem. */
1766 sizeof (struct df_live_bb_info
),/* Size of entry of block_info array. */
1767 TV_DF_LIVE
, /* Timing variable. */
1768 false /* Reset blocks on dropping out of blocks_to_analyze. */
1772 /* Create a new DATAFLOW instance and add it to an existing instance
1773 of DF. The returned structure is what is used to get at the
1777 df_live_add_problem (void)
1779 df_add_problem (&problem_LIVE
);
1780 /* These will be initialized when df_scan_blocks processes each
1782 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
1786 /* Set all of the blocks as dirty. This needs to be done if this
1787 problem is added after all of the insns have been scanned. */
1790 df_live_set_all_dirty (void)
1793 FOR_ALL_BB_FN (bb
, cfun
)
1794 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1799 /* Verify that all of the lr related info is consistent and
1803 df_live_verify_transfer_functions (void)
1806 bitmap_head saved_gen
;
1807 bitmap_head saved_kill
;
1808 bitmap_head all_blocks
;
1813 bitmap_initialize (&saved_gen
, &bitmap_default_obstack
);
1814 bitmap_initialize (&saved_kill
, &bitmap_default_obstack
);
1815 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1817 df_grow_insn_info ();
1819 FOR_ALL_BB_FN (bb
, cfun
)
1821 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1822 bitmap_set_bit (&all_blocks
, bb
->index
);
1826 /* Make a copy of the transfer functions and then compute
1827 new ones to see if the transfer functions have
1829 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1832 bitmap_copy (&saved_gen
, &bb_info
->gen
);
1833 bitmap_copy (&saved_kill
, &bb_info
->kill
);
1834 bitmap_clear (&bb_info
->gen
);
1835 bitmap_clear (&bb_info
->kill
);
1837 df_live_bb_local_compute (bb
->index
);
1838 gcc_assert (bitmap_equal_p (&saved_gen
, &bb_info
->gen
));
1839 gcc_assert (bitmap_equal_p (&saved_kill
, &bb_info
->kill
));
1844 /* If we do not have basic block info, the block must be in
1845 the list of dirty blocks or else some one has added a
1846 block behind our backs. */
1847 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1850 /* Make sure no one created a block without following
1852 gcc_assert (df_scan_get_bb_info (bb
->index
));
1855 /* Make sure there are no dirty bits in blocks that have been deleted. */
1856 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1858 bitmap_clear (&saved_gen
);
1859 bitmap_clear (&saved_kill
);
1860 bitmap_clear (&all_blocks
);
1863 /*----------------------------------------------------------------------------
1864 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1866 Link either the defs to the uses and / or the uses to the defs.
1868 These problems are set up like the other dataflow problems so that
1869 they nicely fit into the framework. They are much simpler and only
1870 involve a single traversal of instructions and an examination of
1871 the reaching defs information (the dependent problem).
1872 ----------------------------------------------------------------------------*/
1874 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1876 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1879 df_chain_create (df_ref src
, df_ref dst
)
1881 struct df_link
*head
= DF_REF_CHAIN (src
);
1882 struct df_link
*link
= df_chain
->block_pool
->allocate ();
1884 DF_REF_CHAIN (src
) = link
;
1891 /* Delete any du or ud chains that start at REF and point to
1894 df_chain_unlink_1 (df_ref ref
, df_ref target
)
1896 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1897 struct df_link
*prev
= NULL
;
1901 if (chain
->ref
== target
)
1904 prev
->next
= chain
->next
;
1906 DF_REF_CHAIN (ref
) = chain
->next
;
1907 df_chain
->block_pool
->remove (chain
);
1911 chain
= chain
->next
;
1916 /* Delete a du or ud chain that leave or point to REF. */
1919 df_chain_unlink (df_ref ref
)
1921 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1924 struct df_link
*next
= chain
->next
;
1925 /* Delete the other side if it exists. */
1926 df_chain_unlink_1 (chain
->ref
, ref
);
1927 df_chain
->block_pool
->remove (chain
);
1930 DF_REF_CHAIN (ref
) = NULL
;
1934 /* Copy the du or ud chain starting at FROM_REF and attach it to
1938 df_chain_copy (df_ref to_ref
,
1939 struct df_link
*from_ref
)
1943 df_chain_create (to_ref
, from_ref
->ref
);
1944 from_ref
= from_ref
->next
;
1949 /* Remove this problem from the stack of dataflow problems. */
1952 df_chain_remove_problem (void)
1955 unsigned int bb_index
;
1957 /* Wholesale destruction of the old chains. */
1958 if (df_chain
->block_pool
)
1959 delete df_chain
->block_pool
;
1961 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1965 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
1967 if (df_chain_problem_p (DF_DU_CHAIN
))
1968 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
1969 DF_REF_CHAIN (def
) = NULL
;
1970 if (df_chain_problem_p (DF_UD_CHAIN
))
1971 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
1972 DF_REF_CHAIN (use
) = NULL
;
1974 FOR_BB_INSNS (bb
, insn
)
1977 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
1978 if (df_chain_problem_p (DF_DU_CHAIN
))
1979 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1980 DF_REF_CHAIN (def
) = NULL
;
1981 if (df_chain_problem_p (DF_UD_CHAIN
))
1983 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
1984 DF_REF_CHAIN (use
) = NULL
;
1985 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
1986 DF_REF_CHAIN (use
) = NULL
;
1991 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
1992 df_chain
->block_pool
= NULL
;
1996 /* Remove the chain problem completely. */
1999 df_chain_fully_remove_problem (void)
2001 df_chain_remove_problem ();
2002 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2007 /* Create def-use or use-def chains. */
2010 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2012 df_chain_remove_problem ();
2013 df_chain
->block_pool
= new pool_allocator
<df_link
> ("df_chain_block pool",
2015 df_chain
->optional_p
= true;
2019 /* Reset all of the chains when the set of basic blocks changes. */
2022 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2024 df_chain_remove_problem ();
2028 /* Create the chains for a list of USEs. */
2031 df_chain_create_bb_process_use (bitmap local_rd
,
2036 unsigned int def_index
;
2038 for (; use
; use
= DF_REF_NEXT_LOC (use
))
2040 unsigned int uregno
= DF_REF_REGNO (use
);
2041 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2042 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2044 /* Do not want to go through this for an uninitialized var. */
2045 int count
= DF_DEFS_COUNT (uregno
);
2048 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2050 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2051 unsigned int last_index
= first_index
+ count
- 1;
2053 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2056 if (def_index
> last_index
)
2059 def
= DF_DEFS_GET (def_index
);
2060 if (df_chain_problem_p (DF_DU_CHAIN
))
2061 df_chain_create (def
, use
);
2062 if (df_chain_problem_p (DF_UD_CHAIN
))
2063 df_chain_create (use
, def
);
2072 /* Create chains from reaching defs bitmaps for basic block BB. */
2075 df_chain_create_bb (unsigned int bb_index
)
2077 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
2078 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2082 bitmap_initialize (&cpy
, &bitmap_default_obstack
);
2083 bitmap_copy (&cpy
, &bb_info
->in
);
2084 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2086 /* Since we are going forwards, process the artificial uses first
2087 then the artificial defs second. */
2090 /* Create the chains for the artificial uses from the EH_USES at the
2091 beginning of the block. */
2093 /* Artificials are only hard regs. */
2094 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2095 df_chain_create_bb_process_use (&cpy
,
2096 df_get_artificial_uses (bb
->index
),
2100 df_rd_simulate_artificial_defs_at_top (bb
, &cpy
);
2102 /* Process the regular instructions next. */
2103 FOR_BB_INSNS (bb
, insn
)
2106 unsigned int uid
= INSN_UID (insn
);
2108 /* First scan the uses and link them up with the defs that remain
2109 in the cpy vector. */
2110 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_USES (uid
), 0);
2111 if (df
->changeable_flags
& DF_EQ_NOTES
)
2112 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2114 /* Since we are going forwards, process the defs second. */
2115 df_rd_simulate_one_insn (bb
, insn
, &cpy
);
2118 /* Create the chains for the artificial uses of the hard registers
2119 at the end of the block. */
2120 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2121 df_chain_create_bb_process_use (&cpy
,
2122 df_get_artificial_uses (bb
->index
),
2125 bitmap_clear (&cpy
);
2128 /* Create def-use chains from reaching use bitmaps for basic blocks
2132 df_chain_finalize (bitmap all_blocks
)
2134 unsigned int bb_index
;
2137 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2139 df_chain_create_bb (bb_index
);
2144 /* Free all storage associated with the problem. */
2147 df_chain_free (void)
2149 delete df_chain
->block_pool
;
2150 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2155 /* Debugging info. */
2158 df_chain_bb_dump (basic_block bb
, FILE *file
, bool top
)
2160 /* Artificials are only hard regs. */
2161 if (df
->changeable_flags
& DF_NO_HARD_REGS
)
2163 if (df_chain_problem_p (DF_UD_CHAIN
))
2168 ";; UD chains for artificial uses at %s\n",
2169 top
? "top" : "bottom");
2170 FOR_EACH_ARTIFICIAL_USE (use
, bb
->index
)
2171 if ((top
&& (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2172 || (!top
&& !(DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)))
2174 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2175 df_chain_dump (DF_REF_CHAIN (use
), file
);
2176 fprintf (file
, "\n");
2179 if (df_chain_problem_p (DF_DU_CHAIN
))
2184 ";; DU chains for artificial defs at %s\n",
2185 top
? "top" : "bottom");
2186 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
2187 if ((top
&& (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
2188 || (!top
&& !(DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)))
2190 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2191 df_chain_dump (DF_REF_CHAIN (def
), file
);
2192 fprintf (file
, "\n");
2198 df_chain_top_dump (basic_block bb
, FILE *file
)
2200 df_chain_bb_dump (bb
, file
, /*top=*/true);
2204 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2206 df_chain_bb_dump (bb
, file
, /*top=*/false);
2210 df_chain_insn_top_dump (const rtx_insn
*insn
, FILE *file
)
2212 if (df_chain_problem_p (DF_UD_CHAIN
) && INSN_P (insn
))
2214 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2217 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2218 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2219 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2220 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use
))
2221 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2223 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2224 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
2225 fprintf (file
, "read/write ");
2226 df_chain_dump (DF_REF_CHAIN (use
), file
);
2227 fprintf (file
, "\n");
2229 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
2230 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use
))
2231 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2233 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2234 df_chain_dump (DF_REF_CHAIN (use
), file
);
2235 fprintf (file
, "\n");
2241 df_chain_insn_bottom_dump (const rtx_insn
*insn
, FILE *file
)
2243 if (df_chain_problem_p (DF_DU_CHAIN
) && INSN_P (insn
))
2245 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2247 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2248 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2249 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2250 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def
))
2251 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2253 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2254 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
2255 fprintf (file
, "read/write ");
2256 df_chain_dump (DF_REF_CHAIN (def
), file
);
2257 fprintf (file
, "\n");
2259 fprintf (file
, "\n");
2263 static struct df_problem problem_CHAIN
=
2265 DF_CHAIN
, /* Problem id. */
2266 DF_NONE
, /* Direction. */
2267 df_chain_alloc
, /* Allocate the problem specific data. */
2268 df_chain_reset
, /* Reset global information. */
2269 NULL
, /* Free basic block info. */
2270 NULL
, /* Local compute function. */
2271 NULL
, /* Init the solution specific data. */
2272 NULL
, /* Iterative solver. */
2273 NULL
, /* Confluence operator 0. */
2274 NULL
, /* Confluence operator n. */
2275 NULL
, /* Transfer function. */
2276 df_chain_finalize
, /* Finalize function. */
2277 df_chain_free
, /* Free all of the problem information. */
2278 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2279 NULL
, /* Debugging. */
2280 df_chain_top_dump
, /* Debugging start block. */
2281 df_chain_bottom_dump
, /* Debugging end block. */
2282 df_chain_insn_top_dump
, /* Debugging start insn. */
2283 df_chain_insn_bottom_dump
, /* Debugging end insn. */
2284 NULL
, /* Incremental solution verify start. */
2285 NULL
, /* Incremental solution verify end. */
2286 &problem_RD
, /* Dependent problem. */
2287 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
2288 TV_DF_CHAIN
, /* Timing variable. */
2289 false /* Reset blocks on dropping out of blocks_to_analyze. */
2293 /* Create a new DATAFLOW instance and add it to an existing instance
2294 of DF. The returned structure is what is used to get at the
2298 df_chain_add_problem (unsigned int chain_flags
)
2300 df_add_problem (&problem_CHAIN
);
2301 df_chain
->local_flags
= chain_flags
;
2302 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
2305 #undef df_chain_problem_p
2308 /*----------------------------------------------------------------------------
2309 WORD LEVEL LIVE REGISTERS
2311 Find the locations in the function where any use of a pseudo can
2312 reach in the backwards direction. In and out bitvectors are built
2313 for each basic block. We only track pseudo registers that have a
2314 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2315 contain two bits corresponding to each of the subwords.
2317 ----------------------------------------------------------------------------*/
2319 /* Private data used to verify the solution for this problem. */
2320 struct df_word_lr_problem_data
2322 /* An obstack for the bitmaps we need for this problem. */
2323 bitmap_obstack word_lr_bitmaps
;
2327 /* Free basic block info. */
2330 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2333 struct df_word_lr_bb_info
*bb_info
= (struct df_word_lr_bb_info
*) vbb_info
;
2336 bitmap_clear (&bb_info
->use
);
2337 bitmap_clear (&bb_info
->def
);
2338 bitmap_clear (&bb_info
->in
);
2339 bitmap_clear (&bb_info
->out
);
2344 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2345 not touched unless the block is new. */
2348 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2350 unsigned int bb_index
;
2353 struct df_word_lr_problem_data
*problem_data
2354 = XNEW (struct df_word_lr_problem_data
);
2356 df_word_lr
->problem_data
= problem_data
;
2358 df_grow_bb_info (df_word_lr
);
2360 /* Create the mapping from regnos to slots. This does not change
2361 unless the problem is destroyed and recreated. In particular, if
2362 we end up deleting the only insn that used a subreg, we do not
2363 want to redo the mapping because this would invalidate everything
2366 bitmap_obstack_initialize (&problem_data
->word_lr_bitmaps
);
2368 FOR_EACH_BB_FN (bb
, cfun
)
2369 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, bb
->index
);
2371 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
2372 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, EXIT_BLOCK
);
2374 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2376 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2378 /* When bitmaps are already initialized, just clear them. */
2379 if (bb_info
->use
.obstack
)
2381 bitmap_clear (&bb_info
->def
);
2382 bitmap_clear (&bb_info
->use
);
2386 bitmap_initialize (&bb_info
->use
, &problem_data
->word_lr_bitmaps
);
2387 bitmap_initialize (&bb_info
->def
, &problem_data
->word_lr_bitmaps
);
2388 bitmap_initialize (&bb_info
->in
, &problem_data
->word_lr_bitmaps
);
2389 bitmap_initialize (&bb_info
->out
, &problem_data
->word_lr_bitmaps
);
2393 df_word_lr
->optional_p
= true;
2397 /* Reset the global solution for recalculation. */
2400 df_word_lr_reset (bitmap all_blocks
)
2402 unsigned int bb_index
;
2405 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2407 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2408 gcc_assert (bb_info
);
2409 bitmap_clear (&bb_info
->in
);
2410 bitmap_clear (&bb_info
->out
);
2414 /* Examine REF, and if it is for a reg we're interested in, set or
2415 clear the bits corresponding to its subwords from the bitmap
2416 according to IS_SET. LIVE is the bitmap we should update. We do
2417 not track hard regs or pseudos of any size other than 2 *
2419 We return true if we changed the bitmap, or if we encountered a register
2420 we're not tracking. */
2423 df_word_lr_mark_ref (df_ref ref
, bool is_set
, regset live
)
2425 rtx orig_reg
= DF_REF_REG (ref
);
2427 machine_mode reg_mode
;
2429 /* Left at -1 for whole accesses. */
2430 int which_subword
= -1;
2431 bool changed
= false;
2433 if (GET_CODE (reg
) == SUBREG
)
2434 reg
= SUBREG_REG (orig_reg
);
2435 regno
= REGNO (reg
);
2436 reg_mode
= GET_MODE (reg
);
2437 if (regno
< FIRST_PSEUDO_REGISTER
2438 || GET_MODE_SIZE (reg_mode
) != 2 * UNITS_PER_WORD
)
2441 if (GET_CODE (orig_reg
) == SUBREG
2442 && df_read_modify_subreg_p (orig_reg
))
2444 gcc_assert (DF_REF_FLAGS_IS_SET (ref
, DF_REF_PARTIAL
));
2445 if (subreg_lowpart_p (orig_reg
))
2452 if (which_subword
!= 1)
2453 changed
|= bitmap_set_bit (live
, regno
* 2);
2454 if (which_subword
!= 0)
2455 changed
|= bitmap_set_bit (live
, regno
* 2 + 1);
2459 if (which_subword
!= 1)
2460 changed
|= bitmap_clear_bit (live
, regno
* 2);
2461 if (which_subword
!= 0)
2462 changed
|= bitmap_clear_bit (live
, regno
* 2 + 1);
2467 /* Compute local live register info for basic block BB. */
2470 df_word_lr_bb_local_compute (unsigned int bb_index
)
2472 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
2473 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2477 /* Ensure that artificial refs don't contain references to pseudos. */
2478 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
2479 gcc_assert (DF_REF_REGNO (def
) < FIRST_PSEUDO_REGISTER
);
2481 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
2482 gcc_assert (DF_REF_REGNO (use
) < FIRST_PSEUDO_REGISTER
);
2484 FOR_BB_INSNS_REVERSE (bb
, insn
)
2486 if (!NONDEBUG_INSN_P (insn
))
2489 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2490 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2491 /* If the def is to only part of the reg, it does
2492 not kill the other defs that reach here. */
2493 if (!(DF_REF_FLAGS (def
) & (DF_REF_CONDITIONAL
)))
2495 df_word_lr_mark_ref (def
, true, &bb_info
->def
);
2496 df_word_lr_mark_ref (def
, false, &bb_info
->use
);
2498 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2499 df_word_lr_mark_ref (use
, true, &bb_info
->use
);
2504 /* Compute local live register info for each basic block within BLOCKS. */
2507 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2509 unsigned int bb_index
;
2512 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2514 if (bb_index
== EXIT_BLOCK
)
2518 EXECUTE_IF_SET_IN_BITMAP (df
->exit_block_uses
, FIRST_PSEUDO_REGISTER
,
2523 df_word_lr_bb_local_compute (bb_index
);
2526 bitmap_clear (df_word_lr
->out_of_date_transfer_functions
);
2530 /* Initialize the solution vectors. */
2533 df_word_lr_init (bitmap all_blocks
)
2535 unsigned int bb_index
;
2538 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2540 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2541 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
2542 bitmap_clear (&bb_info
->out
);
2547 /* Confluence function that ignores fake edges. */
2550 df_word_lr_confluence_n (edge e
)
2552 bitmap op1
= &df_word_lr_get_bb_info (e
->src
->index
)->out
;
2553 bitmap op2
= &df_word_lr_get_bb_info (e
->dest
->index
)->in
;
2555 return bitmap_ior_into (op1
, op2
);
2559 /* Transfer function. */
2562 df_word_lr_transfer_function (int bb_index
)
2564 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2565 bitmap in
= &bb_info
->in
;
2566 bitmap out
= &bb_info
->out
;
2567 bitmap use
= &bb_info
->use
;
2568 bitmap def
= &bb_info
->def
;
2570 return bitmap_ior_and_compl (in
, use
, out
, def
);
2574 /* Free all storage associated with the problem. */
2577 df_word_lr_free (void)
2579 struct df_word_lr_problem_data
*problem_data
2580 = (struct df_word_lr_problem_data
*)df_word_lr
->problem_data
;
2582 if (df_word_lr
->block_info
)
2584 df_word_lr
->block_info_size
= 0;
2585 free (df_word_lr
->block_info
);
2586 df_word_lr
->block_info
= NULL
;
2589 BITMAP_FREE (df_word_lr
->out_of_date_transfer_functions
);
2590 bitmap_obstack_release (&problem_data
->word_lr_bitmaps
);
2591 free (problem_data
);
2596 /* Debugging info at top of bb. */
2599 df_word_lr_top_dump (basic_block bb
, FILE *file
)
2601 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2605 fprintf (file
, ";; blr in \t");
2606 df_print_word_regset (file
, &bb_info
->in
);
2607 fprintf (file
, ";; blr use \t");
2608 df_print_word_regset (file
, &bb_info
->use
);
2609 fprintf (file
, ";; blr def \t");
2610 df_print_word_regset (file
, &bb_info
->def
);
2614 /* Debugging info at bottom of bb. */
2617 df_word_lr_bottom_dump (basic_block bb
, FILE *file
)
2619 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2623 fprintf (file
, ";; blr out \t");
2624 df_print_word_regset (file
, &bb_info
->out
);
2628 /* All of the information associated with every instance of the problem. */
2630 static struct df_problem problem_WORD_LR
=
2632 DF_WORD_LR
, /* Problem id. */
2633 DF_BACKWARD
, /* Direction. */
2634 df_word_lr_alloc
, /* Allocate the problem specific data. */
2635 df_word_lr_reset
, /* Reset global information. */
2636 df_word_lr_free_bb_info
, /* Free basic block info. */
2637 df_word_lr_local_compute
, /* Local compute function. */
2638 df_word_lr_init
, /* Init the solution specific data. */
2639 df_worklist_dataflow
, /* Worklist solver. */
2640 NULL
, /* Confluence operator 0. */
2641 df_word_lr_confluence_n
, /* Confluence operator n. */
2642 df_word_lr_transfer_function
, /* Transfer function. */
2643 NULL
, /* Finalize function. */
2644 df_word_lr_free
, /* Free all of the problem information. */
2645 df_word_lr_free
, /* Remove this problem from the stack of dataflow problems. */
2646 NULL
, /* Debugging. */
2647 df_word_lr_top_dump
, /* Debugging start block. */
2648 df_word_lr_bottom_dump
, /* Debugging end block. */
2649 NULL
, /* Debugging start insn. */
2650 NULL
, /* Debugging end insn. */
2651 NULL
, /* Incremental solution verify start. */
2652 NULL
, /* Incremental solution verify end. */
2653 NULL
, /* Dependent problem. */
2654 sizeof (struct df_word_lr_bb_info
),/* Size of entry of block_info array. */
2655 TV_DF_WORD_LR
, /* Timing variable. */
2656 false /* Reset blocks on dropping out of blocks_to_analyze. */
2660 /* Create a new DATAFLOW instance and add it to an existing instance
2661 of DF. The returned structure is what is used to get at the
2665 df_word_lr_add_problem (void)
2667 df_add_problem (&problem_WORD_LR
);
2668 /* These will be initialized when df_scan_blocks processes each
2670 df_word_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
2674 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
2675 any bits, which is used by the caller to determine whether a set is
2676 necessary. We also return true if there are other reasons not to delete
2680 df_word_lr_simulate_defs (rtx_insn
*insn
, bitmap live
)
2682 bool changed
= false;
2685 FOR_EACH_INSN_DEF (def
, insn
)
2686 if (DF_REF_FLAGS (def
) & DF_REF_CONDITIONAL
)
2689 changed
|= df_word_lr_mark_ref (def
, false, live
);
2694 /* Simulate the effects of the uses of INSN on LIVE. */
2697 df_word_lr_simulate_uses (rtx_insn
*insn
, bitmap live
)
2701 FOR_EACH_INSN_USE (use
, insn
)
2702 df_word_lr_mark_ref (use
, true, live
);
2705 /*----------------------------------------------------------------------------
2706 This problem computes REG_DEAD and REG_UNUSED notes.
2707 ----------------------------------------------------------------------------*/
2710 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2712 df_note
->optional_p
= true;
2715 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
2717 df_print_note (const char *prefix
, rtx_insn
*insn
, rtx note
)
2721 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
2722 print_rtl (dump_file
, note
);
2723 fprintf (dump_file
, "\n");
2728 /* After reg-stack, the x86 floating point stack regs are difficult to
2729 analyze because of all of the pushes, pops and rotations. Thus, we
2730 just leave the notes alone. */
2734 df_ignore_stack_reg (int regno
)
2736 return regstack_completed
2737 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
2741 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
2748 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
2751 df_remove_dead_and_unused_notes (rtx_insn
*insn
)
2753 rtx
*pprev
= ®_NOTES (insn
);
2758 switch (REG_NOTE_KIND (link
))
2761 /* After reg-stack, we need to ignore any unused notes
2762 for the stack registers. */
2763 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2765 pprev
= &XEXP (link
, 1);
2770 rtx next
= XEXP (link
, 1);
2771 if (REG_DEAD_DEBUGGING
)
2772 df_print_note ("deleting: ", insn
, link
);
2773 free_EXPR_LIST_node (link
);
2774 *pprev
= link
= next
;
2779 /* After reg-stack, we need to ignore any unused notes
2780 for the stack registers. */
2781 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2783 pprev
= &XEXP (link
, 1);
2788 rtx next
= XEXP (link
, 1);
2789 if (REG_DEAD_DEBUGGING
)
2790 df_print_note ("deleting: ", insn
, link
);
2791 free_EXPR_LIST_node (link
);
2792 *pprev
= link
= next
;
2797 pprev
= &XEXP (link
, 1);
2804 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2805 as the bitmap of currently live registers. */
2808 df_remove_dead_eq_notes (rtx_insn
*insn
, bitmap live
)
2810 rtx
*pprev
= ®_NOTES (insn
);
2815 switch (REG_NOTE_KIND (link
))
2820 /* Remove the notes that refer to dead registers. As we have at most
2821 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2822 so we need to purge the complete EQ_USES vector when removing
2823 the note using df_notes_rescan. */
2825 bool deleted
= false;
2827 FOR_EACH_INSN_EQ_USE (use
, insn
)
2828 if (DF_REF_REGNO (use
) > FIRST_PSEUDO_REGISTER
2830 && (DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
)
2831 && !bitmap_bit_p (live
, DF_REF_REGNO (use
))
2832 && loc_mentioned_in_p (DF_REF_LOC (use
), XEXP (link
, 0)))
2840 if (REG_DEAD_DEBUGGING
)
2841 df_print_note ("deleting: ", insn
, link
);
2842 next
= XEXP (link
, 1);
2843 free_EXPR_LIST_node (link
);
2844 *pprev
= link
= next
;
2845 df_notes_rescan (insn
);
2849 pprev
= &XEXP (link
, 1);
2856 pprev
= &XEXP (link
, 1);
2863 /* Set a NOTE_TYPE note for REG in INSN. */
2866 df_set_note (enum reg_note note_type
, rtx_insn
*insn
, rtx reg
)
2868 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2869 add_reg_note (insn
, note_type
, reg
);
2872 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2873 arguments. Return true if the register value described by MWS's
2874 mw_reg is known to be completely unused, and if mw_reg can therefore
2875 be used in a REG_UNUSED note. */
2878 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
2879 bitmap live
, bitmap artificial_uses
)
2883 /* If MWS describes a partial reference, create REG_UNUSED notes for
2884 individual hard registers. */
2885 if (mws
->flags
& DF_REF_PARTIAL
)
2888 /* Likewise if some part of the register is used. */
2889 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2890 if (bitmap_bit_p (live
, r
)
2891 || bitmap_bit_p (artificial_uses
, r
))
2894 gcc_assert (REG_P (mws
->mw_reg
));
2899 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2900 based on the bits in LIVE. Do not generate notes for registers in
2901 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
2902 not generated if the reg is both read and written by the
2907 df_set_unused_notes_for_mw (rtx_insn
*insn
, struct df_mw_hardreg
*mws
,
2908 bitmap live
, bitmap do_not_gen
,
2909 bitmap artificial_uses
,
2910 struct dead_debug_local
*debug
)
2914 if (REG_DEAD_DEBUGGING
&& dump_file
)
2915 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
2916 mws
->start_regno
, mws
->end_regno
);
2918 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
2920 unsigned int regno
= mws
->start_regno
;
2921 df_set_note (REG_UNUSED
, insn
, mws
->mw_reg
);
2922 dead_debug_insert_temp (debug
, regno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
2924 if (REG_DEAD_DEBUGGING
)
2925 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
2927 bitmap_set_bit (do_not_gen
, regno
);
2928 /* Only do this if the value is totally dead. */
2931 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2933 if (!bitmap_bit_p (live
, r
)
2934 && !bitmap_bit_p (artificial_uses
, r
))
2936 df_set_note (REG_UNUSED
, insn
, regno_reg_rtx
[r
]);
2937 dead_debug_insert_temp (debug
, r
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
2938 if (REG_DEAD_DEBUGGING
)
2939 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
2941 bitmap_set_bit (do_not_gen
, r
);
2946 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2947 arguments. Return true if the register value described by MWS's
2948 mw_reg is known to be completely dead, and if mw_reg can therefore
2949 be used in a REG_DEAD note. */
2952 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
2953 bitmap live
, bitmap artificial_uses
,
2958 /* If MWS describes a partial reference, create REG_DEAD notes for
2959 individual hard registers. */
2960 if (mws
->flags
& DF_REF_PARTIAL
)
2963 /* Likewise if some part of the register is not dead. */
2964 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2965 if (bitmap_bit_p (live
, r
)
2966 || bitmap_bit_p (artificial_uses
, r
)
2967 || bitmap_bit_p (do_not_gen
, r
))
2970 gcc_assert (REG_P (mws
->mw_reg
));
2974 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2975 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
2976 from being set if the instruction both reads and writes the
2980 df_set_dead_notes_for_mw (rtx_insn
*insn
, struct df_mw_hardreg
*mws
,
2981 bitmap live
, bitmap do_not_gen
,
2982 bitmap artificial_uses
, bool *added_notes_p
)
2985 bool is_debug
= *added_notes_p
;
2987 *added_notes_p
= false;
2989 if (REG_DEAD_DEBUGGING
&& dump_file
)
2991 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
2992 mws
->start_regno
, mws
->end_regno
);
2993 df_print_regset (dump_file
, do_not_gen
);
2994 fprintf (dump_file
, " live =");
2995 df_print_regset (dump_file
, live
);
2996 fprintf (dump_file
, " artificial uses =");
2997 df_print_regset (dump_file
, artificial_uses
);
3000 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3004 *added_notes_p
= true;
3007 /* Add a dead note for the entire multi word register. */
3008 df_set_note (REG_DEAD
, insn
, mws
->mw_reg
);
3009 if (REG_DEAD_DEBUGGING
)
3010 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3014 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3015 if (!bitmap_bit_p (live
, r
)
3016 && !bitmap_bit_p (artificial_uses
, r
)
3017 && !bitmap_bit_p (do_not_gen
, r
))
3021 *added_notes_p
= true;
3024 df_set_note (REG_DEAD
, insn
, regno_reg_rtx
[r
]);
3025 if (REG_DEAD_DEBUGGING
)
3026 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3033 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3034 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3037 df_create_unused_note (rtx_insn
*insn
, df_ref def
,
3038 bitmap live
, bitmap artificial_uses
,
3039 struct dead_debug_local
*debug
)
3041 unsigned int dregno
= DF_REF_REGNO (def
);
3043 if (REG_DEAD_DEBUGGING
&& dump_file
)
3045 fprintf (dump_file
, " regular looking at def ");
3046 df_ref_debug (def
, dump_file
);
3049 if (!((DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3050 || bitmap_bit_p (live
, dregno
)
3051 || bitmap_bit_p (artificial_uses
, dregno
)
3052 || df_ignore_stack_reg (dregno
)))
3054 rtx reg
= (DF_REF_LOC (def
))
3055 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3056 df_set_note (REG_UNUSED
, insn
, reg
);
3057 dead_debug_insert_temp (debug
, dregno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
3058 if (REG_DEAD_DEBUGGING
)
3059 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3066 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3067 info: lifetime, bb, and number of defs and uses for basic block
3068 BB. The three bitvectors are scratch regs used here. */
3071 df_note_bb_compute (unsigned int bb_index
,
3072 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3074 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
3077 struct dead_debug_local debug
;
3079 dead_debug_local_init (&debug
, NULL
, NULL
);
3081 bitmap_copy (live
, df_get_live_out (bb
));
3082 bitmap_clear (artificial_uses
);
3084 if (REG_DEAD_DEBUGGING
&& dump_file
)
3086 fprintf (dump_file
, "live at bottom ");
3087 df_print_regset (dump_file
, live
);
3090 /* Process the artificial defs and uses at the bottom of the block
3091 to begin processing. */
3092 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3094 if (REG_DEAD_DEBUGGING
&& dump_file
)
3095 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3097 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3098 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3101 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
3102 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3104 unsigned int regno
= DF_REF_REGNO (use
);
3105 bitmap_set_bit (live
, regno
);
3107 /* Notes are not generated for any of the artificial registers
3108 at the bottom of the block. */
3109 bitmap_set_bit (artificial_uses
, regno
);
3112 if (REG_DEAD_DEBUGGING
&& dump_file
)
3114 fprintf (dump_file
, "live before artificials out ");
3115 df_print_regset (dump_file
, live
);
3118 FOR_BB_INSNS_REVERSE (bb
, insn
)
3120 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
3127 debug_insn
= DEBUG_INSN_P (insn
);
3129 bitmap_clear (do_not_gen
);
3130 df_remove_dead_and_unused_notes (insn
);
3132 /* Process the defs. */
3135 if (REG_DEAD_DEBUGGING
&& dump_file
)
3137 fprintf (dump_file
, "processing call %d\n live =",
3139 df_print_regset (dump_file
, live
);
3142 /* We only care about real sets for calls. Clobbers cannot
3143 be depended on to really die. */
3144 FOR_EACH_INSN_INFO_MW (mw
, insn_info
)
3145 if ((DF_MWS_REG_DEF_P (mw
))
3146 && !df_ignore_stack_reg (mw
->start_regno
))
3147 df_set_unused_notes_for_mw (insn
, mw
, live
, do_not_gen
,
3148 artificial_uses
, &debug
);
3150 /* All of the defs except the return value are some sort of
3151 clobber. This code is for the return. */
3152 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
3154 unsigned int dregno
= DF_REF_REGNO (def
);
3155 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3157 df_create_unused_note (insn
,
3158 def
, live
, artificial_uses
, &debug
);
3159 bitmap_set_bit (do_not_gen
, dregno
);
3162 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3163 bitmap_clear_bit (live
, dregno
);
3169 FOR_EACH_INSN_INFO_MW (mw
, insn_info
)
3170 if (DF_MWS_REG_DEF_P (mw
))
3171 df_set_unused_notes_for_mw (insn
, mw
, live
, do_not_gen
,
3172 artificial_uses
, &debug
);
3174 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
3176 unsigned int dregno
= DF_REF_REGNO (def
);
3177 df_create_unused_note (insn
,
3178 def
, live
, artificial_uses
, &debug
);
3180 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3181 bitmap_set_bit (do_not_gen
, dregno
);
3183 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3184 bitmap_clear_bit (live
, dregno
);
3188 /* Process the uses. */
3189 FOR_EACH_INSN_INFO_MW (mw
, insn_info
)
3190 if (DF_MWS_REG_USE_P (mw
)
3191 && !df_ignore_stack_reg (mw
->start_regno
))
3193 bool really_add_notes
= debug_insn
!= 0;
3195 df_set_dead_notes_for_mw (insn
, mw
, live
, do_not_gen
,
3199 if (really_add_notes
)
3203 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
3205 unsigned int uregno
= DF_REF_REGNO (use
);
3207 if (REG_DEAD_DEBUGGING
&& dump_file
&& !debug_insn
)
3209 fprintf (dump_file
, " regular looking at use ");
3210 df_ref_debug (use
, dump_file
);
3213 if (!bitmap_bit_p (live
, uregno
))
3219 /* We won't add REG_UNUSED or REG_DEAD notes for
3220 these, so we don't have to mess with them in
3221 debug insns either. */
3222 if (!bitmap_bit_p (artificial_uses
, uregno
)
3223 && !df_ignore_stack_reg (uregno
))
3224 dead_debug_add (&debug
, use
, uregno
);
3230 dead_debug_insert_temp (&debug
, uregno
, insn
,
3231 DEBUG_TEMP_BEFORE_WITH_REG
);
3233 if ( (!(DF_REF_FLAGS (use
)
3234 & (DF_REF_MW_HARDREG
| DF_REF_READ_WRITE
)))
3235 && (!bitmap_bit_p (do_not_gen
, uregno
))
3236 && (!bitmap_bit_p (artificial_uses
, uregno
))
3237 && (!df_ignore_stack_reg (uregno
)))
3239 rtx reg
= (DF_REF_LOC (use
))
3240 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3241 df_set_note (REG_DEAD
, insn
, reg
);
3243 if (REG_DEAD_DEBUGGING
)
3244 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3246 /* This register is now live. */
3247 bitmap_set_bit (live
, uregno
);
3251 df_remove_dead_eq_notes (insn
, live
);
3253 if (debug_insn
== -1)
3255 /* ??? We could probably do better here, replacing dead
3256 registers with their definitions. */
3257 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3258 df_insn_rescan_debug_internal (insn
);
3262 dead_debug_local_finish (&debug
, NULL
);
3266 /* Compute register info: lifetime, bb, and number of defs and uses. */
3268 df_note_compute (bitmap all_blocks
)
3270 unsigned int bb_index
;
3272 bitmap_head live
, do_not_gen
, artificial_uses
;
3274 bitmap_initialize (&live
, &df_bitmap_obstack
);
3275 bitmap_initialize (&do_not_gen
, &df_bitmap_obstack
);
3276 bitmap_initialize (&artificial_uses
, &df_bitmap_obstack
);
3278 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3280 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3281 pseudos in debug insns because we don't always (re)visit blocks
3282 with death points after visiting dead uses. Even changing this
3283 loop to postorder would still leave room for visiting a death
3284 point before visiting a subsequent debug use. */
3285 df_note_bb_compute (bb_index
, &live
, &do_not_gen
, &artificial_uses
);
3288 bitmap_clear (&live
);
3289 bitmap_clear (&do_not_gen
);
3290 bitmap_clear (&artificial_uses
);
3294 /* Free all storage associated with the problem. */
3303 /* All of the information associated every instance of the problem. */
3305 static struct df_problem problem_NOTE
=
3307 DF_NOTE
, /* Problem id. */
3308 DF_NONE
, /* Direction. */
3309 df_note_alloc
, /* Allocate the problem specific data. */
3310 NULL
, /* Reset global information. */
3311 NULL
, /* Free basic block info. */
3312 df_note_compute
, /* Local compute function. */
3313 NULL
, /* Init the solution specific data. */
3314 NULL
, /* Iterative solver. */
3315 NULL
, /* Confluence operator 0. */
3316 NULL
, /* Confluence operator n. */
3317 NULL
, /* Transfer function. */
3318 NULL
, /* Finalize function. */
3319 df_note_free
, /* Free all of the problem information. */
3320 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3321 NULL
, /* Debugging. */
3322 NULL
, /* Debugging start block. */
3323 NULL
, /* Debugging end block. */
3324 NULL
, /* Debugging start insn. */
3325 NULL
, /* Debugging end insn. */
3326 NULL
, /* Incremental solution verify start. */
3327 NULL
, /* Incremental solution verify end. */
3328 &problem_LR
, /* Dependent problem. */
3329 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
3330 TV_DF_NOTE
, /* Timing variable. */
3331 false /* Reset blocks on dropping out of blocks_to_analyze. */
3335 /* Create a new DATAFLOW instance and add it to an existing instance
3336 of DF. The returned structure is what is used to get at the
3340 df_note_add_problem (void)
3342 df_add_problem (&problem_NOTE
);
3348 /*----------------------------------------------------------------------------
3349 Functions for simulating the effects of single insns.
3351 You can either simulate in the forwards direction, starting from
3352 the top of a block or the backwards direction from the end of the
3353 block. If you go backwards, defs are examined first to clear bits,
3354 then uses are examined to set bits. If you go forwards, defs are
3355 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3356 are examined to clear bits. In either case, the result of examining
3357 a def can be undone (respectively by a use or a REG_UNUSED note).
3359 If you start at the top of the block, use one of DF_LIVE_IN or
3360 DF_LR_IN. If you start at the bottom of the block use one of
3361 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3362 THEY WILL BE DESTROYED.
3363 ----------------------------------------------------------------------------*/
3366 /* Find the set of DEFs for INSN. */
3369 df_simulate_find_defs (rtx_insn
*insn
, bitmap defs
)
3373 FOR_EACH_INSN_DEF (def
, insn
)
3374 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3377 /* Find the set of uses for INSN. This includes partial defs. */
3380 df_simulate_find_uses (rtx_insn
*insn
, bitmap uses
)
3383 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
3385 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
3386 if (DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3387 bitmap_set_bit (uses
, DF_REF_REGNO (def
));
3388 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
3389 bitmap_set_bit (uses
, DF_REF_REGNO (use
));
3392 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3395 df_simulate_find_noclobber_defs (rtx_insn
*insn
, bitmap defs
)
3399 FOR_EACH_INSN_DEF (def
, insn
)
3400 if (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
3401 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3405 /* Simulate the effects of the defs of INSN on LIVE. */
3408 df_simulate_defs (rtx_insn
*insn
, bitmap live
)
3412 FOR_EACH_INSN_DEF (def
, insn
)
3414 unsigned int dregno
= DF_REF_REGNO (def
);
3416 /* If the def is to only part of the reg, it does
3417 not kill the other defs that reach here. */
3418 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3419 bitmap_clear_bit (live
, dregno
);
3424 /* Simulate the effects of the uses of INSN on LIVE. */
3427 df_simulate_uses (rtx_insn
*insn
, bitmap live
)
3431 if (DEBUG_INSN_P (insn
))
3434 FOR_EACH_INSN_USE (use
, insn
)
3435 /* Add use to set of uses in this BB. */
3436 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3440 /* Add back the always live regs in BB to LIVE. */
3443 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3445 /* These regs are considered always live so if they end up dying
3446 because of some def, we need to bring the back again. */
3447 if (bb_has_eh_pred (bb
))
3448 bitmap_ior_into (live
, &df
->eh_block_artificial_uses
);
3450 bitmap_ior_into (live
, &df
->regular_block_artificial_uses
);
3454 /*----------------------------------------------------------------------------
3455 The following three functions are used only for BACKWARDS scanning:
3456 i.e. they process the defs before the uses.
3458 df_simulate_initialize_backwards should be called first with a
3459 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3460 df_simulate_one_insn_backwards should be called for each insn in
3461 the block, starting with the last one. Finally,
3462 df_simulate_finalize_backwards can be called to get a new value
3463 of the sets at the top of the block (this is rarely used).
3464 ----------------------------------------------------------------------------*/
3466 /* Apply the artificial uses and defs at the end of BB in a backwards
3470 df_simulate_initialize_backwards (basic_block bb
, bitmap live
)
3473 int bb_index
= bb
->index
;
3475 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3476 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3477 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3479 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
3480 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3481 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3485 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3488 df_simulate_one_insn_backwards (basic_block bb
, rtx_insn
*insn
, bitmap live
)
3490 if (!NONDEBUG_INSN_P (insn
))
3493 df_simulate_defs (insn
, live
);
3494 df_simulate_uses (insn
, live
);
3495 df_simulate_fixup_sets (bb
, live
);
3499 /* Apply the artificial uses and defs at the top of BB in a backwards
3503 df_simulate_finalize_backwards (basic_block bb
, bitmap live
)
3509 int bb_index
= bb
->index
;
3511 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3512 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3513 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3516 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
3517 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3518 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3521 /*----------------------------------------------------------------------------
3522 The following three functions are used only for FORWARDS scanning:
3523 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3524 Thus it is important to add the DF_NOTES problem to the stack of
3525 problems computed before using these functions.
3527 df_simulate_initialize_forwards should be called first with a
3528 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3529 df_simulate_one_insn_forwards should be called for each insn in
3530 the block, starting with the first one.
3531 ----------------------------------------------------------------------------*/
3533 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3534 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3538 df_simulate_initialize_forwards (basic_block bb
, bitmap live
)
3541 int bb_index
= bb
->index
;
3543 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3544 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3545 bitmap_set_bit (live
, DF_REF_REGNO (def
));
3548 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3551 df_simulate_one_insn_forwards (basic_block bb
, rtx_insn
*insn
, bitmap live
)
3554 if (! INSN_P (insn
))
3557 /* Make sure that DF_NOTE really is an active df problem. */
3558 gcc_assert (df_note
);
3560 /* Note that this is the opposite as how the problem is defined, because
3561 in the LR problem defs _kill_ liveness. However, they do so backwards,
3562 while here the scan is performed forwards! So, first assume that the
3563 def is live, and if this is not true REG_UNUSED notes will rectify the
3565 df_simulate_find_noclobber_defs (insn
, live
);
3567 /* Clear all of the registers that go dead. */
3568 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3570 switch (REG_NOTE_KIND (link
))
3575 rtx reg
= XEXP (link
, 0);
3576 bitmap_clear_range (live
, REGNO (reg
), REG_NREGS (reg
));
3583 df_simulate_fixup_sets (bb
, live
);
3586 /* Used by the next two functions to encode information about the
3587 memory references we found. */
3588 #define MEMREF_NORMAL 1
3589 #define MEMREF_VOLATILE 2
3591 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3594 find_memory (rtx_insn
*insn
)
3597 subrtx_iterator::array_type array
;
3598 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
3600 const_rtx x
= *iter
;
3601 if (GET_CODE (x
) == ASM_OPERANDS
&& MEM_VOLATILE_P (x
))
3602 flags
|= MEMREF_VOLATILE
;
3605 if (MEM_VOLATILE_P (x
))
3606 flags
|= MEMREF_VOLATILE
;
3607 else if (!MEM_READONLY_P (x
))
3608 flags
|= MEMREF_NORMAL
;
3614 /* A subroutine of can_move_insns_across_p called through note_stores.
3615 DATA points to an integer in which we set either the bit for
3616 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3620 find_memory_stores (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
,
3621 void *data ATTRIBUTE_UNUSED
)
3623 int *pflags
= (int *)data
;
3624 if (GET_CODE (x
) == SUBREG
)
3626 /* Treat stores to SP as stores to memory, this will prevent problems
3627 when there are references to the stack frame. */
3628 if (x
== stack_pointer_rtx
)
3629 *pflags
|= MEMREF_VOLATILE
;
3632 *pflags
|= MEM_VOLATILE_P (x
) ? MEMREF_VOLATILE
: MEMREF_NORMAL
;
3635 /* Scan BB backwards, using df_simulate functions to keep track of
3636 lifetimes, up to insn POINT. The result is stored in LIVE. */
3639 simulate_backwards_to_point (basic_block bb
, regset live
, rtx point
)
3642 bitmap_copy (live
, df_get_live_out (bb
));
3643 df_simulate_initialize_backwards (bb
, live
);
3645 /* Scan and update life information until we reach the point we're
3647 for (insn
= BB_END (bb
); insn
!= point
; insn
= PREV_INSN (insn
))
3648 df_simulate_one_insn_backwards (bb
, insn
, live
);
3651 /* Return true if it is safe to move a group of insns, described by
3652 the range FROM to TO, backwards across another group of insns,
3653 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
3654 are no insns between ACROSS_TO and FROM, but they may be in
3655 different basic blocks; MERGE_BB is the block from which the
3656 insns will be moved. The caller must pass in a regset MERGE_LIVE
3657 which specifies the registers live after TO.
3659 This function may be called in one of two cases: either we try to
3660 move identical instructions from all successor blocks into their
3661 predecessor, or we try to move from only one successor block. If
3662 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3663 the second case. It should contain a set of registers live at the
3664 end of ACROSS_TO which must not be clobbered by moving the insns.
3665 In that case, we're also more careful about moving memory references
3668 We return false if it is not safe to move the entire group, but it
3669 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
3670 is set to point at the last moveable insn in such a case. */
3673 can_move_insns_across (rtx_insn
*from
, rtx_insn
*to
,
3674 rtx_insn
*across_from
, rtx_insn
*across_to
,
3675 basic_block merge_bb
, regset merge_live
,
3676 regset other_branch_live
, rtx_insn
**pmove_upto
)
3678 rtx_insn
*insn
, *next
, *max_to
;
3679 bitmap merge_set
, merge_use
, local_merge_live
;
3680 bitmap test_set
, test_use
;
3681 unsigned i
, fail
= 0;
3683 int memrefs_in_across
= 0;
3684 int mem_sets_in_across
= 0;
3685 bool trapping_insns_in_across
= false;
3687 if (pmove_upto
!= NULL
)
3690 /* Find real bounds, ignoring debug insns. */
3691 while (!NONDEBUG_INSN_P (from
) && from
!= to
)
3692 from
= NEXT_INSN (from
);
3693 while (!NONDEBUG_INSN_P (to
) && from
!= to
)
3694 to
= PREV_INSN (to
);
3696 for (insn
= across_to
; ; insn
= next
)
3700 if (RTL_CONST_OR_PURE_CALL_P (insn
))
3701 /* Pure functions can read from memory. Const functions can
3702 read from arguments that the ABI has forced onto the stack.
3703 Neither sort of read can be volatile. */
3704 memrefs_in_across
|= MEMREF_NORMAL
;
3707 memrefs_in_across
|= MEMREF_VOLATILE
;
3708 mem_sets_in_across
|= MEMREF_VOLATILE
;
3711 if (NONDEBUG_INSN_P (insn
))
3713 if (volatile_insn_p (PATTERN (insn
)))
3715 memrefs_in_across
|= find_memory (insn
);
3716 note_stores (PATTERN (insn
), find_memory_stores
,
3717 &mem_sets_in_across
);
3718 /* This is used just to find sets of the stack pointer. */
3719 memrefs_in_across
|= mem_sets_in_across
;
3720 trapping_insns_in_across
|= may_trap_p (PATTERN (insn
));
3722 next
= PREV_INSN (insn
);
3723 if (insn
== across_from
)
3728 MERGE_SET = set of registers set in MERGE_BB
3729 MERGE_USE = set of registers used in MERGE_BB and live at its top
3730 MERGE_LIVE = set of registers live at the point inside the MERGE
3731 range that we've reached during scanning
3732 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3733 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3734 and live before ACROSS_FROM. */
3736 merge_set
= BITMAP_ALLOC (®_obstack
);
3737 merge_use
= BITMAP_ALLOC (®_obstack
);
3738 local_merge_live
= BITMAP_ALLOC (®_obstack
);
3739 test_set
= BITMAP_ALLOC (®_obstack
);
3740 test_use
= BITMAP_ALLOC (®_obstack
);
3742 /* Compute the set of registers set and used in the ACROSS range. */
3743 if (other_branch_live
!= NULL
)
3744 bitmap_copy (test_use
, other_branch_live
);
3745 df_simulate_initialize_backwards (merge_bb
, test_use
);
3746 for (insn
= across_to
; ; insn
= next
)
3748 if (NONDEBUG_INSN_P (insn
))
3750 df_simulate_find_defs (insn
, test_set
);
3751 df_simulate_defs (insn
, test_use
);
3752 df_simulate_uses (insn
, test_use
);
3754 next
= PREV_INSN (insn
);
3755 if (insn
== across_from
)
3759 /* Compute an upper bound for the amount of insns moved, by finding
3760 the first insn in MERGE that sets a register in TEST_USE, or uses
3761 a register in TEST_SET. We also check for calls, trapping operations,
3762 and memory references. */
3764 for (insn
= from
; ; insn
= next
)
3768 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3770 if (NONDEBUG_INSN_P (insn
))
3772 if (may_trap_or_fault_p (PATTERN (insn
))
3773 && (trapping_insns_in_across
3774 || other_branch_live
!= NULL
3775 || volatile_insn_p (PATTERN (insn
))))
3778 /* We cannot move memory stores past each other, or move memory
3779 reads past stores, at least not without tracking them and
3780 calling true_dependence on every pair.
3782 If there is no other branch and no memory references or
3783 sets in the ACROSS range, we can move memory references
3784 freely, even volatile ones.
3786 Otherwise, the rules are as follows: volatile memory
3787 references and stores can't be moved at all, and any type
3788 of memory reference can't be moved if there are volatile
3789 accesses or stores in the ACROSS range. That leaves
3790 normal reads, which can be moved, as the trapping case is
3791 dealt with elsewhere. */
3792 if (other_branch_live
!= NULL
|| memrefs_in_across
!= 0)
3794 int mem_ref_flags
= 0;
3795 int mem_set_flags
= 0;
3796 note_stores (PATTERN (insn
), find_memory_stores
, &mem_set_flags
);
3797 mem_ref_flags
= find_memory (insn
);
3798 /* Catch sets of the stack pointer. */
3799 mem_ref_flags
|= mem_set_flags
;
3801 if ((mem_ref_flags
| mem_set_flags
) & MEMREF_VOLATILE
)
3803 if ((memrefs_in_across
& MEMREF_VOLATILE
) && mem_ref_flags
!= 0)
3805 if (mem_set_flags
!= 0
3806 || (mem_sets_in_across
!= 0 && mem_ref_flags
!= 0))
3809 df_simulate_find_uses (insn
, merge_use
);
3810 /* We're only interested in uses which use a value live at
3811 the top, not one previously set in this block. */
3812 bitmap_and_compl_into (merge_use
, merge_set
);
3813 df_simulate_find_defs (insn
, merge_set
);
3814 if (bitmap_intersect_p (merge_set
, test_use
)
3815 || bitmap_intersect_p (merge_use
, test_set
))
3817 if (!HAVE_cc0
|| !sets_cc0_p (insn
))
3820 next
= NEXT_INSN (insn
);
3827 if (max_to
== NULL_RTX
|| (fail
&& pmove_upto
== NULL
))
3830 /* Now, lower this upper bound by also taking into account that
3831 a range of insns moved across ACROSS must not leave a register
3832 live at the end that will be clobbered in ACROSS. We need to
3833 find a point where TEST_SET & LIVE == 0.
3835 Insns in the MERGE range that set registers which are also set
3836 in the ACROSS range may still be moved as long as we also move
3837 later insns which use the results of the set, and make the
3838 register dead again. This is verified by the condition stated
3839 above. We only need to test it for registers that are set in
3842 MERGE_LIVE is provided by the caller and holds live registers after
3844 bitmap_copy (local_merge_live
, merge_live
);
3845 for (insn
= to
; insn
!= max_to
; insn
= PREV_INSN (insn
))
3846 df_simulate_one_insn_backwards (merge_bb
, insn
, local_merge_live
);
3848 /* We're not interested in registers that aren't set in the moved
3850 bitmap_and_into (local_merge_live
, merge_set
);
3853 if (NONDEBUG_INSN_P (insn
))
3855 if (!bitmap_intersect_p (test_set
, local_merge_live
)
3856 && (!HAVE_cc0
|| !sets_cc0_p (insn
)))
3862 df_simulate_one_insn_backwards (merge_bb
, insn
,
3870 insn
= PREV_INSN (insn
);
3877 *pmove_upto
= max_to
;
3879 /* For small register class machines, don't lengthen lifetimes of
3880 hard registers before reload. */
3881 if (! reload_completed
3882 && targetm
.small_register_classes_for_mode_p (VOIDmode
))
3884 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
3886 if (i
< FIRST_PSEUDO_REGISTER
3888 && ! global_regs
[i
])
3897 BITMAP_FREE (merge_set
);
3898 BITMAP_FREE (merge_use
);
3899 BITMAP_FREE (local_merge_live
);
3900 BITMAP_FREE (test_set
);
3901 BITMAP_FREE (test_use
);
3907 /*----------------------------------------------------------------------------
3908 MULTIPLE DEFINITIONS
3910 Find the locations in the function reached by multiple definition sites
3911 for a live pseudo. In and out bitvectors are built for each basic
3912 block. They are restricted for efficiency to live registers.
3914 The gen and kill sets for the problem are obvious. Together they
3915 include all defined registers in a basic block; the gen set includes
3916 registers where a partial or conditional or may-clobber definition is
3917 last in the BB, while the kill set includes registers with a complete
3918 definition coming last. However, the computation of the dataflow
3919 itself is interesting.
3921 The idea behind it comes from SSA form's iterated dominance frontier
3922 criterion for inserting PHI functions. Just like in that case, we can use
3923 the dominance frontier to find places where multiple definitions meet;
3924 a register X defined in a basic block BB1 has multiple definitions in
3925 basic blocks in BB1's dominance frontier.
3927 So, the in-set of a basic block BB2 is not just the union of the
3928 out-sets of BB2's predecessors, but includes some more bits that come
3929 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3930 the previous paragraph). I called this set the init-set of BB2.
3932 (Note: I actually use the kill-set only to build the init-set.
3933 gen bits are anyway propagated from BB1 to BB2 by dataflow).
3935 For example, if you have
3939 if <...> goto BB2 else goto BB3;
3947 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3948 init-set of BB3 includes r10 and r12, but not r11. Note that we do
3949 not need to iterate the dominance frontier, because we do not insert
3950 anything like PHI functions there! Instead, dataflow will take care of
3951 propagating the information to BB3's successors.
3952 ---------------------------------------------------------------------------*/
3954 /* Private data used to verify the solution for this problem. */
3955 struct df_md_problem_data
3957 /* An obstack for the bitmaps we need for this problem. */
3958 bitmap_obstack md_bitmaps
;
3961 /* Scratch var used by transfer functions. This is used to do md analysis
3962 only for live registers. */
3963 static bitmap_head df_md_scratch
;
3967 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
3970 struct df_md_bb_info
*bb_info
= (struct df_md_bb_info
*) vbb_info
;
3973 bitmap_clear (&bb_info
->kill
);
3974 bitmap_clear (&bb_info
->gen
);
3975 bitmap_clear (&bb_info
->init
);
3976 bitmap_clear (&bb_info
->in
);
3977 bitmap_clear (&bb_info
->out
);
3982 /* Allocate or reset bitmaps for DF_MD. The solution bits are
3983 not touched unless the block is new. */
3986 df_md_alloc (bitmap all_blocks
)
3988 unsigned int bb_index
;
3990 struct df_md_problem_data
*problem_data
;
3992 df_grow_bb_info (df_md
);
3993 if (df_md
->problem_data
)
3994 problem_data
= (struct df_md_problem_data
*) df_md
->problem_data
;
3997 problem_data
= XNEW (struct df_md_problem_data
);
3998 df_md
->problem_data
= problem_data
;
3999 bitmap_obstack_initialize (&problem_data
->md_bitmaps
);
4001 bitmap_initialize (&df_md_scratch
, &problem_data
->md_bitmaps
);
4003 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4005 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4006 /* When bitmaps are already initialized, just clear them. */
4007 if (bb_info
->init
.obstack
)
4009 bitmap_clear (&bb_info
->init
);
4010 bitmap_clear (&bb_info
->gen
);
4011 bitmap_clear (&bb_info
->kill
);
4012 bitmap_clear (&bb_info
->in
);
4013 bitmap_clear (&bb_info
->out
);
4017 bitmap_initialize (&bb_info
->init
, &problem_data
->md_bitmaps
);
4018 bitmap_initialize (&bb_info
->gen
, &problem_data
->md_bitmaps
);
4019 bitmap_initialize (&bb_info
->kill
, &problem_data
->md_bitmaps
);
4020 bitmap_initialize (&bb_info
->in
, &problem_data
->md_bitmaps
);
4021 bitmap_initialize (&bb_info
->out
, &problem_data
->md_bitmaps
);
4025 df_md
->optional_p
= true;
4028 /* Add the effect of the top artificial defs of BB to the multiple definitions
4032 df_md_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_md
)
4034 int bb_index
= bb
->index
;
4036 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
4037 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4039 unsigned int dregno
= DF_REF_REGNO (def
);
4040 if (DF_REF_FLAGS (def
)
4041 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4042 bitmap_set_bit (local_md
, dregno
);
4044 bitmap_clear_bit (local_md
, dregno
);
4049 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4053 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx_insn
*insn
,
4058 FOR_EACH_INSN_DEF (def
, insn
)
4060 unsigned int dregno
= DF_REF_REGNO (def
);
4061 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4062 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4064 if (DF_REF_FLAGS (def
)
4065 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4066 bitmap_set_bit (local_md
, DF_REF_ID (def
));
4068 bitmap_clear_bit (local_md
, DF_REF_ID (def
));
4074 df_md_bb_local_compute_process_def (struct df_md_bb_info
*bb_info
,
4078 bitmap_clear (&seen_in_insn
);
4080 for (; def
; def
= DF_REF_NEXT_LOC (def
))
4082 unsigned int dregno
= DF_REF_REGNO (def
);
4083 if (((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4084 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4085 && top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
4087 if (!bitmap_bit_p (&seen_in_insn
, dregno
))
4089 if (DF_REF_FLAGS (def
)
4090 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4092 bitmap_set_bit (&bb_info
->gen
, dregno
);
4093 bitmap_clear_bit (&bb_info
->kill
, dregno
);
4097 /* When we find a clobber and a regular def,
4098 make sure the regular def wins. */
4099 bitmap_set_bit (&seen_in_insn
, dregno
);
4100 bitmap_set_bit (&bb_info
->kill
, dregno
);
4101 bitmap_clear_bit (&bb_info
->gen
, dregno
);
4109 /* Compute local multiple def info for basic block BB. */
4112 df_md_bb_local_compute (unsigned int bb_index
)
4114 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
4115 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4118 /* Artificials are only hard regs. */
4119 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4120 df_md_bb_local_compute_process_def (bb_info
,
4121 df_get_artificial_defs (bb_index
),
4124 FOR_BB_INSNS (bb
, insn
)
4126 unsigned int uid
= INSN_UID (insn
);
4130 df_md_bb_local_compute_process_def (bb_info
, DF_INSN_UID_DEFS (uid
), 0);
4133 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4134 df_md_bb_local_compute_process_def (bb_info
,
4135 df_get_artificial_defs (bb_index
),
4139 /* Compute local reaching def info for each basic block within BLOCKS. */
4142 df_md_local_compute (bitmap all_blocks
)
4144 unsigned int bb_index
, df_bb_index
;
4145 bitmap_iterator bi1
, bi2
;
4147 bitmap_head
*frontiers
;
4149 bitmap_initialize (&seen_in_insn
, &bitmap_default_obstack
);
4151 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4153 df_md_bb_local_compute (bb_index
);
4156 bitmap_clear (&seen_in_insn
);
4158 frontiers
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
4159 FOR_ALL_BB_FN (bb
, cfun
)
4160 bitmap_initialize (&frontiers
[bb
->index
], &bitmap_default_obstack
);
4162 compute_dominance_frontiers (frontiers
);
4164 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4165 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4167 bitmap kill
= &df_md_get_bb_info (bb_index
)->kill
;
4168 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[bb_index
], 0, df_bb_index
, bi2
)
4170 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, df_bb_index
);
4171 if (bitmap_bit_p (all_blocks
, df_bb_index
))
4172 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index
)->init
, kill
,
4173 df_get_live_in (bb
));
4177 FOR_ALL_BB_FN (bb
, cfun
)
4178 bitmap_clear (&frontiers
[bb
->index
]);
4183 /* Reset the global solution for recalculation. */
4186 df_md_reset (bitmap all_blocks
)
4188 unsigned int bb_index
;
4191 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4193 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4194 gcc_assert (bb_info
);
4195 bitmap_clear (&bb_info
->in
);
4196 bitmap_clear (&bb_info
->out
);
4201 df_md_transfer_function (int bb_index
)
4203 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
4204 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4205 bitmap in
= &bb_info
->in
;
4206 bitmap out
= &bb_info
->out
;
4207 bitmap gen
= &bb_info
->gen
;
4208 bitmap kill
= &bb_info
->kill
;
4210 /* We need to use a scratch set here so that the value returned from this
4211 function invocation properly reflects whether the sets changed in a
4212 significant way; i.e. not just because the live set was anded in. */
4213 bitmap_and (&df_md_scratch
, gen
, df_get_live_out (bb
));
4215 /* Multiple definitions of a register are not relevant if it is not
4216 live. Thus we trim the result to the places where it is live. */
4217 bitmap_and_into (in
, df_get_live_in (bb
));
4219 return bitmap_ior_and_compl (out
, &df_md_scratch
, in
, kill
);
4222 /* Initialize the solution bit vectors for problem. */
4225 df_md_init (bitmap all_blocks
)
4227 unsigned int bb_index
;
4230 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4232 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4234 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4235 df_md_transfer_function (bb_index
);
4240 df_md_confluence_0 (basic_block bb
)
4242 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4243 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4246 /* In of target gets or of out of source. */
4249 df_md_confluence_n (edge e
)
4251 bitmap op1
= &df_md_get_bb_info (e
->dest
->index
)->in
;
4252 bitmap op2
= &df_md_get_bb_info (e
->src
->index
)->out
;
4254 if (e
->flags
& EDGE_FAKE
)
4257 if (e
->flags
& EDGE_EH
)
4258 return bitmap_ior_and_compl_into (op1
, op2
,
4259 regs_invalidated_by_call_regset
);
4261 return bitmap_ior_into (op1
, op2
);
4264 /* Free all storage associated with the problem. */
4269 struct df_md_problem_data
*problem_data
4270 = (struct df_md_problem_data
*) df_md
->problem_data
;
4272 bitmap_obstack_release (&problem_data
->md_bitmaps
);
4273 free (problem_data
);
4274 df_md
->problem_data
= NULL
;
4276 df_md
->block_info_size
= 0;
4277 free (df_md
->block_info
);
4278 df_md
->block_info
= NULL
;
4283 /* Debugging info at top of bb. */
4286 df_md_top_dump (basic_block bb
, FILE *file
)
4288 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4292 fprintf (file
, ";; md in \t");
4293 df_print_regset (file
, &bb_info
->in
);
4294 fprintf (file
, ";; md init \t");
4295 df_print_regset (file
, &bb_info
->init
);
4296 fprintf (file
, ";; md gen \t");
4297 df_print_regset (file
, &bb_info
->gen
);
4298 fprintf (file
, ";; md kill \t");
4299 df_print_regset (file
, &bb_info
->kill
);
4302 /* Debugging info at bottom of bb. */
4305 df_md_bottom_dump (basic_block bb
, FILE *file
)
4307 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4311 fprintf (file
, ";; md out \t");
4312 df_print_regset (file
, &bb_info
->out
);
4315 static struct df_problem problem_MD
=
4317 DF_MD
, /* Problem id. */
4318 DF_FORWARD
, /* Direction. */
4319 df_md_alloc
, /* Allocate the problem specific data. */
4320 df_md_reset
, /* Reset global information. */
4321 df_md_free_bb_info
, /* Free basic block info. */
4322 df_md_local_compute
, /* Local compute function. */
4323 df_md_init
, /* Init the solution specific data. */
4324 df_worklist_dataflow
, /* Worklist solver. */
4325 df_md_confluence_0
, /* Confluence operator 0. */
4326 df_md_confluence_n
, /* Confluence operator n. */
4327 df_md_transfer_function
, /* Transfer function. */
4328 NULL
, /* Finalize function. */
4329 df_md_free
, /* Free all of the problem information. */
4330 df_md_free
, /* Remove this problem from the stack of dataflow problems. */
4331 NULL
, /* Debugging. */
4332 df_md_top_dump
, /* Debugging start block. */
4333 df_md_bottom_dump
, /* Debugging end block. */
4334 NULL
, /* Debugging start insn. */
4335 NULL
, /* Debugging end insn. */
4336 NULL
, /* Incremental solution verify start. */
4337 NULL
, /* Incremental solution verify end. */
4338 NULL
, /* Dependent problem. */
4339 sizeof (struct df_md_bb_info
),/* Size of entry of block_info array. */
4340 TV_DF_MD
, /* Timing variable. */
4341 false /* Reset blocks on dropping out of blocks_to_analyze. */
4344 /* Create a new MD instance and add it to the existing instance
4348 df_md_add_problem (void)
4350 df_add_problem (&problem_MD
);