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"
35 #include "hard-reg-set.h"
39 #include "alloc-pool.h"
42 #include "dominance.h"
45 #include "basic-block.h"
57 /* Note that turning REG_DEAD_DEBUGGING on will cause
58 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
59 addresses in the dumps. */
60 #define REG_DEAD_DEBUGGING 0
62 #define DF_SPARSE_THRESHOLD 32
64 static bitmap_head seen_in_block
;
65 static bitmap_head seen_in_insn
;
67 /*----------------------------------------------------------------------------
69 ----------------------------------------------------------------------------*/
71 /* Generic versions to get the void* version of the block info. Only
72 used inside the problem instance vectors. */
74 /* Dump a def-use or use-def chain for REF to FILE. */
77 df_chain_dump (struct df_link
*link
, FILE *file
)
80 for (; link
; link
= link
->next
)
82 fprintf (file
, "%c%d(bb %d insn %d) ",
83 DF_REF_REG_DEF_P (link
->ref
)
85 : (DF_REF_FLAGS (link
->ref
) & DF_REF_IN_NOTE
) ? 'e' : 'u',
86 DF_REF_ID (link
->ref
),
87 DF_REF_BBNO (link
->ref
),
88 DF_REF_IS_ARTIFICIAL (link
->ref
)
89 ? -1 : DF_REF_INSN_UID (link
->ref
));
95 /* Print some basic block info as part of df_dump. */
98 df_print_bb_index (basic_block bb
, FILE *file
)
103 fprintf (file
, "\n( ");
104 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
106 basic_block pred
= e
->src
;
107 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
109 fprintf (file
, ")->[%d]->( ", bb
->index
);
110 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
112 basic_block succ
= e
->dest
;
113 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
115 fprintf (file
, ")\n");
119 /*----------------------------------------------------------------------------
122 Find the locations in the function where each definition site for a
123 pseudo reaches. In and out bitvectors are built for each basic
124 block. The id field in the ref is used to index into these sets.
125 See df.h for details.
127 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
128 existing uses are included in the global reaching DEFs set, or in other
129 words only DEFs that are still live. This is a kind of pruned version
130 of the traditional reaching definitions problem that is much less
131 complex to compute and produces enough information to compute UD-chains.
132 In this context, live must be interpreted in the DF_LR sense: Uses that
133 are upward exposed but maybe not initialized on all paths through the
134 CFG. For a USE that is not reached by a DEF on all paths, we still want
135 to make those DEFs that do reach the USE visible, and pruning based on
136 DF_LIVE would make that impossible.
137 ----------------------------------------------------------------------------*/
139 /* This problem plays a large number of games for the sake of
142 1) The order of the bits in the bitvectors. After the scanning
143 phase, all of the defs are sorted. All of the defs for the reg 0
144 are first, followed by all defs for reg 1 and so on.
146 2) There are two kill sets, one if the number of defs is less or
147 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
150 <= : Data is built directly in the kill set.
152 > : One level of indirection is used to keep from generating long
153 strings of 1 bits in the kill sets. Bitvectors that are indexed
154 by the regnum are used to represent that there is a killing def
155 for the register. The confluence and transfer functions use
156 these along with the bitmap_clear_range call to remove ranges of
157 bits without actually generating a knockout vector.
159 The kill and sparse_kill and the dense_invalidated_by_call and
160 sparse_invalidated_by_call both play this game. */
162 /* Private data used to compute the solution for this problem. These
163 data structures are not accessible outside of this module. */
164 struct df_rd_problem_data
166 /* The set of defs to regs invalidated by call. */
167 bitmap_head sparse_invalidated_by_call
;
168 /* The set of defs to regs invalidate by call for rd. */
169 bitmap_head dense_invalidated_by_call
;
170 /* An obstack for the bitmaps we need for this problem. */
171 bitmap_obstack rd_bitmaps
;
175 /* Free basic block info. */
178 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
181 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
184 bitmap_clear (&bb_info
->kill
);
185 bitmap_clear (&bb_info
->sparse_kill
);
186 bitmap_clear (&bb_info
->gen
);
187 bitmap_clear (&bb_info
->in
);
188 bitmap_clear (&bb_info
->out
);
193 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
194 not touched unless the block is new. */
197 df_rd_alloc (bitmap all_blocks
)
199 unsigned int bb_index
;
201 struct df_rd_problem_data
*problem_data
;
203 if (df_rd
->problem_data
)
205 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
206 bitmap_clear (&problem_data
->sparse_invalidated_by_call
);
207 bitmap_clear (&problem_data
->dense_invalidated_by_call
);
211 problem_data
= XNEW (struct df_rd_problem_data
);
212 df_rd
->problem_data
= problem_data
;
214 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
215 bitmap_initialize (&problem_data
->sparse_invalidated_by_call
,
216 &problem_data
->rd_bitmaps
);
217 bitmap_initialize (&problem_data
->dense_invalidated_by_call
,
218 &problem_data
->rd_bitmaps
);
221 df_grow_bb_info (df_rd
);
223 /* Because of the clustering of all use sites for the same pseudo,
224 we have to process all of the blocks before doing the analysis. */
226 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
228 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
230 /* When bitmaps are already initialized, just clear them. */
231 if (bb_info
->kill
.obstack
)
233 bitmap_clear (&bb_info
->kill
);
234 bitmap_clear (&bb_info
->sparse_kill
);
235 bitmap_clear (&bb_info
->gen
);
239 bitmap_initialize (&bb_info
->kill
, &problem_data
->rd_bitmaps
);
240 bitmap_initialize (&bb_info
->sparse_kill
, &problem_data
->rd_bitmaps
);
241 bitmap_initialize (&bb_info
->gen
, &problem_data
->rd_bitmaps
);
242 bitmap_initialize (&bb_info
->in
, &problem_data
->rd_bitmaps
);
243 bitmap_initialize (&bb_info
->out
, &problem_data
->rd_bitmaps
);
246 df_rd
->optional_p
= true;
250 /* Add the effect of the top artificial defs of BB to the reaching definitions
254 df_rd_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_rd
)
256 int bb_index
= bb
->index
;
258 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
259 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
261 unsigned int dregno
= DF_REF_REGNO (def
);
262 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
263 bitmap_clear_range (local_rd
,
264 DF_DEFS_BEGIN (dregno
),
265 DF_DEFS_COUNT (dregno
));
266 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
270 /* Add the effect of the defs of INSN to the reaching definitions bitmap
274 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx_insn
*insn
,
279 FOR_EACH_INSN_DEF (def
, insn
)
281 unsigned int dregno
= DF_REF_REGNO (def
);
282 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
283 || (dregno
>= FIRST_PSEUDO_REGISTER
))
285 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
286 bitmap_clear_range (local_rd
,
287 DF_DEFS_BEGIN (dregno
),
288 DF_DEFS_COUNT (dregno
));
289 if (!(DF_REF_FLAGS (def
)
290 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
291 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
296 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
297 more complicated than just simulating, because we must produce the
298 gen and kill sets and hence deal with the two possible representations
302 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
306 for (; def
; def
= DF_REF_NEXT_LOC (def
))
308 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
310 unsigned int regno
= DF_REF_REGNO (def
);
311 unsigned int begin
= DF_DEFS_BEGIN (regno
);
312 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
314 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
315 || (regno
>= FIRST_PSEUDO_REGISTER
))
317 /* Only the last def(s) for a regno in the block has any
319 if (!bitmap_bit_p (&seen_in_block
, regno
))
321 /* The first def for regno in insn gets to knock out the
322 defs from other instructions. */
323 if ((!bitmap_bit_p (&seen_in_insn
, regno
))
324 /* If the def is to only part of the reg, it does
325 not kill the other defs that reach here. */
326 && (!(DF_REF_FLAGS (def
) &
327 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
329 if (n_defs
> DF_SPARSE_THRESHOLD
)
331 bitmap_set_bit (&bb_info
->sparse_kill
, regno
);
332 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
336 bitmap_set_range (&bb_info
->kill
, begin
, n_defs
);
337 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
341 bitmap_set_bit (&seen_in_insn
, regno
);
342 /* All defs for regno in the instruction may be put into
344 if (!(DF_REF_FLAGS (def
)
345 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
346 bitmap_set_bit (&bb_info
->gen
, DF_REF_ID (def
));
353 /* Compute local reaching def info for basic block BB. */
356 df_rd_bb_local_compute (unsigned int bb_index
)
358 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
359 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
362 bitmap_clear (&seen_in_block
);
363 bitmap_clear (&seen_in_insn
);
365 /* Artificials are only hard regs. */
366 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
367 df_rd_bb_local_compute_process_def (bb_info
,
368 df_get_artificial_defs (bb_index
),
371 FOR_BB_INSNS_REVERSE (bb
, insn
)
373 unsigned int uid
= INSN_UID (insn
);
378 df_rd_bb_local_compute_process_def (bb_info
,
379 DF_INSN_UID_DEFS (uid
), 0);
381 /* This complex dance with the two bitmaps is required because
382 instructions can assign twice to the same pseudo. This
383 generally happens with calls that will have one def for the
384 result and another def for the clobber. If only one vector
385 is used and the clobber goes first, the result will be
387 bitmap_ior_into (&seen_in_block
, &seen_in_insn
);
388 bitmap_clear (&seen_in_insn
);
391 /* Process the artificial defs at the top of the block last since we
392 are going backwards through the block and these are logically at
394 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
395 df_rd_bb_local_compute_process_def (bb_info
,
396 df_get_artificial_defs (bb_index
),
401 /* Compute local reaching def info for each basic block within BLOCKS. */
404 df_rd_local_compute (bitmap all_blocks
)
406 unsigned int bb_index
;
409 struct df_rd_problem_data
*problem_data
410 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
411 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
412 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
414 bitmap_initialize (&seen_in_block
, &df_bitmap_obstack
);
415 bitmap_initialize (&seen_in_insn
, &df_bitmap_obstack
);
417 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
419 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
421 df_rd_bb_local_compute (bb_index
);
424 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
425 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset
, 0, regno
, bi
)
427 if (! HARD_REGISTER_NUM_P (regno
)
428 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
430 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
431 bitmap_set_bit (sparse_invalidated
, regno
);
433 bitmap_set_range (dense_invalidated
,
434 DF_DEFS_BEGIN (regno
),
435 DF_DEFS_COUNT (regno
));
439 bitmap_clear (&seen_in_block
);
440 bitmap_clear (&seen_in_insn
);
444 /* Initialize the solution bit vectors for problem. */
447 df_rd_init_solution (bitmap all_blocks
)
449 unsigned int bb_index
;
452 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
454 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
456 bitmap_copy (&bb_info
->out
, &bb_info
->gen
);
457 bitmap_clear (&bb_info
->in
);
461 /* In of target gets or of out of source. */
464 df_rd_confluence_n (edge e
)
466 bitmap op1
= &df_rd_get_bb_info (e
->dest
->index
)->in
;
467 bitmap op2
= &df_rd_get_bb_info (e
->src
->index
)->out
;
468 bool changed
= false;
470 if (e
->flags
& EDGE_FAKE
)
473 if (e
->flags
& EDGE_EH
)
475 struct df_rd_problem_data
*problem_data
476 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
477 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
478 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
483 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
484 bitmap_and_compl (&tmp
, op2
, dense_invalidated
);
486 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
488 bitmap_clear_range (&tmp
,
489 DF_DEFS_BEGIN (regno
),
490 DF_DEFS_COUNT (regno
));
492 changed
|= bitmap_ior_into (op1
, &tmp
);
497 return bitmap_ior_into (op1
, op2
);
501 /* Transfer function. */
504 df_rd_transfer_function (int bb_index
)
506 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
509 bitmap in
= &bb_info
->in
;
510 bitmap out
= &bb_info
->out
;
511 bitmap gen
= &bb_info
->gen
;
512 bitmap kill
= &bb_info
->kill
;
513 bitmap sparse_kill
= &bb_info
->sparse_kill
;
514 bool changed
= false;
516 if (bitmap_empty_p (sparse_kill
))
517 changed
= bitmap_ior_and_compl (out
, gen
, in
, kill
);
520 struct df_rd_problem_data
*problem_data
;
523 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
524 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
525 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
526 bitmap_initialize (&tmp
, &problem_data
->rd_bitmaps
);
528 bitmap_and_compl (&tmp
, in
, kill
);
529 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
531 bitmap_clear_range (&tmp
,
532 DF_DEFS_BEGIN (regno
),
533 DF_DEFS_COUNT (regno
));
535 bitmap_ior_into (&tmp
, gen
);
536 changed
= !bitmap_equal_p (&tmp
, out
);
546 if (df
->changeable_flags
& DF_RD_PRUNE_DEAD_DEFS
)
548 /* Create a mask of DEFs for all registers live at the end of this
549 basic block, and mask out DEFs of registers that are not live.
550 Computing the mask looks costly, but the benefit of the pruning
551 outweighs the cost. */
552 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
553 bitmap regs_live_out
= &df_lr_get_bb_info (bb_index
)->out
;
554 bitmap live_defs
= BITMAP_ALLOC (&df_bitmap_obstack
);
558 EXECUTE_IF_SET_IN_BITMAP (regs_live_out
, 0, regno
, bi
)
559 bitmap_set_range (live_defs
,
560 DF_DEFS_BEGIN (regno
),
561 DF_DEFS_COUNT (regno
));
562 changed
|= bitmap_and_into (&bb_info
->out
, live_defs
);
563 BITMAP_FREE (live_defs
);
569 /* Free all storage associated with the problem. */
574 struct df_rd_problem_data
*problem_data
575 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
579 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
581 df_rd
->block_info_size
= 0;
582 free (df_rd
->block_info
);
583 df_rd
->block_info
= NULL
;
584 free (df_rd
->problem_data
);
590 /* Debugging info. */
593 df_rd_start_dump (FILE *file
)
595 struct df_rd_problem_data
*problem_data
596 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
597 unsigned int m
= DF_REG_SIZE (df
);
600 if (!df_rd
->block_info
)
603 fprintf (file
, ";; Reaching defs:\n");
605 fprintf (file
, ";; sparse invalidated \t");
606 dump_bitmap (file
, &problem_data
->sparse_invalidated_by_call
);
607 fprintf (file
, ";; dense invalidated \t");
608 dump_bitmap (file
, &problem_data
->dense_invalidated_by_call
);
610 fprintf (file
, ";; reg->defs[] map:\t");
611 for (regno
= 0; regno
< m
; regno
++)
612 if (DF_DEFS_COUNT (regno
))
613 fprintf (file
, "%d[%d,%d] ", regno
,
614 DF_DEFS_BEGIN (regno
),
615 DF_DEFS_BEGIN (regno
) + DF_DEFS_COUNT (regno
) - 1);
616 fprintf (file
, "\n");
621 df_rd_dump_defs_set (bitmap defs_set
, const char *prefix
, FILE *file
)
625 unsigned int m
= DF_REG_SIZE (df
);
626 bool first_reg
= true;
628 fprintf (file
, "%s\t(%d) ", prefix
, (int) bitmap_count_bits (defs_set
));
630 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
631 for (regno
= 0; regno
< m
; regno
++)
633 if (HARD_REGISTER_NUM_P (regno
)
634 && (df
->changeable_flags
& DF_NO_HARD_REGS
))
636 bitmap_set_range (&tmp
, DF_DEFS_BEGIN (regno
), DF_DEFS_COUNT (regno
));
637 bitmap_and_into (&tmp
, defs_set
);
638 if (! bitmap_empty_p (&tmp
))
642 bool first_def
= true;
648 fprintf (file
, "%u[", regno
);
649 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, ix
, bi
)
651 fprintf (file
, "%s%u", first_def
? "" : ",", ix
);
659 fprintf (file
, "\n");
663 /* Debugging info at top of bb. */
666 df_rd_top_dump (basic_block bb
, FILE *file
)
668 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
672 df_rd_dump_defs_set (&bb_info
->in
, ";; rd in ", file
);
673 df_rd_dump_defs_set (&bb_info
->gen
, ";; rd gen ", file
);
674 df_rd_dump_defs_set (&bb_info
->kill
, ";; rd kill", file
);
678 /* Debugging info at bottom of bb. */
681 df_rd_bottom_dump (basic_block bb
, FILE *file
)
683 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
687 df_rd_dump_defs_set (&bb_info
->out
, ";; rd out ", file
);
690 /* All of the information associated with every instance of the problem. */
692 static struct df_problem problem_RD
=
694 DF_RD
, /* Problem id. */
695 DF_FORWARD
, /* Direction. */
696 df_rd_alloc
, /* Allocate the problem specific data. */
697 NULL
, /* Reset global information. */
698 df_rd_free_bb_info
, /* Free basic block info. */
699 df_rd_local_compute
, /* Local compute function. */
700 df_rd_init_solution
, /* Init the solution specific data. */
701 df_worklist_dataflow
, /* Worklist solver. */
702 NULL
, /* Confluence operator 0. */
703 df_rd_confluence_n
, /* Confluence operator n. */
704 df_rd_transfer_function
, /* Transfer function. */
705 NULL
, /* Finalize function. */
706 df_rd_free
, /* Free all of the problem information. */
707 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
708 df_rd_start_dump
, /* Debugging. */
709 df_rd_top_dump
, /* Debugging start block. */
710 df_rd_bottom_dump
, /* Debugging end block. */
711 NULL
, /* Debugging start insn. */
712 NULL
, /* Debugging end insn. */
713 NULL
, /* Incremental solution verify start. */
714 NULL
, /* Incremental solution verify end. */
715 NULL
, /* Dependent problem. */
716 sizeof (struct df_rd_bb_info
),/* Size of entry of block_info array. */
717 TV_DF_RD
, /* Timing variable. */
718 true /* Reset blocks on dropping out of blocks_to_analyze. */
723 /* Create a new RD instance and add it to the existing instance
727 df_rd_add_problem (void)
729 df_add_problem (&problem_RD
);
734 /*----------------------------------------------------------------------------
737 Find the locations in the function where any use of a pseudo can
738 reach in the backwards direction. In and out bitvectors are built
739 for each basic block. The regno is used to index into these sets.
740 See df.h for details.
741 ----------------------------------------------------------------------------*/
743 /* Private data used to verify the solution for this problem. */
744 struct df_lr_problem_data
748 /* An obstack for the bitmaps we need for this problem. */
749 bitmap_obstack lr_bitmaps
;
752 /* Free basic block info. */
755 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
758 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
761 bitmap_clear (&bb_info
->use
);
762 bitmap_clear (&bb_info
->def
);
763 bitmap_clear (&bb_info
->in
);
764 bitmap_clear (&bb_info
->out
);
769 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
770 not touched unless the block is new. */
773 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
775 unsigned int bb_index
;
777 struct df_lr_problem_data
*problem_data
;
779 df_grow_bb_info (df_lr
);
780 if (df_lr
->problem_data
)
781 problem_data
= (struct df_lr_problem_data
*) df_lr
->problem_data
;
784 problem_data
= XNEW (struct df_lr_problem_data
);
785 df_lr
->problem_data
= problem_data
;
787 problem_data
->out
= NULL
;
788 problem_data
->in
= NULL
;
789 bitmap_obstack_initialize (&problem_data
->lr_bitmaps
);
792 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
794 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
796 /* When bitmaps are already initialized, just clear them. */
797 if (bb_info
->use
.obstack
)
799 bitmap_clear (&bb_info
->def
);
800 bitmap_clear (&bb_info
->use
);
804 bitmap_initialize (&bb_info
->use
, &problem_data
->lr_bitmaps
);
805 bitmap_initialize (&bb_info
->def
, &problem_data
->lr_bitmaps
);
806 bitmap_initialize (&bb_info
->in
, &problem_data
->lr_bitmaps
);
807 bitmap_initialize (&bb_info
->out
, &problem_data
->lr_bitmaps
);
811 df_lr
->optional_p
= false;
815 /* Reset the global solution for recalculation. */
818 df_lr_reset (bitmap all_blocks
)
820 unsigned int bb_index
;
823 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
825 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
826 gcc_assert (bb_info
);
827 bitmap_clear (&bb_info
->in
);
828 bitmap_clear (&bb_info
->out
);
833 /* Compute local live register info for basic block BB. */
836 df_lr_bb_local_compute (unsigned int bb_index
)
838 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
839 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
843 /* Process the registers set in an exception handler. */
844 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
845 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
847 unsigned int dregno
= DF_REF_REGNO (def
);
848 bitmap_set_bit (&bb_info
->def
, dregno
);
849 bitmap_clear_bit (&bb_info
->use
, dregno
);
852 /* Process the hardware registers that are always live. */
853 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
854 /* Add use to set of uses in this BB. */
855 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
856 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
858 FOR_BB_INSNS_REVERSE (bb
, insn
)
860 if (!NONDEBUG_INSN_P (insn
))
863 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
864 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
865 /* If the def is to only part of the reg, it does
866 not kill the other defs that reach here. */
867 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
869 unsigned int dregno
= DF_REF_REGNO (def
);
870 bitmap_set_bit (&bb_info
->def
, dregno
);
871 bitmap_clear_bit (&bb_info
->use
, dregno
);
874 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
875 /* Add use to set of uses in this BB. */
876 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
879 /* Process the registers set in an exception handler or the hard
880 frame pointer if this block is the target of a non local
882 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
883 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
885 unsigned int dregno
= DF_REF_REGNO (def
);
886 bitmap_set_bit (&bb_info
->def
, dregno
);
887 bitmap_clear_bit (&bb_info
->use
, dregno
);
891 /* Process the uses that are live into an exception handler. */
892 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
893 /* Add use to set of uses in this BB. */
894 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
895 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
898 /* If the df_live problem is not defined, such as at -O0 and -O1, we
899 still need to keep the luids up to date. This is normally done
900 in the df_live problem since this problem has a forwards
903 df_recompute_luids (bb
);
907 /* Compute local live register info for each basic block within BLOCKS. */
910 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
912 unsigned int bb_index
, i
;
915 bitmap_clear (&df
->hardware_regs_used
);
917 /* The all-important stack pointer must always be live. */
918 bitmap_set_bit (&df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
920 /* Global regs are always live, too. */
921 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
923 bitmap_set_bit (&df
->hardware_regs_used
, i
);
925 /* Before reload, there are a few registers that must be forced
926 live everywhere -- which might not already be the case for
927 blocks within infinite loops. */
928 if (!reload_completed
)
930 unsigned int pic_offset_table_regnum
= PIC_OFFSET_TABLE_REGNUM
;
931 /* Any reference to any pseudo before reload is a potential
932 reference of the frame pointer. */
933 bitmap_set_bit (&df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
935 /* Pseudos with argument area equivalences may require
936 reloading via the argument pointer. */
937 if (FRAME_POINTER_REGNUM
!= ARG_POINTER_REGNUM
938 && fixed_regs
[ARG_POINTER_REGNUM
])
939 bitmap_set_bit (&df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
941 /* Any constant, or pseudo with constant equivalences, may
942 require reloading from memory using the pic register. */
943 if (pic_offset_table_regnum
!= INVALID_REGNUM
944 && fixed_regs
[pic_offset_table_regnum
])
945 bitmap_set_bit (&df
->hardware_regs_used
, pic_offset_table_regnum
);
948 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
950 if (bb_index
== EXIT_BLOCK
)
952 /* The exit block is special for this problem and its bits are
953 computed from thin air. */
954 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
955 bitmap_copy (&bb_info
->use
, df
->exit_block_uses
);
958 df_lr_bb_local_compute (bb_index
);
961 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
965 /* Initialize the solution vectors. */
968 df_lr_init (bitmap all_blocks
)
970 unsigned int bb_index
;
973 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
975 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
976 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
977 bitmap_clear (&bb_info
->out
);
982 /* Confluence function that processes infinite loops. This might be a
983 noreturn function that throws. And even if it isn't, getting the
984 unwind info right helps debugging. */
986 df_lr_confluence_0 (basic_block bb
)
988 bitmap op1
= &df_lr_get_bb_info (bb
->index
)->out
;
989 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
990 bitmap_copy (op1
, &df
->hardware_regs_used
);
994 /* Confluence function that ignores fake edges. */
997 df_lr_confluence_n (edge e
)
999 bitmap op1
= &df_lr_get_bb_info (e
->src
->index
)->out
;
1000 bitmap op2
= &df_lr_get_bb_info (e
->dest
->index
)->in
;
1001 bool changed
= false;
1003 /* Call-clobbered registers die across exception and call edges. */
1004 /* ??? Abnormal call edges ignored for the moment, as this gets
1005 confused by sibling call edges, which crashes reg-stack. */
1006 if (e
->flags
& EDGE_EH
)
1007 changed
= bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
1009 changed
= bitmap_ior_into (op1
, op2
);
1011 changed
|= bitmap_ior_into (op1
, &df
->hardware_regs_used
);
1016 /* Transfer function. */
1019 df_lr_transfer_function (int bb_index
)
1021 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1022 bitmap in
= &bb_info
->in
;
1023 bitmap out
= &bb_info
->out
;
1024 bitmap use
= &bb_info
->use
;
1025 bitmap def
= &bb_info
->def
;
1027 return bitmap_ior_and_compl (in
, use
, out
, def
);
1031 /* Run the fast dce as a side effect of building LR. */
1034 df_lr_finalize (bitmap all_blocks
)
1036 df_lr
->solutions_dirty
= false;
1037 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1041 /* If dce deletes some instructions, we need to recompute the lr
1042 solution before proceeding further. The problem is that fast
1043 dce is a pessimestic dataflow algorithm. In the case where
1044 it deletes a statement S inside of a loop, the uses inside of
1045 S may not be deleted from the dataflow solution because they
1046 were carried around the loop. While it is conservatively
1047 correct to leave these extra bits, the standards of df
1048 require that we maintain the best possible (least fixed
1049 point) solution. The only way to do that is to redo the
1050 iteration from the beginning. See PR35805 for an
1052 if (df_lr
->solutions_dirty
)
1054 df_clear_flags (DF_LR_RUN_DCE
);
1055 df_lr_alloc (all_blocks
);
1056 df_lr_local_compute (all_blocks
);
1057 df_worklist_dataflow (df_lr
, all_blocks
, df
->postorder
, df
->n_blocks
);
1058 df_lr_finalize (all_blocks
);
1059 df_set_flags (DF_LR_RUN_DCE
);
1065 /* Free all storage associated with the problem. */
1070 struct df_lr_problem_data
*problem_data
1071 = (struct df_lr_problem_data
*) df_lr
->problem_data
;
1072 if (df_lr
->block_info
)
1075 df_lr
->block_info_size
= 0;
1076 free (df_lr
->block_info
);
1077 df_lr
->block_info
= NULL
;
1078 bitmap_obstack_release (&problem_data
->lr_bitmaps
);
1079 free (df_lr
->problem_data
);
1080 df_lr
->problem_data
= NULL
;
1083 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1088 /* Debugging info at top of bb. */
1091 df_lr_top_dump (basic_block bb
, FILE *file
)
1093 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1094 struct df_lr_problem_data
*problem_data
;
1098 fprintf (file
, ";; lr in \t");
1099 df_print_regset (file
, &bb_info
->in
);
1100 if (df_lr
->problem_data
)
1102 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1103 if (problem_data
->in
)
1105 fprintf (file
, ";; old in \t");
1106 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1109 fprintf (file
, ";; lr use \t");
1110 df_print_regset (file
, &bb_info
->use
);
1111 fprintf (file
, ";; lr def \t");
1112 df_print_regset (file
, &bb_info
->def
);
1116 /* Debugging info at bottom of bb. */
1119 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1121 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1122 struct df_lr_problem_data
*problem_data
;
1126 fprintf (file
, ";; lr out \t");
1127 df_print_regset (file
, &bb_info
->out
);
1128 if (df_lr
->problem_data
)
1130 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1131 if (problem_data
->out
)
1133 fprintf (file
, ";; old out \t");
1134 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1140 /* Build the datastructure to verify that the solution to the dataflow
1141 equations is not dirty. */
1144 df_lr_verify_solution_start (void)
1147 struct df_lr_problem_data
*problem_data
;
1148 if (df_lr
->solutions_dirty
)
1151 /* Set it true so that the solution is recomputed. */
1152 df_lr
->solutions_dirty
= true;
1154 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1155 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1156 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1158 FOR_ALL_BB_FN (bb
, cfun
)
1160 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->lr_bitmaps
);
1161 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->lr_bitmaps
);
1162 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1163 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1168 /* Compare the saved datastructure and the new solution to the dataflow
1172 df_lr_verify_solution_end (void)
1174 struct df_lr_problem_data
*problem_data
;
1177 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1179 if (!problem_data
->out
)
1182 if (df_lr
->solutions_dirty
)
1183 /* Do not check if the solution is still dirty. See the comment
1184 in df_lr_finalize for details. */
1185 df_lr
->solutions_dirty
= false;
1187 FOR_ALL_BB_FN (bb
, cfun
)
1189 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1190 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1192 /*df_dump (stderr);*/
1197 /* Cannot delete them immediately because you may want to dump them
1198 if the comparison fails. */
1199 FOR_ALL_BB_FN (bb
, cfun
)
1201 bitmap_clear (&problem_data
->in
[bb
->index
]);
1202 bitmap_clear (&problem_data
->out
[bb
->index
]);
1205 free (problem_data
->in
);
1206 free (problem_data
->out
);
1207 problem_data
->in
= NULL
;
1208 problem_data
->out
= NULL
;
1212 /* All of the information associated with every instance of the problem. */
1214 static struct df_problem problem_LR
=
1216 DF_LR
, /* Problem id. */
1217 DF_BACKWARD
, /* Direction. */
1218 df_lr_alloc
, /* Allocate the problem specific data. */
1219 df_lr_reset
, /* Reset global information. */
1220 df_lr_free_bb_info
, /* Free basic block info. */
1221 df_lr_local_compute
, /* Local compute function. */
1222 df_lr_init
, /* Init the solution specific data. */
1223 df_worklist_dataflow
, /* Worklist solver. */
1224 df_lr_confluence_0
, /* Confluence operator 0. */
1225 df_lr_confluence_n
, /* Confluence operator n. */
1226 df_lr_transfer_function
, /* Transfer function. */
1227 df_lr_finalize
, /* Finalize function. */
1228 df_lr_free
, /* Free all of the problem information. */
1229 NULL
, /* Remove this problem from the stack of dataflow problems. */
1230 NULL
, /* Debugging. */
1231 df_lr_top_dump
, /* Debugging start block. */
1232 df_lr_bottom_dump
, /* Debugging end block. */
1233 NULL
, /* Debugging start insn. */
1234 NULL
, /* Debugging end insn. */
1235 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1236 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1237 NULL
, /* Dependent problem. */
1238 sizeof (struct df_lr_bb_info
),/* Size of entry of block_info array. */
1239 TV_DF_LR
, /* Timing variable. */
1240 false /* Reset blocks on dropping out of blocks_to_analyze. */
1244 /* Create a new DATAFLOW instance and add it to an existing instance
1245 of DF. The returned structure is what is used to get at the
1249 df_lr_add_problem (void)
1251 df_add_problem (&problem_LR
);
1252 /* These will be initialized when df_scan_blocks processes each
1254 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
1258 /* Verify that all of the lr related info is consistent and
1262 df_lr_verify_transfer_functions (void)
1265 bitmap_head saved_def
;
1266 bitmap_head saved_use
;
1267 bitmap_head all_blocks
;
1272 bitmap_initialize (&saved_def
, &bitmap_default_obstack
);
1273 bitmap_initialize (&saved_use
, &bitmap_default_obstack
);
1274 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1276 FOR_ALL_BB_FN (bb
, cfun
)
1278 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1279 bitmap_set_bit (&all_blocks
, bb
->index
);
1283 /* Make a copy of the transfer functions and then compute
1284 new ones to see if the transfer functions have
1286 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1289 bitmap_copy (&saved_def
, &bb_info
->def
);
1290 bitmap_copy (&saved_use
, &bb_info
->use
);
1291 bitmap_clear (&bb_info
->def
);
1292 bitmap_clear (&bb_info
->use
);
1294 df_lr_bb_local_compute (bb
->index
);
1295 gcc_assert (bitmap_equal_p (&saved_def
, &bb_info
->def
));
1296 gcc_assert (bitmap_equal_p (&saved_use
, &bb_info
->use
));
1301 /* If we do not have basic block info, the block must be in
1302 the list of dirty blocks or else some one has added a
1303 block behind our backs. */
1304 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1307 /* Make sure no one created a block without following
1309 gcc_assert (df_scan_get_bb_info (bb
->index
));
1312 /* Make sure there are no dirty bits in blocks that have been deleted. */
1313 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1316 bitmap_clear (&saved_def
);
1317 bitmap_clear (&saved_use
);
1318 bitmap_clear (&all_blocks
);
1323 /*----------------------------------------------------------------------------
1324 LIVE AND MUST-INITIALIZED REGISTERS.
1326 This problem first computes the IN and OUT bitvectors for the
1327 must-initialized registers problems, which is a forward problem.
1328 It gives the set of registers for which we MUST have an available
1329 definition on any path from the entry block to the entry/exit of
1330 a basic block. Sets generate a definition, while clobbers kill
1333 In and out bitvectors are built for each basic block and are indexed by
1334 regnum (see df.h for details). In and out bitvectors in struct
1335 df_live_bb_info actually refers to the must-initialized problem;
1337 Then, the in and out sets for the LIVE problem itself are computed.
1338 These are the logical AND of the IN and OUT sets from the LR problem
1339 and the must-initialized problem.
1340 ----------------------------------------------------------------------------*/
1342 /* Private data used to verify the solution for this problem. */
1343 struct df_live_problem_data
1347 /* An obstack for the bitmaps we need for this problem. */
1348 bitmap_obstack live_bitmaps
;
1351 /* Scratch var used by transfer functions. This is used to implement
1352 an optimization to reduce the amount of space used to compute the
1353 combined lr and live analysis. */
1354 static bitmap_head df_live_scratch
;
1357 /* Free basic block info. */
1360 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1363 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1366 bitmap_clear (&bb_info
->gen
);
1367 bitmap_clear (&bb_info
->kill
);
1368 bitmap_clear (&bb_info
->in
);
1369 bitmap_clear (&bb_info
->out
);
1374 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1375 not touched unless the block is new. */
1378 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1380 unsigned int bb_index
;
1382 struct df_live_problem_data
*problem_data
;
1384 if (df_live
->problem_data
)
1385 problem_data
= (struct df_live_problem_data
*) df_live
->problem_data
;
1388 problem_data
= XNEW (struct df_live_problem_data
);
1389 df_live
->problem_data
= problem_data
;
1391 problem_data
->out
= NULL
;
1392 problem_data
->in
= NULL
;
1393 bitmap_obstack_initialize (&problem_data
->live_bitmaps
);
1394 bitmap_initialize (&df_live_scratch
, &problem_data
->live_bitmaps
);
1397 df_grow_bb_info (df_live
);
1399 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1401 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1403 /* When bitmaps are already initialized, just clear them. */
1404 if (bb_info
->kill
.obstack
)
1406 bitmap_clear (&bb_info
->kill
);
1407 bitmap_clear (&bb_info
->gen
);
1411 bitmap_initialize (&bb_info
->kill
, &problem_data
->live_bitmaps
);
1412 bitmap_initialize (&bb_info
->gen
, &problem_data
->live_bitmaps
);
1413 bitmap_initialize (&bb_info
->in
, &problem_data
->live_bitmaps
);
1414 bitmap_initialize (&bb_info
->out
, &problem_data
->live_bitmaps
);
1417 df_live
->optional_p
= (optimize
<= 1);
1421 /* Reset the global solution for recalculation. */
1424 df_live_reset (bitmap all_blocks
)
1426 unsigned int bb_index
;
1429 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1431 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1432 gcc_assert (bb_info
);
1433 bitmap_clear (&bb_info
->in
);
1434 bitmap_clear (&bb_info
->out
);
1439 /* Compute local uninitialized register info for basic block BB. */
1442 df_live_bb_local_compute (unsigned int bb_index
)
1444 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
1445 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1450 FOR_BB_INSNS (bb
, insn
)
1452 unsigned int uid
= INSN_UID (insn
);
1453 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1455 /* Inserting labels does not always trigger the incremental
1459 gcc_assert (!INSN_P (insn
));
1460 insn_info
= df_insn_create_insn_record (insn
);
1463 DF_INSN_INFO_LUID (insn_info
) = luid
;
1468 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1470 unsigned int regno
= DF_REF_REGNO (def
);
1472 if (DF_REF_FLAGS_IS_SET (def
,
1473 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1474 /* All partial or conditional def
1475 seen are included in the gen set. */
1476 bitmap_set_bit (&bb_info
->gen
, regno
);
1477 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1478 /* Only must clobbers for the entire reg destroy the
1480 bitmap_set_bit (&bb_info
->kill
, regno
);
1481 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1482 bitmap_set_bit (&bb_info
->gen
, regno
);
1486 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
1487 bitmap_set_bit (&bb_info
->gen
, DF_REF_REGNO (def
));
1491 /* Compute local uninitialized register info. */
1494 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1496 unsigned int bb_index
;
1499 df_grow_insn_info ();
1501 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1504 df_live_bb_local_compute (bb_index
);
1507 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1511 /* Initialize the solution vectors. */
1514 df_live_init (bitmap all_blocks
)
1516 unsigned int bb_index
;
1519 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1521 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1522 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1524 /* No register may reach a location where it is not used. Thus
1525 we trim the rr result to the places where it is used. */
1526 bitmap_and (&bb_info
->out
, &bb_info
->gen
, &bb_lr_info
->out
);
1527 bitmap_clear (&bb_info
->in
);
1531 /* Forward confluence function that ignores fake edges. */
1534 df_live_confluence_n (edge e
)
1536 bitmap op1
= &df_live_get_bb_info (e
->dest
->index
)->in
;
1537 bitmap op2
= &df_live_get_bb_info (e
->src
->index
)->out
;
1539 if (e
->flags
& EDGE_FAKE
)
1542 return bitmap_ior_into (op1
, op2
);
1546 /* Transfer function for the forwards must-initialized problem. */
1549 df_live_transfer_function (int bb_index
)
1551 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1552 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1553 bitmap in
= &bb_info
->in
;
1554 bitmap out
= &bb_info
->out
;
1555 bitmap gen
= &bb_info
->gen
;
1556 bitmap kill
= &bb_info
->kill
;
1558 /* We need to use a scratch set here so that the value returned from this
1559 function invocation properly reflects whether the sets changed in a
1560 significant way; i.e. not just because the lr set was anded in. */
1561 bitmap_and (&df_live_scratch
, gen
, &bb_lr_info
->out
);
1562 /* No register may reach a location where it is not used. Thus
1563 we trim the rr result to the places where it is used. */
1564 bitmap_and_into (in
, &bb_lr_info
->in
);
1566 return bitmap_ior_and_compl (out
, &df_live_scratch
, in
, kill
);
1570 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1573 df_live_finalize (bitmap all_blocks
)
1576 if (df_live
->solutions_dirty
)
1579 unsigned int bb_index
;
1581 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1583 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1584 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1586 /* No register may reach a location where it is not used. Thus
1587 we trim the rr result to the places where it is used. */
1588 bitmap_and_into (&bb_live_info
->in
, &bb_lr_info
->in
);
1589 bitmap_and_into (&bb_live_info
->out
, &bb_lr_info
->out
);
1592 df_live
->solutions_dirty
= false;
1597 /* Free all storage associated with the problem. */
1602 struct df_live_problem_data
*problem_data
1603 = (struct df_live_problem_data
*) df_live
->problem_data
;
1604 if (df_live
->block_info
)
1606 df_live
->block_info_size
= 0;
1607 free (df_live
->block_info
);
1608 df_live
->block_info
= NULL
;
1609 bitmap_clear (&df_live_scratch
);
1610 bitmap_obstack_release (&problem_data
->live_bitmaps
);
1611 free (problem_data
);
1612 df_live
->problem_data
= NULL
;
1614 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1619 /* Debugging info at top of bb. */
1622 df_live_top_dump (basic_block bb
, FILE *file
)
1624 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1625 struct df_live_problem_data
*problem_data
;
1630 fprintf (file
, ";; live in \t");
1631 df_print_regset (file
, &bb_info
->in
);
1632 if (df_live
->problem_data
)
1634 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1635 if (problem_data
->in
)
1637 fprintf (file
, ";; old in \t");
1638 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1641 fprintf (file
, ";; live gen \t");
1642 df_print_regset (file
, &bb_info
->gen
);
1643 fprintf (file
, ";; live kill\t");
1644 df_print_regset (file
, &bb_info
->kill
);
1648 /* Debugging info at bottom of bb. */
1651 df_live_bottom_dump (basic_block bb
, FILE *file
)
1653 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1654 struct df_live_problem_data
*problem_data
;
1659 fprintf (file
, ";; live out \t");
1660 df_print_regset (file
, &bb_info
->out
);
1661 if (df_live
->problem_data
)
1663 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1664 if (problem_data
->out
)
1666 fprintf (file
, ";; old out \t");
1667 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1673 /* Build the datastructure to verify that the solution to the dataflow
1674 equations is not dirty. */
1677 df_live_verify_solution_start (void)
1680 struct df_live_problem_data
*problem_data
;
1681 if (df_live
->solutions_dirty
)
1684 /* Set it true so that the solution is recomputed. */
1685 df_live
->solutions_dirty
= true;
1687 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1688 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1689 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
1691 FOR_ALL_BB_FN (bb
, cfun
)
1693 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->live_bitmaps
);
1694 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->live_bitmaps
);
1695 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1696 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1701 /* Compare the saved datastructure and the new solution to the dataflow
1705 df_live_verify_solution_end (void)
1707 struct df_live_problem_data
*problem_data
;
1710 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1711 if (!problem_data
->out
)
1714 FOR_ALL_BB_FN (bb
, cfun
)
1716 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1717 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
1719 /*df_dump (stderr);*/
1724 /* Cannot delete them immediately because you may want to dump them
1725 if the comparison fails. */
1726 FOR_ALL_BB_FN (bb
, cfun
)
1728 bitmap_clear (&problem_data
->in
[bb
->index
]);
1729 bitmap_clear (&problem_data
->out
[bb
->index
]);
1732 free (problem_data
->in
);
1733 free (problem_data
->out
);
1734 free (problem_data
);
1735 df_live
->problem_data
= NULL
;
1739 /* All of the information associated with every instance of the problem. */
1741 static struct df_problem problem_LIVE
=
1743 DF_LIVE
, /* Problem id. */
1744 DF_FORWARD
, /* Direction. */
1745 df_live_alloc
, /* Allocate the problem specific data. */
1746 df_live_reset
, /* Reset global information. */
1747 df_live_free_bb_info
, /* Free basic block info. */
1748 df_live_local_compute
, /* Local compute function. */
1749 df_live_init
, /* Init the solution specific data. */
1750 df_worklist_dataflow
, /* Worklist solver. */
1751 NULL
, /* Confluence operator 0. */
1752 df_live_confluence_n
, /* Confluence operator n. */
1753 df_live_transfer_function
, /* Transfer function. */
1754 df_live_finalize
, /* Finalize function. */
1755 df_live_free
, /* Free all of the problem information. */
1756 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1757 NULL
, /* Debugging. */
1758 df_live_top_dump
, /* Debugging start block. */
1759 df_live_bottom_dump
, /* Debugging end block. */
1760 NULL
, /* Debugging start insn. */
1761 NULL
, /* Debugging end insn. */
1762 df_live_verify_solution_start
,/* Incremental solution verify start. */
1763 df_live_verify_solution_end
, /* Incremental solution verify end. */
1764 &problem_LR
, /* Dependent problem. */
1765 sizeof (struct df_live_bb_info
),/* Size of entry of block_info array. */
1766 TV_DF_LIVE
, /* Timing variable. */
1767 false /* Reset blocks on dropping out of blocks_to_analyze. */
1771 /* Create a new DATAFLOW instance and add it to an existing instance
1772 of DF. The returned structure is what is used to get at the
1776 df_live_add_problem (void)
1778 df_add_problem (&problem_LIVE
);
1779 /* These will be initialized when df_scan_blocks processes each
1781 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
1785 /* Set all of the blocks as dirty. This needs to be done if this
1786 problem is added after all of the insns have been scanned. */
1789 df_live_set_all_dirty (void)
1792 FOR_ALL_BB_FN (bb
, cfun
)
1793 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1798 /* Verify that all of the lr related info is consistent and
1802 df_live_verify_transfer_functions (void)
1805 bitmap_head saved_gen
;
1806 bitmap_head saved_kill
;
1807 bitmap_head all_blocks
;
1812 bitmap_initialize (&saved_gen
, &bitmap_default_obstack
);
1813 bitmap_initialize (&saved_kill
, &bitmap_default_obstack
);
1814 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1816 df_grow_insn_info ();
1818 FOR_ALL_BB_FN (bb
, cfun
)
1820 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1821 bitmap_set_bit (&all_blocks
, bb
->index
);
1825 /* Make a copy of the transfer functions and then compute
1826 new ones to see if the transfer functions have
1828 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1831 bitmap_copy (&saved_gen
, &bb_info
->gen
);
1832 bitmap_copy (&saved_kill
, &bb_info
->kill
);
1833 bitmap_clear (&bb_info
->gen
);
1834 bitmap_clear (&bb_info
->kill
);
1836 df_live_bb_local_compute (bb
->index
);
1837 gcc_assert (bitmap_equal_p (&saved_gen
, &bb_info
->gen
));
1838 gcc_assert (bitmap_equal_p (&saved_kill
, &bb_info
->kill
));
1843 /* If we do not have basic block info, the block must be in
1844 the list of dirty blocks or else some one has added a
1845 block behind our backs. */
1846 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1849 /* Make sure no one created a block without following
1851 gcc_assert (df_scan_get_bb_info (bb
->index
));
1854 /* Make sure there are no dirty bits in blocks that have been deleted. */
1855 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1857 bitmap_clear (&saved_gen
);
1858 bitmap_clear (&saved_kill
);
1859 bitmap_clear (&all_blocks
);
1862 /*----------------------------------------------------------------------------
1863 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1865 Link either the defs to the uses and / or the uses to the defs.
1867 These problems are set up like the other dataflow problems so that
1868 they nicely fit into the framework. They are much simpler and only
1869 involve a single traversal of instructions and an examination of
1870 the reaching defs information (the dependent problem).
1871 ----------------------------------------------------------------------------*/
1873 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1875 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1878 df_chain_create (df_ref src
, df_ref dst
)
1880 struct df_link
*head
= DF_REF_CHAIN (src
);
1881 struct df_link
*link
= df_chain
->block_pool
->allocate ();
1883 DF_REF_CHAIN (src
) = link
;
1890 /* Delete any du or ud chains that start at REF and point to
1893 df_chain_unlink_1 (df_ref ref
, df_ref target
)
1895 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1896 struct df_link
*prev
= NULL
;
1900 if (chain
->ref
== target
)
1903 prev
->next
= chain
->next
;
1905 DF_REF_CHAIN (ref
) = chain
->next
;
1906 df_chain
->block_pool
->remove (chain
);
1910 chain
= chain
->next
;
1915 /* Delete a du or ud chain that leave or point to REF. */
1918 df_chain_unlink (df_ref ref
)
1920 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1923 struct df_link
*next
= chain
->next
;
1924 /* Delete the other side if it exists. */
1925 df_chain_unlink_1 (chain
->ref
, ref
);
1926 df_chain
->block_pool
->remove (chain
);
1929 DF_REF_CHAIN (ref
) = NULL
;
1933 /* Copy the du or ud chain starting at FROM_REF and attach it to
1937 df_chain_copy (df_ref to_ref
,
1938 struct df_link
*from_ref
)
1942 df_chain_create (to_ref
, from_ref
->ref
);
1943 from_ref
= from_ref
->next
;
1948 /* Remove this problem from the stack of dataflow problems. */
1951 df_chain_remove_problem (void)
1954 unsigned int bb_index
;
1956 /* Wholesale destruction of the old chains. */
1957 if (df_chain
->block_pool
)
1958 delete df_chain
->block_pool
;
1960 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1964 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
1966 if (df_chain_problem_p (DF_DU_CHAIN
))
1967 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
1968 DF_REF_CHAIN (def
) = NULL
;
1969 if (df_chain_problem_p (DF_UD_CHAIN
))
1970 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
1971 DF_REF_CHAIN (use
) = NULL
;
1973 FOR_BB_INSNS (bb
, insn
)
1976 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
1977 if (df_chain_problem_p (DF_DU_CHAIN
))
1978 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1979 DF_REF_CHAIN (def
) = NULL
;
1980 if (df_chain_problem_p (DF_UD_CHAIN
))
1982 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
1983 DF_REF_CHAIN (use
) = NULL
;
1984 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
1985 DF_REF_CHAIN (use
) = NULL
;
1990 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
1991 df_chain
->block_pool
= NULL
;
1995 /* Remove the chain problem completely. */
1998 df_chain_fully_remove_problem (void)
2000 df_chain_remove_problem ();
2001 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2006 /* Create def-use or use-def chains. */
2009 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2011 df_chain_remove_problem ();
2012 df_chain
->block_pool
= new pool_allocator
<df_link
> ("df_chain_block pool",
2014 df_chain
->optional_p
= true;
2018 /* Reset all of the chains when the set of basic blocks changes. */
2021 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2023 df_chain_remove_problem ();
2027 /* Create the chains for a list of USEs. */
2030 df_chain_create_bb_process_use (bitmap local_rd
,
2035 unsigned int def_index
;
2037 for (; use
; use
= DF_REF_NEXT_LOC (use
))
2039 unsigned int uregno
= DF_REF_REGNO (use
);
2040 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2041 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2043 /* Do not want to go through this for an uninitialized var. */
2044 int count
= DF_DEFS_COUNT (uregno
);
2047 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2049 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2050 unsigned int last_index
= first_index
+ count
- 1;
2052 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2055 if (def_index
> last_index
)
2058 def
= DF_DEFS_GET (def_index
);
2059 if (df_chain_problem_p (DF_DU_CHAIN
))
2060 df_chain_create (def
, use
);
2061 if (df_chain_problem_p (DF_UD_CHAIN
))
2062 df_chain_create (use
, def
);
2071 /* Create chains from reaching defs bitmaps for basic block BB. */
2074 df_chain_create_bb (unsigned int bb_index
)
2076 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
2077 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2081 bitmap_initialize (&cpy
, &bitmap_default_obstack
);
2082 bitmap_copy (&cpy
, &bb_info
->in
);
2083 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2085 /* Since we are going forwards, process the artificial uses first
2086 then the artificial defs second. */
2089 /* Create the chains for the artificial uses from the EH_USES at the
2090 beginning of the block. */
2092 /* Artificials are only hard regs. */
2093 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2094 df_chain_create_bb_process_use (&cpy
,
2095 df_get_artificial_uses (bb
->index
),
2099 df_rd_simulate_artificial_defs_at_top (bb
, &cpy
);
2101 /* Process the regular instructions next. */
2102 FOR_BB_INSNS (bb
, insn
)
2105 unsigned int uid
= INSN_UID (insn
);
2107 /* First scan the uses and link them up with the defs that remain
2108 in the cpy vector. */
2109 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_USES (uid
), 0);
2110 if (df
->changeable_flags
& DF_EQ_NOTES
)
2111 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2113 /* Since we are going forwards, process the defs second. */
2114 df_rd_simulate_one_insn (bb
, insn
, &cpy
);
2117 /* Create the chains for the artificial uses of the hard registers
2118 at the end of the block. */
2119 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2120 df_chain_create_bb_process_use (&cpy
,
2121 df_get_artificial_uses (bb
->index
),
2124 bitmap_clear (&cpy
);
2127 /* Create def-use chains from reaching use bitmaps for basic blocks
2131 df_chain_finalize (bitmap all_blocks
)
2133 unsigned int bb_index
;
2136 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2138 df_chain_create_bb (bb_index
);
2143 /* Free all storage associated with the problem. */
2146 df_chain_free (void)
2148 delete df_chain
->block_pool
;
2149 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2154 /* Debugging info. */
2157 df_chain_bb_dump (basic_block bb
, FILE *file
, bool top
)
2159 /* Artificials are only hard regs. */
2160 if (df
->changeable_flags
& DF_NO_HARD_REGS
)
2162 if (df_chain_problem_p (DF_UD_CHAIN
))
2167 ";; UD chains for artificial uses at %s\n",
2168 top
? "top" : "bottom");
2169 FOR_EACH_ARTIFICIAL_USE (use
, bb
->index
)
2170 if ((top
&& (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2171 || (!top
&& !(DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)))
2173 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2174 df_chain_dump (DF_REF_CHAIN (use
), file
);
2175 fprintf (file
, "\n");
2178 if (df_chain_problem_p (DF_DU_CHAIN
))
2183 ";; DU chains for artificial defs at %s\n",
2184 top
? "top" : "bottom");
2185 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
2186 if ((top
&& (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
2187 || (!top
&& !(DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)))
2189 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2190 df_chain_dump (DF_REF_CHAIN (def
), file
);
2191 fprintf (file
, "\n");
2197 df_chain_top_dump (basic_block bb
, FILE *file
)
2199 df_chain_bb_dump (bb
, file
, /*top=*/true);
2203 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2205 df_chain_bb_dump (bb
, file
, /*top=*/false);
2209 df_chain_insn_top_dump (const rtx_insn
*insn
, FILE *file
)
2211 if (df_chain_problem_p (DF_UD_CHAIN
) && INSN_P (insn
))
2213 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2216 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2217 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2218 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2219 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use
))
2220 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2222 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2223 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
2224 fprintf (file
, "read/write ");
2225 df_chain_dump (DF_REF_CHAIN (use
), file
);
2226 fprintf (file
, "\n");
2228 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
2229 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use
))
2230 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2232 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2233 df_chain_dump (DF_REF_CHAIN (use
), file
);
2234 fprintf (file
, "\n");
2240 df_chain_insn_bottom_dump (const rtx_insn
*insn
, FILE *file
)
2242 if (df_chain_problem_p (DF_DU_CHAIN
) && INSN_P (insn
))
2244 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2246 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2247 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2248 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2249 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def
))
2250 || !(df
->changeable_flags
& DF_NO_HARD_REGS
))
2252 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2253 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
2254 fprintf (file
, "read/write ");
2255 df_chain_dump (DF_REF_CHAIN (def
), file
);
2256 fprintf (file
, "\n");
2258 fprintf (file
, "\n");
2262 static struct df_problem problem_CHAIN
=
2264 DF_CHAIN
, /* Problem id. */
2265 DF_NONE
, /* Direction. */
2266 df_chain_alloc
, /* Allocate the problem specific data. */
2267 df_chain_reset
, /* Reset global information. */
2268 NULL
, /* Free basic block info. */
2269 NULL
, /* Local compute function. */
2270 NULL
, /* Init the solution specific data. */
2271 NULL
, /* Iterative solver. */
2272 NULL
, /* Confluence operator 0. */
2273 NULL
, /* Confluence operator n. */
2274 NULL
, /* Transfer function. */
2275 df_chain_finalize
, /* Finalize function. */
2276 df_chain_free
, /* Free all of the problem information. */
2277 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2278 NULL
, /* Debugging. */
2279 df_chain_top_dump
, /* Debugging start block. */
2280 df_chain_bottom_dump
, /* Debugging end block. */
2281 df_chain_insn_top_dump
, /* Debugging start insn. */
2282 df_chain_insn_bottom_dump
, /* Debugging end insn. */
2283 NULL
, /* Incremental solution verify start. */
2284 NULL
, /* Incremental solution verify end. */
2285 &problem_RD
, /* Dependent problem. */
2286 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
2287 TV_DF_CHAIN
, /* Timing variable. */
2288 false /* Reset blocks on dropping out of blocks_to_analyze. */
2292 /* Create a new DATAFLOW instance and add it to an existing instance
2293 of DF. The returned structure is what is used to get at the
2297 df_chain_add_problem (unsigned int chain_flags
)
2299 df_add_problem (&problem_CHAIN
);
2300 df_chain
->local_flags
= chain_flags
;
2301 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
2304 #undef df_chain_problem_p
2307 /*----------------------------------------------------------------------------
2308 WORD LEVEL LIVE REGISTERS
2310 Find the locations in the function where any use of a pseudo can
2311 reach in the backwards direction. In and out bitvectors are built
2312 for each basic block. We only track pseudo registers that have a
2313 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2314 contain two bits corresponding to each of the subwords.
2316 ----------------------------------------------------------------------------*/
2318 /* Private data used to verify the solution for this problem. */
2319 struct df_word_lr_problem_data
2321 /* An obstack for the bitmaps we need for this problem. */
2322 bitmap_obstack word_lr_bitmaps
;
2326 /* Free basic block info. */
2329 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2332 struct df_word_lr_bb_info
*bb_info
= (struct df_word_lr_bb_info
*) vbb_info
;
2335 bitmap_clear (&bb_info
->use
);
2336 bitmap_clear (&bb_info
->def
);
2337 bitmap_clear (&bb_info
->in
);
2338 bitmap_clear (&bb_info
->out
);
2343 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2344 not touched unless the block is new. */
2347 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2349 unsigned int bb_index
;
2352 struct df_word_lr_problem_data
*problem_data
2353 = XNEW (struct df_word_lr_problem_data
);
2355 df_word_lr
->problem_data
= problem_data
;
2357 df_grow_bb_info (df_word_lr
);
2359 /* Create the mapping from regnos to slots. This does not change
2360 unless the problem is destroyed and recreated. In particular, if
2361 we end up deleting the only insn that used a subreg, we do not
2362 want to redo the mapping because this would invalidate everything
2365 bitmap_obstack_initialize (&problem_data
->word_lr_bitmaps
);
2367 FOR_EACH_BB_FN (bb
, cfun
)
2368 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, bb
->index
);
2370 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
2371 bitmap_set_bit (df_word_lr
->out_of_date_transfer_functions
, EXIT_BLOCK
);
2373 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2375 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2377 /* When bitmaps are already initialized, just clear them. */
2378 if (bb_info
->use
.obstack
)
2380 bitmap_clear (&bb_info
->def
);
2381 bitmap_clear (&bb_info
->use
);
2385 bitmap_initialize (&bb_info
->use
, &problem_data
->word_lr_bitmaps
);
2386 bitmap_initialize (&bb_info
->def
, &problem_data
->word_lr_bitmaps
);
2387 bitmap_initialize (&bb_info
->in
, &problem_data
->word_lr_bitmaps
);
2388 bitmap_initialize (&bb_info
->out
, &problem_data
->word_lr_bitmaps
);
2392 df_word_lr
->optional_p
= true;
2396 /* Reset the global solution for recalculation. */
2399 df_word_lr_reset (bitmap all_blocks
)
2401 unsigned int bb_index
;
2404 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2406 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2407 gcc_assert (bb_info
);
2408 bitmap_clear (&bb_info
->in
);
2409 bitmap_clear (&bb_info
->out
);
2413 /* Examine REF, and if it is for a reg we're interested in, set or
2414 clear the bits corresponding to its subwords from the bitmap
2415 according to IS_SET. LIVE is the bitmap we should update. We do
2416 not track hard regs or pseudos of any size other than 2 *
2418 We return true if we changed the bitmap, or if we encountered a register
2419 we're not tracking. */
2422 df_word_lr_mark_ref (df_ref ref
, bool is_set
, regset live
)
2424 rtx orig_reg
= DF_REF_REG (ref
);
2426 machine_mode reg_mode
;
2428 /* Left at -1 for whole accesses. */
2429 int which_subword
= -1;
2430 bool changed
= false;
2432 if (GET_CODE (reg
) == SUBREG
)
2433 reg
= SUBREG_REG (orig_reg
);
2434 regno
= REGNO (reg
);
2435 reg_mode
= GET_MODE (reg
);
2436 if (regno
< FIRST_PSEUDO_REGISTER
2437 || GET_MODE_SIZE (reg_mode
) != 2 * UNITS_PER_WORD
)
2440 if (GET_CODE (orig_reg
) == SUBREG
2441 && df_read_modify_subreg_p (orig_reg
))
2443 gcc_assert (DF_REF_FLAGS_IS_SET (ref
, DF_REF_PARTIAL
));
2444 if (subreg_lowpart_p (orig_reg
))
2451 if (which_subword
!= 1)
2452 changed
|= bitmap_set_bit (live
, regno
* 2);
2453 if (which_subword
!= 0)
2454 changed
|= bitmap_set_bit (live
, regno
* 2 + 1);
2458 if (which_subword
!= 1)
2459 changed
|= bitmap_clear_bit (live
, regno
* 2);
2460 if (which_subword
!= 0)
2461 changed
|= bitmap_clear_bit (live
, regno
* 2 + 1);
2466 /* Compute local live register info for basic block BB. */
2469 df_word_lr_bb_local_compute (unsigned int bb_index
)
2471 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
2472 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2476 /* Ensure that artificial refs don't contain references to pseudos. */
2477 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
2478 gcc_assert (DF_REF_REGNO (def
) < FIRST_PSEUDO_REGISTER
);
2480 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
2481 gcc_assert (DF_REF_REGNO (use
) < FIRST_PSEUDO_REGISTER
);
2483 FOR_BB_INSNS_REVERSE (bb
, insn
)
2485 if (!NONDEBUG_INSN_P (insn
))
2488 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2489 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2490 /* If the def is to only part of the reg, it does
2491 not kill the other defs that reach here. */
2492 if (!(DF_REF_FLAGS (def
) & (DF_REF_CONDITIONAL
)))
2494 df_word_lr_mark_ref (def
, true, &bb_info
->def
);
2495 df_word_lr_mark_ref (def
, false, &bb_info
->use
);
2497 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2498 df_word_lr_mark_ref (use
, true, &bb_info
->use
);
2503 /* Compute local live register info for each basic block within BLOCKS. */
2506 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2508 unsigned int bb_index
;
2511 EXECUTE_IF_SET_IN_BITMAP (df_word_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2513 if (bb_index
== EXIT_BLOCK
)
2517 EXECUTE_IF_SET_IN_BITMAP (df
->exit_block_uses
, FIRST_PSEUDO_REGISTER
,
2522 df_word_lr_bb_local_compute (bb_index
);
2525 bitmap_clear (df_word_lr
->out_of_date_transfer_functions
);
2529 /* Initialize the solution vectors. */
2532 df_word_lr_init (bitmap all_blocks
)
2534 unsigned int bb_index
;
2537 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2539 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2540 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
2541 bitmap_clear (&bb_info
->out
);
2546 /* Confluence function that ignores fake edges. */
2549 df_word_lr_confluence_n (edge e
)
2551 bitmap op1
= &df_word_lr_get_bb_info (e
->src
->index
)->out
;
2552 bitmap op2
= &df_word_lr_get_bb_info (e
->dest
->index
)->in
;
2554 return bitmap_ior_into (op1
, op2
);
2558 /* Transfer function. */
2561 df_word_lr_transfer_function (int bb_index
)
2563 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb_index
);
2564 bitmap in
= &bb_info
->in
;
2565 bitmap out
= &bb_info
->out
;
2566 bitmap use
= &bb_info
->use
;
2567 bitmap def
= &bb_info
->def
;
2569 return bitmap_ior_and_compl (in
, use
, out
, def
);
2573 /* Free all storage associated with the problem. */
2576 df_word_lr_free (void)
2578 struct df_word_lr_problem_data
*problem_data
2579 = (struct df_word_lr_problem_data
*)df_word_lr
->problem_data
;
2581 if (df_word_lr
->block_info
)
2583 df_word_lr
->block_info_size
= 0;
2584 free (df_word_lr
->block_info
);
2585 df_word_lr
->block_info
= NULL
;
2588 BITMAP_FREE (df_word_lr
->out_of_date_transfer_functions
);
2589 bitmap_obstack_release (&problem_data
->word_lr_bitmaps
);
2590 free (problem_data
);
2595 /* Debugging info at top of bb. */
2598 df_word_lr_top_dump (basic_block bb
, FILE *file
)
2600 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2604 fprintf (file
, ";; blr in \t");
2605 df_print_word_regset (file
, &bb_info
->in
);
2606 fprintf (file
, ";; blr use \t");
2607 df_print_word_regset (file
, &bb_info
->use
);
2608 fprintf (file
, ";; blr def \t");
2609 df_print_word_regset (file
, &bb_info
->def
);
2613 /* Debugging info at bottom of bb. */
2616 df_word_lr_bottom_dump (basic_block bb
, FILE *file
)
2618 struct df_word_lr_bb_info
*bb_info
= df_word_lr_get_bb_info (bb
->index
);
2622 fprintf (file
, ";; blr out \t");
2623 df_print_word_regset (file
, &bb_info
->out
);
2627 /* All of the information associated with every instance of the problem. */
2629 static struct df_problem problem_WORD_LR
=
2631 DF_WORD_LR
, /* Problem id. */
2632 DF_BACKWARD
, /* Direction. */
2633 df_word_lr_alloc
, /* Allocate the problem specific data. */
2634 df_word_lr_reset
, /* Reset global information. */
2635 df_word_lr_free_bb_info
, /* Free basic block info. */
2636 df_word_lr_local_compute
, /* Local compute function. */
2637 df_word_lr_init
, /* Init the solution specific data. */
2638 df_worklist_dataflow
, /* Worklist solver. */
2639 NULL
, /* Confluence operator 0. */
2640 df_word_lr_confluence_n
, /* Confluence operator n. */
2641 df_word_lr_transfer_function
, /* Transfer function. */
2642 NULL
, /* Finalize function. */
2643 df_word_lr_free
, /* Free all of the problem information. */
2644 df_word_lr_free
, /* Remove this problem from the stack of dataflow problems. */
2645 NULL
, /* Debugging. */
2646 df_word_lr_top_dump
, /* Debugging start block. */
2647 df_word_lr_bottom_dump
, /* Debugging end block. */
2648 NULL
, /* Debugging start insn. */
2649 NULL
, /* Debugging end insn. */
2650 NULL
, /* Incremental solution verify start. */
2651 NULL
, /* Incremental solution verify end. */
2652 NULL
, /* Dependent problem. */
2653 sizeof (struct df_word_lr_bb_info
),/* Size of entry of block_info array. */
2654 TV_DF_WORD_LR
, /* Timing variable. */
2655 false /* Reset blocks on dropping out of blocks_to_analyze. */
2659 /* Create a new DATAFLOW instance and add it to an existing instance
2660 of DF. The returned structure is what is used to get at the
2664 df_word_lr_add_problem (void)
2666 df_add_problem (&problem_WORD_LR
);
2667 /* These will be initialized when df_scan_blocks processes each
2669 df_word_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (&df_bitmap_obstack
);
2673 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
2674 any bits, which is used by the caller to determine whether a set is
2675 necessary. We also return true if there are other reasons not to delete
2679 df_word_lr_simulate_defs (rtx_insn
*insn
, bitmap live
)
2681 bool changed
= false;
2684 FOR_EACH_INSN_DEF (def
, insn
)
2685 if (DF_REF_FLAGS (def
) & DF_REF_CONDITIONAL
)
2688 changed
|= df_word_lr_mark_ref (def
, false, live
);
2693 /* Simulate the effects of the uses of INSN on LIVE. */
2696 df_word_lr_simulate_uses (rtx_insn
*insn
, bitmap live
)
2700 FOR_EACH_INSN_USE (use
, insn
)
2701 df_word_lr_mark_ref (use
, true, live
);
2704 /*----------------------------------------------------------------------------
2705 This problem computes REG_DEAD and REG_UNUSED notes.
2706 ----------------------------------------------------------------------------*/
2709 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2711 df_note
->optional_p
= true;
2714 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
2716 df_print_note (const char *prefix
, rtx_insn
*insn
, rtx note
)
2720 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
2721 print_rtl (dump_file
, note
);
2722 fprintf (dump_file
, "\n");
2727 /* After reg-stack, the x86 floating point stack regs are difficult to
2728 analyze because of all of the pushes, pops and rotations. Thus, we
2729 just leave the notes alone. */
2733 df_ignore_stack_reg (int regno
)
2735 return regstack_completed
2736 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
2740 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
2747 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
2750 df_remove_dead_and_unused_notes (rtx_insn
*insn
)
2752 rtx
*pprev
= ®_NOTES (insn
);
2757 switch (REG_NOTE_KIND (link
))
2760 /* After reg-stack, we need to ignore any unused notes
2761 for the stack registers. */
2762 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2764 pprev
= &XEXP (link
, 1);
2769 rtx next
= XEXP (link
, 1);
2770 if (REG_DEAD_DEBUGGING
)
2771 df_print_note ("deleting: ", insn
, link
);
2772 free_EXPR_LIST_node (link
);
2773 *pprev
= link
= next
;
2778 /* After reg-stack, we need to ignore any unused notes
2779 for the stack registers. */
2780 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
2782 pprev
= &XEXP (link
, 1);
2787 rtx next
= XEXP (link
, 1);
2788 if (REG_DEAD_DEBUGGING
)
2789 df_print_note ("deleting: ", insn
, link
);
2790 free_EXPR_LIST_node (link
);
2791 *pprev
= link
= next
;
2796 pprev
= &XEXP (link
, 1);
2803 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2804 as the bitmap of currently live registers. */
2807 df_remove_dead_eq_notes (rtx_insn
*insn
, bitmap live
)
2809 rtx
*pprev
= ®_NOTES (insn
);
2814 switch (REG_NOTE_KIND (link
))
2819 /* Remove the notes that refer to dead registers. As we have at most
2820 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2821 so we need to purge the complete EQ_USES vector when removing
2822 the note using df_notes_rescan. */
2824 bool deleted
= false;
2826 FOR_EACH_INSN_EQ_USE (use
, insn
)
2827 if (DF_REF_REGNO (use
) > FIRST_PSEUDO_REGISTER
2829 && (DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
)
2830 && !bitmap_bit_p (live
, DF_REF_REGNO (use
))
2831 && loc_mentioned_in_p (DF_REF_LOC (use
), XEXP (link
, 0)))
2839 if (REG_DEAD_DEBUGGING
)
2840 df_print_note ("deleting: ", insn
, link
);
2841 next
= XEXP (link
, 1);
2842 free_EXPR_LIST_node (link
);
2843 *pprev
= link
= next
;
2844 df_notes_rescan (insn
);
2848 pprev
= &XEXP (link
, 1);
2855 pprev
= &XEXP (link
, 1);
2862 /* Set a NOTE_TYPE note for REG in INSN. */
2865 df_set_note (enum reg_note note_type
, rtx_insn
*insn
, rtx reg
)
2867 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2868 add_reg_note (insn
, note_type
, reg
);
2871 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2872 arguments. Return true if the register value described by MWS's
2873 mw_reg is known to be completely unused, and if mw_reg can therefore
2874 be used in a REG_UNUSED note. */
2877 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
2878 bitmap live
, bitmap artificial_uses
)
2882 /* If MWS describes a partial reference, create REG_UNUSED notes for
2883 individual hard registers. */
2884 if (mws
->flags
& DF_REF_PARTIAL
)
2887 /* Likewise if some part of the register is used. */
2888 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2889 if (bitmap_bit_p (live
, r
)
2890 || bitmap_bit_p (artificial_uses
, r
))
2893 gcc_assert (REG_P (mws
->mw_reg
));
2898 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2899 based on the bits in LIVE. Do not generate notes for registers in
2900 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
2901 not generated if the reg is both read and written by the
2906 df_set_unused_notes_for_mw (rtx_insn
*insn
, struct df_mw_hardreg
*mws
,
2907 bitmap live
, bitmap do_not_gen
,
2908 bitmap artificial_uses
,
2909 struct dead_debug_local
*debug
)
2913 if (REG_DEAD_DEBUGGING
&& dump_file
)
2914 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
2915 mws
->start_regno
, mws
->end_regno
);
2917 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
2919 unsigned int regno
= mws
->start_regno
;
2920 df_set_note (REG_UNUSED
, insn
, mws
->mw_reg
);
2921 dead_debug_insert_temp (debug
, regno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
2923 if (REG_DEAD_DEBUGGING
)
2924 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
2926 bitmap_set_bit (do_not_gen
, regno
);
2927 /* Only do this if the value is totally dead. */
2930 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2932 if (!bitmap_bit_p (live
, r
)
2933 && !bitmap_bit_p (artificial_uses
, r
))
2935 df_set_note (REG_UNUSED
, insn
, regno_reg_rtx
[r
]);
2936 dead_debug_insert_temp (debug
, r
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
2937 if (REG_DEAD_DEBUGGING
)
2938 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
2940 bitmap_set_bit (do_not_gen
, r
);
2945 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2946 arguments. Return true if the register value described by MWS's
2947 mw_reg is known to be completely dead, and if mw_reg can therefore
2948 be used in a REG_DEAD note. */
2951 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
2952 bitmap live
, bitmap artificial_uses
,
2957 /* If MWS describes a partial reference, create REG_DEAD notes for
2958 individual hard registers. */
2959 if (mws
->flags
& DF_REF_PARTIAL
)
2962 /* Likewise if some part of the register is not dead. */
2963 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
2964 if (bitmap_bit_p (live
, r
)
2965 || bitmap_bit_p (artificial_uses
, r
)
2966 || bitmap_bit_p (do_not_gen
, r
))
2969 gcc_assert (REG_P (mws
->mw_reg
));
2973 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2974 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
2975 from being set if the instruction both reads and writes the
2979 df_set_dead_notes_for_mw (rtx_insn
*insn
, struct df_mw_hardreg
*mws
,
2980 bitmap live
, bitmap do_not_gen
,
2981 bitmap artificial_uses
, bool *added_notes_p
)
2984 bool is_debug
= *added_notes_p
;
2986 *added_notes_p
= false;
2988 if (REG_DEAD_DEBUGGING
&& dump_file
)
2990 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
2991 mws
->start_regno
, mws
->end_regno
);
2992 df_print_regset (dump_file
, do_not_gen
);
2993 fprintf (dump_file
, " live =");
2994 df_print_regset (dump_file
, live
);
2995 fprintf (dump_file
, " artificial uses =");
2996 df_print_regset (dump_file
, artificial_uses
);
2999 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3003 *added_notes_p
= true;
3006 /* Add a dead note for the entire multi word register. */
3007 df_set_note (REG_DEAD
, insn
, mws
->mw_reg
);
3008 if (REG_DEAD_DEBUGGING
)
3009 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3013 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3014 if (!bitmap_bit_p (live
, r
)
3015 && !bitmap_bit_p (artificial_uses
, r
)
3016 && !bitmap_bit_p (do_not_gen
, r
))
3020 *added_notes_p
= true;
3023 df_set_note (REG_DEAD
, insn
, regno_reg_rtx
[r
]);
3024 if (REG_DEAD_DEBUGGING
)
3025 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3032 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3033 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3036 df_create_unused_note (rtx_insn
*insn
, df_ref def
,
3037 bitmap live
, bitmap artificial_uses
,
3038 struct dead_debug_local
*debug
)
3040 unsigned int dregno
= DF_REF_REGNO (def
);
3042 if (REG_DEAD_DEBUGGING
&& dump_file
)
3044 fprintf (dump_file
, " regular looking at def ");
3045 df_ref_debug (def
, dump_file
);
3048 if (!((DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3049 || bitmap_bit_p (live
, dregno
)
3050 || bitmap_bit_p (artificial_uses
, dregno
)
3051 || df_ignore_stack_reg (dregno
)))
3053 rtx reg
= (DF_REF_LOC (def
))
3054 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3055 df_set_note (REG_UNUSED
, insn
, reg
);
3056 dead_debug_insert_temp (debug
, dregno
, insn
, DEBUG_TEMP_AFTER_WITH_REG
);
3057 if (REG_DEAD_DEBUGGING
)
3058 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3065 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3066 info: lifetime, bb, and number of defs and uses for basic block
3067 BB. The three bitvectors are scratch regs used here. */
3070 df_note_bb_compute (unsigned int bb_index
,
3071 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3073 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
3076 struct dead_debug_local debug
;
3078 dead_debug_local_init (&debug
, NULL
, NULL
);
3080 bitmap_copy (live
, df_get_live_out (bb
));
3081 bitmap_clear (artificial_uses
);
3083 if (REG_DEAD_DEBUGGING
&& dump_file
)
3085 fprintf (dump_file
, "live at bottom ");
3086 df_print_regset (dump_file
, live
);
3089 /* Process the artificial defs and uses at the bottom of the block
3090 to begin processing. */
3091 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3093 if (REG_DEAD_DEBUGGING
&& dump_file
)
3094 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3096 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3097 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3100 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
3101 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3103 unsigned int regno
= DF_REF_REGNO (use
);
3104 bitmap_set_bit (live
, regno
);
3106 /* Notes are not generated for any of the artificial registers
3107 at the bottom of the block. */
3108 bitmap_set_bit (artificial_uses
, regno
);
3111 if (REG_DEAD_DEBUGGING
&& dump_file
)
3113 fprintf (dump_file
, "live before artificials out ");
3114 df_print_regset (dump_file
, live
);
3117 FOR_BB_INSNS_REVERSE (bb
, insn
)
3119 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
3126 debug_insn
= DEBUG_INSN_P (insn
);
3128 bitmap_clear (do_not_gen
);
3129 df_remove_dead_and_unused_notes (insn
);
3131 /* Process the defs. */
3134 if (REG_DEAD_DEBUGGING
&& dump_file
)
3136 fprintf (dump_file
, "processing call %d\n live =",
3138 df_print_regset (dump_file
, live
);
3141 /* We only care about real sets for calls. Clobbers cannot
3142 be depended on to really die. */
3143 FOR_EACH_INSN_INFO_MW (mw
, insn_info
)
3144 if ((DF_MWS_REG_DEF_P (mw
))
3145 && !df_ignore_stack_reg (mw
->start_regno
))
3146 df_set_unused_notes_for_mw (insn
, mw
, live
, do_not_gen
,
3147 artificial_uses
, &debug
);
3149 /* All of the defs except the return value are some sort of
3150 clobber. This code is for the return. */
3151 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
3153 unsigned int dregno
= DF_REF_REGNO (def
);
3154 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3156 df_create_unused_note (insn
,
3157 def
, live
, artificial_uses
, &debug
);
3158 bitmap_set_bit (do_not_gen
, dregno
);
3161 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3162 bitmap_clear_bit (live
, dregno
);
3168 FOR_EACH_INSN_INFO_MW (mw
, insn_info
)
3169 if (DF_MWS_REG_DEF_P (mw
))
3170 df_set_unused_notes_for_mw (insn
, mw
, live
, do_not_gen
,
3171 artificial_uses
, &debug
);
3173 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
3175 unsigned int dregno
= DF_REF_REGNO (def
);
3176 df_create_unused_note (insn
,
3177 def
, live
, artificial_uses
, &debug
);
3179 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3180 bitmap_set_bit (do_not_gen
, dregno
);
3182 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3183 bitmap_clear_bit (live
, dregno
);
3187 /* Process the uses. */
3188 FOR_EACH_INSN_INFO_MW (mw
, insn_info
)
3189 if (DF_MWS_REG_USE_P (mw
)
3190 && !df_ignore_stack_reg (mw
->start_regno
))
3192 bool really_add_notes
= debug_insn
!= 0;
3194 df_set_dead_notes_for_mw (insn
, mw
, live
, do_not_gen
,
3198 if (really_add_notes
)
3202 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
3204 unsigned int uregno
= DF_REF_REGNO (use
);
3206 if (REG_DEAD_DEBUGGING
&& dump_file
&& !debug_insn
)
3208 fprintf (dump_file
, " regular looking at use ");
3209 df_ref_debug (use
, dump_file
);
3212 if (!bitmap_bit_p (live
, uregno
))
3218 /* We won't add REG_UNUSED or REG_DEAD notes for
3219 these, so we don't have to mess with them in
3220 debug insns either. */
3221 if (!bitmap_bit_p (artificial_uses
, uregno
)
3222 && !df_ignore_stack_reg (uregno
))
3223 dead_debug_add (&debug
, use
, uregno
);
3229 dead_debug_insert_temp (&debug
, uregno
, insn
,
3230 DEBUG_TEMP_BEFORE_WITH_REG
);
3232 if ( (!(DF_REF_FLAGS (use
)
3233 & (DF_REF_MW_HARDREG
| DF_REF_READ_WRITE
)))
3234 && (!bitmap_bit_p (do_not_gen
, uregno
))
3235 && (!bitmap_bit_p (artificial_uses
, uregno
))
3236 && (!df_ignore_stack_reg (uregno
)))
3238 rtx reg
= (DF_REF_LOC (use
))
3239 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3240 df_set_note (REG_DEAD
, insn
, reg
);
3242 if (REG_DEAD_DEBUGGING
)
3243 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3245 /* This register is now live. */
3246 bitmap_set_bit (live
, uregno
);
3250 df_remove_dead_eq_notes (insn
, live
);
3252 if (debug_insn
== -1)
3254 /* ??? We could probably do better here, replacing dead
3255 registers with their definitions. */
3256 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3257 df_insn_rescan_debug_internal (insn
);
3261 dead_debug_local_finish (&debug
, NULL
);
3265 /* Compute register info: lifetime, bb, and number of defs and uses. */
3267 df_note_compute (bitmap all_blocks
)
3269 unsigned int bb_index
;
3271 bitmap_head live
, do_not_gen
, artificial_uses
;
3273 bitmap_initialize (&live
, &df_bitmap_obstack
);
3274 bitmap_initialize (&do_not_gen
, &df_bitmap_obstack
);
3275 bitmap_initialize (&artificial_uses
, &df_bitmap_obstack
);
3277 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3279 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3280 pseudos in debug insns because we don't always (re)visit blocks
3281 with death points after visiting dead uses. Even changing this
3282 loop to postorder would still leave room for visiting a death
3283 point before visiting a subsequent debug use. */
3284 df_note_bb_compute (bb_index
, &live
, &do_not_gen
, &artificial_uses
);
3287 bitmap_clear (&live
);
3288 bitmap_clear (&do_not_gen
);
3289 bitmap_clear (&artificial_uses
);
3293 /* Free all storage associated with the problem. */
3302 /* All of the information associated every instance of the problem. */
3304 static struct df_problem problem_NOTE
=
3306 DF_NOTE
, /* Problem id. */
3307 DF_NONE
, /* Direction. */
3308 df_note_alloc
, /* Allocate the problem specific data. */
3309 NULL
, /* Reset global information. */
3310 NULL
, /* Free basic block info. */
3311 df_note_compute
, /* Local compute function. */
3312 NULL
, /* Init the solution specific data. */
3313 NULL
, /* Iterative solver. */
3314 NULL
, /* Confluence operator 0. */
3315 NULL
, /* Confluence operator n. */
3316 NULL
, /* Transfer function. */
3317 NULL
, /* Finalize function. */
3318 df_note_free
, /* Free all of the problem information. */
3319 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3320 NULL
, /* Debugging. */
3321 NULL
, /* Debugging start block. */
3322 NULL
, /* Debugging end block. */
3323 NULL
, /* Debugging start insn. */
3324 NULL
, /* Debugging end insn. */
3325 NULL
, /* Incremental solution verify start. */
3326 NULL
, /* Incremental solution verify end. */
3327 &problem_LR
, /* Dependent problem. */
3328 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
3329 TV_DF_NOTE
, /* Timing variable. */
3330 false /* Reset blocks on dropping out of blocks_to_analyze. */
3334 /* Create a new DATAFLOW instance and add it to an existing instance
3335 of DF. The returned structure is what is used to get at the
3339 df_note_add_problem (void)
3341 df_add_problem (&problem_NOTE
);
3347 /*----------------------------------------------------------------------------
3348 Functions for simulating the effects of single insns.
3350 You can either simulate in the forwards direction, starting from
3351 the top of a block or the backwards direction from the end of the
3352 block. If you go backwards, defs are examined first to clear bits,
3353 then uses are examined to set bits. If you go forwards, defs are
3354 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3355 are examined to clear bits. In either case, the result of examining
3356 a def can be undone (respectively by a use or a REG_UNUSED note).
3358 If you start at the top of the block, use one of DF_LIVE_IN or
3359 DF_LR_IN. If you start at the bottom of the block use one of
3360 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3361 THEY WILL BE DESTROYED.
3362 ----------------------------------------------------------------------------*/
3365 /* Find the set of DEFs for INSN. */
3368 df_simulate_find_defs (rtx_insn
*insn
, bitmap defs
)
3372 FOR_EACH_INSN_DEF (def
, insn
)
3373 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3376 /* Find the set of uses for INSN. This includes partial defs. */
3379 df_simulate_find_uses (rtx_insn
*insn
, bitmap uses
)
3382 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
3384 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
3385 if (DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3386 bitmap_set_bit (uses
, DF_REF_REGNO (def
));
3387 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
3388 bitmap_set_bit (uses
, DF_REF_REGNO (use
));
3391 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3394 df_simulate_find_noclobber_defs (rtx_insn
*insn
, bitmap defs
)
3398 FOR_EACH_INSN_DEF (def
, insn
)
3399 if (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
3400 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3404 /* Simulate the effects of the defs of INSN on LIVE. */
3407 df_simulate_defs (rtx_insn
*insn
, bitmap live
)
3411 FOR_EACH_INSN_DEF (def
, insn
)
3413 unsigned int dregno
= DF_REF_REGNO (def
);
3415 /* If the def is to only part of the reg, it does
3416 not kill the other defs that reach here. */
3417 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3418 bitmap_clear_bit (live
, dregno
);
3423 /* Simulate the effects of the uses of INSN on LIVE. */
3426 df_simulate_uses (rtx_insn
*insn
, bitmap live
)
3430 if (DEBUG_INSN_P (insn
))
3433 FOR_EACH_INSN_USE (use
, insn
)
3434 /* Add use to set of uses in this BB. */
3435 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3439 /* Add back the always live regs in BB to LIVE. */
3442 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3444 /* These regs are considered always live so if they end up dying
3445 because of some def, we need to bring the back again. */
3446 if (bb_has_eh_pred (bb
))
3447 bitmap_ior_into (live
, &df
->eh_block_artificial_uses
);
3449 bitmap_ior_into (live
, &df
->regular_block_artificial_uses
);
3453 /*----------------------------------------------------------------------------
3454 The following three functions are used only for BACKWARDS scanning:
3455 i.e. they process the defs before the uses.
3457 df_simulate_initialize_backwards should be called first with a
3458 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3459 df_simulate_one_insn_backwards should be called for each insn in
3460 the block, starting with the last one. Finally,
3461 df_simulate_finalize_backwards can be called to get a new value
3462 of the sets at the top of the block (this is rarely used).
3463 ----------------------------------------------------------------------------*/
3465 /* Apply the artificial uses and defs at the end of BB in a backwards
3469 df_simulate_initialize_backwards (basic_block bb
, bitmap live
)
3472 int bb_index
= bb
->index
;
3474 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3475 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3476 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3478 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
3479 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3480 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3484 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3487 df_simulate_one_insn_backwards (basic_block bb
, rtx_insn
*insn
, bitmap live
)
3489 if (!NONDEBUG_INSN_P (insn
))
3492 df_simulate_defs (insn
, live
);
3493 df_simulate_uses (insn
, live
);
3494 df_simulate_fixup_sets (bb
, live
);
3498 /* Apply the artificial uses and defs at the top of BB in a backwards
3502 df_simulate_finalize_backwards (basic_block bb
, bitmap live
)
3508 int bb_index
= bb
->index
;
3510 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3511 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3512 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3515 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
3516 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3517 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3520 /*----------------------------------------------------------------------------
3521 The following three functions are used only for FORWARDS scanning:
3522 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3523 Thus it is important to add the DF_NOTES problem to the stack of
3524 problems computed before using these functions.
3526 df_simulate_initialize_forwards should be called first with a
3527 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3528 df_simulate_one_insn_forwards should be called for each insn in
3529 the block, starting with the first one.
3530 ----------------------------------------------------------------------------*/
3532 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3533 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3537 df_simulate_initialize_forwards (basic_block bb
, bitmap live
)
3540 int bb_index
= bb
->index
;
3542 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
3543 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3544 bitmap_set_bit (live
, DF_REF_REGNO (def
));
3547 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3550 df_simulate_one_insn_forwards (basic_block bb
, rtx_insn
*insn
, bitmap live
)
3553 if (! INSN_P (insn
))
3556 /* Make sure that DF_NOTE really is an active df problem. */
3557 gcc_assert (df_note
);
3559 /* Note that this is the opposite as how the problem is defined, because
3560 in the LR problem defs _kill_ liveness. However, they do so backwards,
3561 while here the scan is performed forwards! So, first assume that the
3562 def is live, and if this is not true REG_UNUSED notes will rectify the
3564 df_simulate_find_noclobber_defs (insn
, live
);
3566 /* Clear all of the registers that go dead. */
3567 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3569 switch (REG_NOTE_KIND (link
))
3574 rtx reg
= XEXP (link
, 0);
3575 bitmap_clear_range (live
, REGNO (reg
), REG_NREGS (reg
));
3582 df_simulate_fixup_sets (bb
, live
);
3585 /* Used by the next two functions to encode information about the
3586 memory references we found. */
3587 #define MEMREF_NORMAL 1
3588 #define MEMREF_VOLATILE 2
3590 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3593 find_memory (rtx_insn
*insn
)
3596 subrtx_iterator::array_type array
;
3597 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
3599 const_rtx x
= *iter
;
3600 if (GET_CODE (x
) == ASM_OPERANDS
&& MEM_VOLATILE_P (x
))
3601 flags
|= MEMREF_VOLATILE
;
3604 if (MEM_VOLATILE_P (x
))
3605 flags
|= MEMREF_VOLATILE
;
3606 else if (!MEM_READONLY_P (x
))
3607 flags
|= MEMREF_NORMAL
;
3613 /* A subroutine of can_move_insns_across_p called through note_stores.
3614 DATA points to an integer in which we set either the bit for
3615 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3619 find_memory_stores (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
,
3620 void *data ATTRIBUTE_UNUSED
)
3622 int *pflags
= (int *)data
;
3623 if (GET_CODE (x
) == SUBREG
)
3625 /* Treat stores to SP as stores to memory, this will prevent problems
3626 when there are references to the stack frame. */
3627 if (x
== stack_pointer_rtx
)
3628 *pflags
|= MEMREF_VOLATILE
;
3631 *pflags
|= MEM_VOLATILE_P (x
) ? MEMREF_VOLATILE
: MEMREF_NORMAL
;
3634 /* Scan BB backwards, using df_simulate functions to keep track of
3635 lifetimes, up to insn POINT. The result is stored in LIVE. */
3638 simulate_backwards_to_point (basic_block bb
, regset live
, rtx point
)
3641 bitmap_copy (live
, df_get_live_out (bb
));
3642 df_simulate_initialize_backwards (bb
, live
);
3644 /* Scan and update life information until we reach the point we're
3646 for (insn
= BB_END (bb
); insn
!= point
; insn
= PREV_INSN (insn
))
3647 df_simulate_one_insn_backwards (bb
, insn
, live
);
3650 /* Return true if it is safe to move a group of insns, described by
3651 the range FROM to TO, backwards across another group of insns,
3652 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
3653 are no insns between ACROSS_TO and FROM, but they may be in
3654 different basic blocks; MERGE_BB is the block from which the
3655 insns will be moved. The caller must pass in a regset MERGE_LIVE
3656 which specifies the registers live after TO.
3658 This function may be called in one of two cases: either we try to
3659 move identical instructions from all successor blocks into their
3660 predecessor, or we try to move from only one successor block. If
3661 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3662 the second case. It should contain a set of registers live at the
3663 end of ACROSS_TO which must not be clobbered by moving the insns.
3664 In that case, we're also more careful about moving memory references
3667 We return false if it is not safe to move the entire group, but it
3668 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
3669 is set to point at the last moveable insn in such a case. */
3672 can_move_insns_across (rtx_insn
*from
, rtx_insn
*to
,
3673 rtx_insn
*across_from
, rtx_insn
*across_to
,
3674 basic_block merge_bb
, regset merge_live
,
3675 regset other_branch_live
, rtx_insn
**pmove_upto
)
3677 rtx_insn
*insn
, *next
, *max_to
;
3678 bitmap merge_set
, merge_use
, local_merge_live
;
3679 bitmap test_set
, test_use
;
3680 unsigned i
, fail
= 0;
3682 int memrefs_in_across
= 0;
3683 int mem_sets_in_across
= 0;
3684 bool trapping_insns_in_across
= false;
3686 if (pmove_upto
!= NULL
)
3689 /* Find real bounds, ignoring debug insns. */
3690 while (!NONDEBUG_INSN_P (from
) && from
!= to
)
3691 from
= NEXT_INSN (from
);
3692 while (!NONDEBUG_INSN_P (to
) && from
!= to
)
3693 to
= PREV_INSN (to
);
3695 for (insn
= across_to
; ; insn
= next
)
3699 if (RTL_CONST_OR_PURE_CALL_P (insn
))
3700 /* Pure functions can read from memory. Const functions can
3701 read from arguments that the ABI has forced onto the stack.
3702 Neither sort of read can be volatile. */
3703 memrefs_in_across
|= MEMREF_NORMAL
;
3706 memrefs_in_across
|= MEMREF_VOLATILE
;
3707 mem_sets_in_across
|= MEMREF_VOLATILE
;
3710 if (NONDEBUG_INSN_P (insn
))
3712 if (volatile_insn_p (PATTERN (insn
)))
3714 memrefs_in_across
|= find_memory (insn
);
3715 note_stores (PATTERN (insn
), find_memory_stores
,
3716 &mem_sets_in_across
);
3717 /* This is used just to find sets of the stack pointer. */
3718 memrefs_in_across
|= mem_sets_in_across
;
3719 trapping_insns_in_across
|= may_trap_p (PATTERN (insn
));
3721 next
= PREV_INSN (insn
);
3722 if (insn
== across_from
)
3727 MERGE_SET = set of registers set in MERGE_BB
3728 MERGE_USE = set of registers used in MERGE_BB and live at its top
3729 MERGE_LIVE = set of registers live at the point inside the MERGE
3730 range that we've reached during scanning
3731 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3732 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3733 and live before ACROSS_FROM. */
3735 merge_set
= BITMAP_ALLOC (®_obstack
);
3736 merge_use
= BITMAP_ALLOC (®_obstack
);
3737 local_merge_live
= BITMAP_ALLOC (®_obstack
);
3738 test_set
= BITMAP_ALLOC (®_obstack
);
3739 test_use
= BITMAP_ALLOC (®_obstack
);
3741 /* Compute the set of registers set and used in the ACROSS range. */
3742 if (other_branch_live
!= NULL
)
3743 bitmap_copy (test_use
, other_branch_live
);
3744 df_simulate_initialize_backwards (merge_bb
, test_use
);
3745 for (insn
= across_to
; ; insn
= next
)
3747 if (NONDEBUG_INSN_P (insn
))
3749 df_simulate_find_defs (insn
, test_set
);
3750 df_simulate_defs (insn
, test_use
);
3751 df_simulate_uses (insn
, test_use
);
3753 next
= PREV_INSN (insn
);
3754 if (insn
== across_from
)
3758 /* Compute an upper bound for the amount of insns moved, by finding
3759 the first insn in MERGE that sets a register in TEST_USE, or uses
3760 a register in TEST_SET. We also check for calls, trapping operations,
3761 and memory references. */
3763 for (insn
= from
; ; insn
= next
)
3767 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3769 if (NONDEBUG_INSN_P (insn
))
3771 if (may_trap_or_fault_p (PATTERN (insn
))
3772 && (trapping_insns_in_across
3773 || other_branch_live
!= NULL
3774 || volatile_insn_p (PATTERN (insn
))))
3777 /* We cannot move memory stores past each other, or move memory
3778 reads past stores, at least not without tracking them and
3779 calling true_dependence on every pair.
3781 If there is no other branch and no memory references or
3782 sets in the ACROSS range, we can move memory references
3783 freely, even volatile ones.
3785 Otherwise, the rules are as follows: volatile memory
3786 references and stores can't be moved at all, and any type
3787 of memory reference can't be moved if there are volatile
3788 accesses or stores in the ACROSS range. That leaves
3789 normal reads, which can be moved, as the trapping case is
3790 dealt with elsewhere. */
3791 if (other_branch_live
!= NULL
|| memrefs_in_across
!= 0)
3793 int mem_ref_flags
= 0;
3794 int mem_set_flags
= 0;
3795 note_stores (PATTERN (insn
), find_memory_stores
, &mem_set_flags
);
3796 mem_ref_flags
= find_memory (insn
);
3797 /* Catch sets of the stack pointer. */
3798 mem_ref_flags
|= mem_set_flags
;
3800 if ((mem_ref_flags
| mem_set_flags
) & MEMREF_VOLATILE
)
3802 if ((memrefs_in_across
& MEMREF_VOLATILE
) && mem_ref_flags
!= 0)
3804 if (mem_set_flags
!= 0
3805 || (mem_sets_in_across
!= 0 && mem_ref_flags
!= 0))
3808 df_simulate_find_uses (insn
, merge_use
);
3809 /* We're only interested in uses which use a value live at
3810 the top, not one previously set in this block. */
3811 bitmap_and_compl_into (merge_use
, merge_set
);
3812 df_simulate_find_defs (insn
, merge_set
);
3813 if (bitmap_intersect_p (merge_set
, test_use
)
3814 || bitmap_intersect_p (merge_use
, test_set
))
3816 if (!HAVE_cc0
|| !sets_cc0_p (insn
))
3819 next
= NEXT_INSN (insn
);
3826 if (max_to
== NULL_RTX
|| (fail
&& pmove_upto
== NULL
))
3829 /* Now, lower this upper bound by also taking into account that
3830 a range of insns moved across ACROSS must not leave a register
3831 live at the end that will be clobbered in ACROSS. We need to
3832 find a point where TEST_SET & LIVE == 0.
3834 Insns in the MERGE range that set registers which are also set
3835 in the ACROSS range may still be moved as long as we also move
3836 later insns which use the results of the set, and make the
3837 register dead again. This is verified by the condition stated
3838 above. We only need to test it for registers that are set in
3841 MERGE_LIVE is provided by the caller and holds live registers after
3843 bitmap_copy (local_merge_live
, merge_live
);
3844 for (insn
= to
; insn
!= max_to
; insn
= PREV_INSN (insn
))
3845 df_simulate_one_insn_backwards (merge_bb
, insn
, local_merge_live
);
3847 /* We're not interested in registers that aren't set in the moved
3849 bitmap_and_into (local_merge_live
, merge_set
);
3852 if (NONDEBUG_INSN_P (insn
))
3854 if (!bitmap_intersect_p (test_set
, local_merge_live
)
3855 && (!HAVE_cc0
|| !sets_cc0_p (insn
)))
3861 df_simulate_one_insn_backwards (merge_bb
, insn
,
3869 insn
= PREV_INSN (insn
);
3876 *pmove_upto
= max_to
;
3878 /* For small register class machines, don't lengthen lifetimes of
3879 hard registers before reload. */
3880 if (! reload_completed
3881 && targetm
.small_register_classes_for_mode_p (VOIDmode
))
3883 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
3885 if (i
< FIRST_PSEUDO_REGISTER
3887 && ! global_regs
[i
])
3896 BITMAP_FREE (merge_set
);
3897 BITMAP_FREE (merge_use
);
3898 BITMAP_FREE (local_merge_live
);
3899 BITMAP_FREE (test_set
);
3900 BITMAP_FREE (test_use
);
3906 /*----------------------------------------------------------------------------
3907 MULTIPLE DEFINITIONS
3909 Find the locations in the function reached by multiple definition sites
3910 for a live pseudo. In and out bitvectors are built for each basic
3911 block. They are restricted for efficiency to live registers.
3913 The gen and kill sets for the problem are obvious. Together they
3914 include all defined registers in a basic block; the gen set includes
3915 registers where a partial or conditional or may-clobber definition is
3916 last in the BB, while the kill set includes registers with a complete
3917 definition coming last. However, the computation of the dataflow
3918 itself is interesting.
3920 The idea behind it comes from SSA form's iterated dominance frontier
3921 criterion for inserting PHI functions. Just like in that case, we can use
3922 the dominance frontier to find places where multiple definitions meet;
3923 a register X defined in a basic block BB1 has multiple definitions in
3924 basic blocks in BB1's dominance frontier.
3926 So, the in-set of a basic block BB2 is not just the union of the
3927 out-sets of BB2's predecessors, but includes some more bits that come
3928 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3929 the previous paragraph). I called this set the init-set of BB2.
3931 (Note: I actually use the kill-set only to build the init-set.
3932 gen bits are anyway propagated from BB1 to BB2 by dataflow).
3934 For example, if you have
3938 if <...> goto BB2 else goto BB3;
3946 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3947 init-set of BB3 includes r10 and r12, but not r11. Note that we do
3948 not need to iterate the dominance frontier, because we do not insert
3949 anything like PHI functions there! Instead, dataflow will take care of
3950 propagating the information to BB3's successors.
3951 ---------------------------------------------------------------------------*/
3953 /* Private data used to verify the solution for this problem. */
3954 struct df_md_problem_data
3956 /* An obstack for the bitmaps we need for this problem. */
3957 bitmap_obstack md_bitmaps
;
3960 /* Scratch var used by transfer functions. This is used to do md analysis
3961 only for live registers. */
3962 static bitmap_head df_md_scratch
;
3966 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
3969 struct df_md_bb_info
*bb_info
= (struct df_md_bb_info
*) vbb_info
;
3972 bitmap_clear (&bb_info
->kill
);
3973 bitmap_clear (&bb_info
->gen
);
3974 bitmap_clear (&bb_info
->init
);
3975 bitmap_clear (&bb_info
->in
);
3976 bitmap_clear (&bb_info
->out
);
3981 /* Allocate or reset bitmaps for DF_MD. The solution bits are
3982 not touched unless the block is new. */
3985 df_md_alloc (bitmap all_blocks
)
3987 unsigned int bb_index
;
3989 struct df_md_problem_data
*problem_data
;
3991 df_grow_bb_info (df_md
);
3992 if (df_md
->problem_data
)
3993 problem_data
= (struct df_md_problem_data
*) df_md
->problem_data
;
3996 problem_data
= XNEW (struct df_md_problem_data
);
3997 df_md
->problem_data
= problem_data
;
3998 bitmap_obstack_initialize (&problem_data
->md_bitmaps
);
4000 bitmap_initialize (&df_md_scratch
, &problem_data
->md_bitmaps
);
4002 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4004 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4005 /* When bitmaps are already initialized, just clear them. */
4006 if (bb_info
->init
.obstack
)
4008 bitmap_clear (&bb_info
->init
);
4009 bitmap_clear (&bb_info
->gen
);
4010 bitmap_clear (&bb_info
->kill
);
4011 bitmap_clear (&bb_info
->in
);
4012 bitmap_clear (&bb_info
->out
);
4016 bitmap_initialize (&bb_info
->init
, &problem_data
->md_bitmaps
);
4017 bitmap_initialize (&bb_info
->gen
, &problem_data
->md_bitmaps
);
4018 bitmap_initialize (&bb_info
->kill
, &problem_data
->md_bitmaps
);
4019 bitmap_initialize (&bb_info
->in
, &problem_data
->md_bitmaps
);
4020 bitmap_initialize (&bb_info
->out
, &problem_data
->md_bitmaps
);
4024 df_md
->optional_p
= true;
4027 /* Add the effect of the top artificial defs of BB to the multiple definitions
4031 df_md_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_md
)
4033 int bb_index
= bb
->index
;
4035 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
4036 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4038 unsigned int dregno
= DF_REF_REGNO (def
);
4039 if (DF_REF_FLAGS (def
)
4040 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4041 bitmap_set_bit (local_md
, dregno
);
4043 bitmap_clear_bit (local_md
, dregno
);
4048 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4052 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx_insn
*insn
,
4057 FOR_EACH_INSN_DEF (def
, insn
)
4059 unsigned int dregno
= DF_REF_REGNO (def
);
4060 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4061 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4063 if (DF_REF_FLAGS (def
)
4064 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4065 bitmap_set_bit (local_md
, DF_REF_ID (def
));
4067 bitmap_clear_bit (local_md
, DF_REF_ID (def
));
4073 df_md_bb_local_compute_process_def (struct df_md_bb_info
*bb_info
,
4077 bitmap_clear (&seen_in_insn
);
4079 for (; def
; def
= DF_REF_NEXT_LOC (def
))
4081 unsigned int dregno
= DF_REF_REGNO (def
);
4082 if (((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4083 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4084 && top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
4086 if (!bitmap_bit_p (&seen_in_insn
, dregno
))
4088 if (DF_REF_FLAGS (def
)
4089 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4091 bitmap_set_bit (&bb_info
->gen
, dregno
);
4092 bitmap_clear_bit (&bb_info
->kill
, dregno
);
4096 /* When we find a clobber and a regular def,
4097 make sure the regular def wins. */
4098 bitmap_set_bit (&seen_in_insn
, dregno
);
4099 bitmap_set_bit (&bb_info
->kill
, dregno
);
4100 bitmap_clear_bit (&bb_info
->gen
, dregno
);
4108 /* Compute local multiple def info for basic block BB. */
4111 df_md_bb_local_compute (unsigned int bb_index
)
4113 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
4114 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4117 /* Artificials are only hard regs. */
4118 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4119 df_md_bb_local_compute_process_def (bb_info
,
4120 df_get_artificial_defs (bb_index
),
4123 FOR_BB_INSNS (bb
, insn
)
4125 unsigned int uid
= INSN_UID (insn
);
4129 df_md_bb_local_compute_process_def (bb_info
, DF_INSN_UID_DEFS (uid
), 0);
4132 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4133 df_md_bb_local_compute_process_def (bb_info
,
4134 df_get_artificial_defs (bb_index
),
4138 /* Compute local reaching def info for each basic block within BLOCKS. */
4141 df_md_local_compute (bitmap all_blocks
)
4143 unsigned int bb_index
, df_bb_index
;
4144 bitmap_iterator bi1
, bi2
;
4146 bitmap_head
*frontiers
;
4148 bitmap_initialize (&seen_in_insn
, &bitmap_default_obstack
);
4150 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4152 df_md_bb_local_compute (bb_index
);
4155 bitmap_clear (&seen_in_insn
);
4157 frontiers
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
4158 FOR_ALL_BB_FN (bb
, cfun
)
4159 bitmap_initialize (&frontiers
[bb
->index
], &bitmap_default_obstack
);
4161 compute_dominance_frontiers (frontiers
);
4163 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4164 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4166 bitmap kill
= &df_md_get_bb_info (bb_index
)->kill
;
4167 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[bb_index
], 0, df_bb_index
, bi2
)
4169 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, df_bb_index
);
4170 if (bitmap_bit_p (all_blocks
, df_bb_index
))
4171 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index
)->init
, kill
,
4172 df_get_live_in (bb
));
4176 FOR_ALL_BB_FN (bb
, cfun
)
4177 bitmap_clear (&frontiers
[bb
->index
]);
4182 /* Reset the global solution for recalculation. */
4185 df_md_reset (bitmap all_blocks
)
4187 unsigned int bb_index
;
4190 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4192 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4193 gcc_assert (bb_info
);
4194 bitmap_clear (&bb_info
->in
);
4195 bitmap_clear (&bb_info
->out
);
4200 df_md_transfer_function (int bb_index
)
4202 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
4203 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4204 bitmap in
= &bb_info
->in
;
4205 bitmap out
= &bb_info
->out
;
4206 bitmap gen
= &bb_info
->gen
;
4207 bitmap kill
= &bb_info
->kill
;
4209 /* We need to use a scratch set here so that the value returned from this
4210 function invocation properly reflects whether the sets changed in a
4211 significant way; i.e. not just because the live set was anded in. */
4212 bitmap_and (&df_md_scratch
, gen
, df_get_live_out (bb
));
4214 /* Multiple definitions of a register are not relevant if it is not
4215 live. Thus we trim the result to the places where it is live. */
4216 bitmap_and_into (in
, df_get_live_in (bb
));
4218 return bitmap_ior_and_compl (out
, &df_md_scratch
, in
, kill
);
4221 /* Initialize the solution bit vectors for problem. */
4224 df_md_init (bitmap all_blocks
)
4226 unsigned int bb_index
;
4229 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4231 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4233 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4234 df_md_transfer_function (bb_index
);
4239 df_md_confluence_0 (basic_block bb
)
4241 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4242 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4245 /* In of target gets or of out of source. */
4248 df_md_confluence_n (edge e
)
4250 bitmap op1
= &df_md_get_bb_info (e
->dest
->index
)->in
;
4251 bitmap op2
= &df_md_get_bb_info (e
->src
->index
)->out
;
4253 if (e
->flags
& EDGE_FAKE
)
4256 if (e
->flags
& EDGE_EH
)
4257 return bitmap_ior_and_compl_into (op1
, op2
,
4258 regs_invalidated_by_call_regset
);
4260 return bitmap_ior_into (op1
, op2
);
4263 /* Free all storage associated with the problem. */
4268 struct df_md_problem_data
*problem_data
4269 = (struct df_md_problem_data
*) df_md
->problem_data
;
4271 bitmap_obstack_release (&problem_data
->md_bitmaps
);
4272 free (problem_data
);
4273 df_md
->problem_data
= NULL
;
4275 df_md
->block_info_size
= 0;
4276 free (df_md
->block_info
);
4277 df_md
->block_info
= NULL
;
4282 /* Debugging info at top of bb. */
4285 df_md_top_dump (basic_block bb
, FILE *file
)
4287 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4291 fprintf (file
, ";; md in \t");
4292 df_print_regset (file
, &bb_info
->in
);
4293 fprintf (file
, ";; md init \t");
4294 df_print_regset (file
, &bb_info
->init
);
4295 fprintf (file
, ";; md gen \t");
4296 df_print_regset (file
, &bb_info
->gen
);
4297 fprintf (file
, ";; md kill \t");
4298 df_print_regset (file
, &bb_info
->kill
);
4301 /* Debugging info at bottom of bb. */
4304 df_md_bottom_dump (basic_block bb
, FILE *file
)
4306 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4310 fprintf (file
, ";; md out \t");
4311 df_print_regset (file
, &bb_info
->out
);
4314 static struct df_problem problem_MD
=
4316 DF_MD
, /* Problem id. */
4317 DF_FORWARD
, /* Direction. */
4318 df_md_alloc
, /* Allocate the problem specific data. */
4319 df_md_reset
, /* Reset global information. */
4320 df_md_free_bb_info
, /* Free basic block info. */
4321 df_md_local_compute
, /* Local compute function. */
4322 df_md_init
, /* Init the solution specific data. */
4323 df_worklist_dataflow
, /* Worklist solver. */
4324 df_md_confluence_0
, /* Confluence operator 0. */
4325 df_md_confluence_n
, /* Confluence operator n. */
4326 df_md_transfer_function
, /* Transfer function. */
4327 NULL
, /* Finalize function. */
4328 df_md_free
, /* Free all of the problem information. */
4329 df_md_free
, /* Remove this problem from the stack of dataflow problems. */
4330 NULL
, /* Debugging. */
4331 df_md_top_dump
, /* Debugging start block. */
4332 df_md_bottom_dump
, /* Debugging end block. */
4333 NULL
, /* Debugging start insn. */
4334 NULL
, /* Debugging end insn. */
4335 NULL
, /* Incremental solution verify start. */
4336 NULL
, /* Incremental solution verify end. */
4337 NULL
, /* Dependent problem. */
4338 sizeof (struct df_md_bb_info
),/* Size of entry of block_info array. */
4339 TV_DF_MD
, /* Timing variable. */
4340 false /* Reset blocks on dropping out of blocks_to_analyze. */
4343 /* Create a new MD instance and add it to the existing instance
4347 df_md_add_problem (void)
4349 df_add_problem (&problem_MD
);