1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008, 2009, 2010 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "alloc-pool.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
48 /* Note that turning REG_DEAD_DEBUGGING on will cause
49 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50 addresses in the dumps. */
52 #define REG_DEAD_DEBUGGING
55 #define DF_SPARSE_THRESHOLD 32
57 static bitmap_head seen_in_block
;
58 static bitmap_head seen_in_insn
;
61 /*----------------------------------------------------------------------------
62 Public functions access functions for the dataflow problems.
63 ----------------------------------------------------------------------------*/
64 /* Get the live at out set for BB no matter what problem happens to be
65 defined. This function is used by the register allocators who
66 choose different dataflow problems depending on the optimization
70 df_get_live_out (basic_block bb
)
75 return DF_LIVE_OUT (bb
);
77 return DF_LR_OUT (bb
);
80 /* Get the live at in set for BB no matter what problem happens to be
81 defined. This function is used by the register allocators who
82 choose different dataflow problems depending on the optimization
86 df_get_live_in (basic_block bb
)
91 return DF_LIVE_IN (bb
);
96 /*----------------------------------------------------------------------------
98 ----------------------------------------------------------------------------*/
100 /* Generic versions to get the void* version of the block info. Only
101 used inside the problem instance vectors. */
103 /* Dump a def-use or use-def chain for REF to FILE. */
106 df_chain_dump (struct df_link
*link
, FILE *file
)
108 fprintf (file
, "{ ");
109 for (; link
; link
= link
->next
)
111 fprintf (file
, "%c%d(bb %d insn %d) ",
112 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
113 DF_REF_ID (link
->ref
),
114 DF_REF_BBNO (link
->ref
),
115 DF_REF_IS_ARTIFICIAL (link
->ref
) ? -1 : DF_REF_INSN_UID (link
->ref
));
121 /* Print some basic block info as part of df_dump. */
124 df_print_bb_index (basic_block bb
, FILE *file
)
129 fprintf (file
, "\n( ");
130 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
132 basic_block pred
= e
->src
;
133 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
135 fprintf (file
, ")->[%d]->( ", bb
->index
);
136 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
138 basic_block succ
= e
->dest
;
139 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
141 fprintf (file
, ")\n");
145 /*----------------------------------------------------------------------------
148 Find the locations in the function where each definition site for a
149 pseudo reaches. In and out bitvectors are built for each basic
150 block. The id field in the ref is used to index into these sets.
151 See df.h for details.
152 ----------------------------------------------------------------------------*/
154 /* This problem plays a large number of games for the sake of
157 1) The order of the bits in the bitvectors. After the scanning
158 phase, all of the defs are sorted. All of the defs for the reg 0
159 are first, followed by all defs for reg 1 and so on.
161 2) There are two kill sets, one if the number of defs is less or
162 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
165 <= : Data is built directly in the kill set.
167 > : One level of indirection is used to keep from generating long
168 strings of 1 bits in the kill sets. Bitvectors that are indexed
169 by the regnum are used to represent that there is a killing def
170 for the register. The confluence and transfer functions use
171 these along with the bitmap_clear_range call to remove ranges of
172 bits without actually generating a knockout vector.
174 The kill and sparse_kill and the dense_invalidated_by_call and
175 sparse_invalidated_by_call both play this game. */
177 /* Private data used to compute the solution for this problem. These
178 data structures are not accessible outside of this module. */
179 struct df_rd_problem_data
181 /* The set of defs to regs invalidated by call. */
182 bitmap_head sparse_invalidated_by_call
;
183 /* The set of defs to regs invalidate by call for rd. */
184 bitmap_head dense_invalidated_by_call
;
185 /* An obstack for the bitmaps we need for this problem. */
186 bitmap_obstack rd_bitmaps
;
190 /* Free basic block info. */
193 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
196 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
199 bitmap_clear (&bb_info
->kill
);
200 bitmap_clear (&bb_info
->sparse_kill
);
201 bitmap_clear (&bb_info
->gen
);
202 bitmap_clear (&bb_info
->in
);
203 bitmap_clear (&bb_info
->out
);
208 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
209 not touched unless the block is new. */
212 df_rd_alloc (bitmap all_blocks
)
214 unsigned int bb_index
;
216 struct df_rd_problem_data
*problem_data
;
218 if (df_rd
->problem_data
)
220 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
221 bitmap_clear (&problem_data
->sparse_invalidated_by_call
);
222 bitmap_clear (&problem_data
->dense_invalidated_by_call
);
226 problem_data
= XNEW (struct df_rd_problem_data
);
227 df_rd
->problem_data
= problem_data
;
229 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
230 bitmap_initialize (&problem_data
->sparse_invalidated_by_call
,
231 &problem_data
->rd_bitmaps
);
232 bitmap_initialize (&problem_data
->dense_invalidated_by_call
,
233 &problem_data
->rd_bitmaps
);
236 df_grow_bb_info (df_rd
);
238 /* Because of the clustering of all use sites for the same pseudo,
239 we have to process all of the blocks before doing the
242 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
244 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
246 /* When bitmaps are already initialized, just clear them. */
247 if (bb_info
->kill
.obstack
)
249 bitmap_clear (&bb_info
->kill
);
250 bitmap_clear (&bb_info
->sparse_kill
);
251 bitmap_clear (&bb_info
->gen
);
255 bitmap_initialize (&bb_info
->kill
, &problem_data
->rd_bitmaps
);
256 bitmap_initialize (&bb_info
->sparse_kill
, &problem_data
->rd_bitmaps
);
257 bitmap_initialize (&bb_info
->gen
, &problem_data
->rd_bitmaps
);
258 bitmap_initialize (&bb_info
->in
, &problem_data
->rd_bitmaps
);
259 bitmap_initialize (&bb_info
->out
, &problem_data
->rd_bitmaps
);
262 df_rd
->optional_p
= true;
266 /* Add the effect of the top artificial defs of BB to the reaching definitions
270 df_rd_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_rd
)
272 int bb_index
= bb
->index
;
274 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
276 df_ref def
= *def_rec
;
277 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
279 unsigned int dregno
= DF_REF_REGNO (def
);
280 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
281 bitmap_clear_range (local_rd
,
282 DF_DEFS_BEGIN (dregno
),
283 DF_DEFS_COUNT (dregno
));
284 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
289 /* Add the effect of the defs of INSN to the reaching definitions bitmap
293 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
296 unsigned uid
= INSN_UID (insn
);
299 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
301 df_ref def
= *def_rec
;
302 unsigned int dregno
= DF_REF_REGNO (def
);
303 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
304 || (dregno
>= FIRST_PSEUDO_REGISTER
))
306 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
307 bitmap_clear_range (local_rd
,
308 DF_DEFS_BEGIN (dregno
),
309 DF_DEFS_COUNT (dregno
));
310 if (!(DF_REF_FLAGS (def
)
311 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
312 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
317 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
318 more complicated than just simulating, because we must produce the
319 gen and kill sets and hence deal with the two possible representations
323 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
329 df_ref def
= *def_rec
;
330 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
332 unsigned int regno
= DF_REF_REGNO (def
);
333 unsigned int begin
= DF_DEFS_BEGIN (regno
);
334 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
336 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
337 || (regno
>= FIRST_PSEUDO_REGISTER
))
339 /* Only the last def(s) for a regno in the block has any
341 if (!bitmap_bit_p (&seen_in_block
, regno
))
343 /* The first def for regno in insn gets to knock out the
344 defs from other instructions. */
345 if ((!bitmap_bit_p (&seen_in_insn
, regno
))
346 /* If the def is to only part of the reg, it does
347 not kill the other defs that reach here. */
348 && (!(DF_REF_FLAGS (def
) &
349 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
351 if (n_defs
> DF_SPARSE_THRESHOLD
)
353 bitmap_set_bit (&bb_info
->sparse_kill
, regno
);
354 bitmap_clear_range(&bb_info
->gen
, begin
, n_defs
);
358 bitmap_set_range (&bb_info
->kill
, begin
, n_defs
);
359 bitmap_clear_range (&bb_info
->gen
, begin
, n_defs
);
363 bitmap_set_bit (&seen_in_insn
, regno
);
364 /* All defs for regno in the instruction may be put into
366 if (!(DF_REF_FLAGS (def
)
367 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
368 bitmap_set_bit (&bb_info
->gen
, DF_REF_ID (def
));
376 /* Compute local reaching def info for basic block BB. */
379 df_rd_bb_local_compute (unsigned int bb_index
)
381 basic_block bb
= BASIC_BLOCK (bb_index
);
382 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
385 bitmap_clear (&seen_in_block
);
386 bitmap_clear (&seen_in_insn
);
388 /* Artificials are only hard regs. */
389 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
390 df_rd_bb_local_compute_process_def (bb_info
,
391 df_get_artificial_defs (bb_index
),
394 FOR_BB_INSNS_REVERSE (bb
, insn
)
396 unsigned int uid
= INSN_UID (insn
);
401 df_rd_bb_local_compute_process_def (bb_info
,
402 DF_INSN_UID_DEFS (uid
), 0);
404 /* This complex dance with the two bitmaps is required because
405 instructions can assign twice to the same pseudo. This
406 generally happens with calls that will have one def for the
407 result and another def for the clobber. If only one vector
408 is used and the clobber goes first, the result will be
410 bitmap_ior_into (&seen_in_block
, &seen_in_insn
);
411 bitmap_clear (&seen_in_insn
);
414 /* Process the artificial defs at the top of the block last since we
415 are going backwards through the block and these are logically at
417 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
418 df_rd_bb_local_compute_process_def (bb_info
,
419 df_get_artificial_defs (bb_index
),
424 /* Compute local reaching def info for each basic block within BLOCKS. */
427 df_rd_local_compute (bitmap all_blocks
)
429 unsigned int bb_index
;
432 struct df_rd_problem_data
*problem_data
433 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
434 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
435 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
437 bitmap_initialize (&seen_in_block
, &df_bitmap_obstack
);
438 bitmap_initialize (&seen_in_insn
, &df_bitmap_obstack
);
440 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
442 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
444 df_rd_bb_local_compute (bb_index
);
447 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
448 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset
, 0, regno
, bi
)
450 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
451 bitmap_set_bit (sparse_invalidated
, regno
);
453 bitmap_set_range (dense_invalidated
,
454 DF_DEFS_BEGIN (regno
),
455 DF_DEFS_COUNT (regno
));
458 bitmap_clear (&seen_in_block
);
459 bitmap_clear (&seen_in_insn
);
463 /* Initialize the solution bit vectors for problem. */
466 df_rd_init_solution (bitmap all_blocks
)
468 unsigned int bb_index
;
471 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
473 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
475 bitmap_copy (&bb_info
->out
, &bb_info
->gen
);
476 bitmap_clear (&bb_info
->in
);
480 /* In of target gets or of out of source. */
483 df_rd_confluence_n (edge e
)
485 bitmap op1
= &df_rd_get_bb_info (e
->dest
->index
)->in
;
486 bitmap op2
= &df_rd_get_bb_info (e
->src
->index
)->out
;
487 bool changed
= false;
489 if (e
->flags
& EDGE_FAKE
)
492 if (e
->flags
& EDGE_EH
)
494 struct df_rd_problem_data
*problem_data
495 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
496 bitmap sparse_invalidated
= &problem_data
->sparse_invalidated_by_call
;
497 bitmap dense_invalidated
= &problem_data
->dense_invalidated_by_call
;
502 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
503 bitmap_copy (&tmp
, op2
);
504 bitmap_and_compl_into (&tmp
, dense_invalidated
);
506 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
508 bitmap_clear_range (&tmp
,
509 DF_DEFS_BEGIN (regno
),
510 DF_DEFS_COUNT (regno
));
512 changed
|= bitmap_ior_into (op1
, &tmp
);
517 return bitmap_ior_into (op1
, op2
);
521 /* Transfer function. */
524 df_rd_transfer_function (int bb_index
)
526 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
529 bitmap in
= &bb_info
->in
;
530 bitmap out
= &bb_info
->out
;
531 bitmap gen
= &bb_info
->gen
;
532 bitmap kill
= &bb_info
->kill
;
533 bitmap sparse_kill
= &bb_info
->sparse_kill
;
535 if (bitmap_empty_p (sparse_kill
))
536 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
539 struct df_rd_problem_data
*problem_data
;
540 bool changed
= false;
543 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
544 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
545 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
546 bitmap_initialize (&tmp
, &problem_data
->rd_bitmaps
);
548 bitmap_copy (&tmp
, in
);
549 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
551 bitmap_clear_range (&tmp
,
552 DF_DEFS_BEGIN (regno
),
553 DF_DEFS_COUNT (regno
));
555 bitmap_and_compl_into (&tmp
, kill
);
556 bitmap_ior_into (&tmp
, gen
);
557 changed
= !bitmap_equal_p (&tmp
, out
);
570 /* Free all storage associated with the problem. */
575 struct df_rd_problem_data
*problem_data
576 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
580 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
582 df_rd
->block_info_size
= 0;
583 free (df_rd
->block_info
);
584 df_rd
->block_info
= NULL
;
585 free (df_rd
->problem_data
);
591 /* Debugging info. */
594 df_rd_start_dump (FILE *file
)
596 struct df_rd_problem_data
*problem_data
597 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
598 unsigned int m
= DF_REG_SIZE(df
);
601 if (!df_rd
->block_info
)
604 fprintf (file
, ";; Reaching defs:\n\n");
606 fprintf (file
, " sparse invalidated \t");
607 dump_bitmap (file
, &problem_data
->sparse_invalidated_by_call
);
608 fprintf (file
, " dense invalidated \t");
609 dump_bitmap (file
, &problem_data
->dense_invalidated_by_call
);
611 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_COUNT (regno
));
616 fprintf (file
, "\n");
621 /* Debugging info at top of bb. */
624 df_rd_top_dump (basic_block bb
, FILE *file
)
626 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
630 fprintf (file
, ";; rd in \t(%d)\n", (int) bitmap_count_bits (&bb_info
->in
));
631 dump_bitmap (file
, &bb_info
->in
);
632 fprintf (file
, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (&bb_info
->gen
));
633 dump_bitmap (file
, &bb_info
->gen
);
634 fprintf (file
, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (&bb_info
->kill
));
635 dump_bitmap (file
, &bb_info
->kill
);
639 /* Debugging info at top of bb. */
642 df_rd_bottom_dump (basic_block bb
, FILE *file
)
644 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
648 fprintf (file
, ";; rd out \t(%d)\n", (int) bitmap_count_bits (&bb_info
->out
));
649 dump_bitmap (file
, &bb_info
->out
);
652 /* All of the information associated with every instance of the problem. */
654 static struct df_problem problem_RD
=
656 DF_RD
, /* Problem id. */
657 DF_FORWARD
, /* Direction. */
658 df_rd_alloc
, /* Allocate the problem specific data. */
659 NULL
, /* Reset global information. */
660 df_rd_free_bb_info
, /* Free basic block info. */
661 df_rd_local_compute
, /* Local compute function. */
662 df_rd_init_solution
, /* Init the solution specific data. */
663 df_worklist_dataflow
, /* Worklist solver. */
664 NULL
, /* Confluence operator 0. */
665 df_rd_confluence_n
, /* Confluence operator n. */
666 df_rd_transfer_function
, /* Transfer function. */
667 NULL
, /* Finalize function. */
668 df_rd_free
, /* Free all of the problem information. */
669 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
670 df_rd_start_dump
, /* Debugging. */
671 df_rd_top_dump
, /* Debugging start block. */
672 df_rd_bottom_dump
, /* Debugging end block. */
673 NULL
, /* Incremental solution verify start. */
674 NULL
, /* Incremental solution verify end. */
675 NULL
, /* Dependent problem. */
676 sizeof (struct df_rd_bb_info
),/* Size of entry of block_info array. */
677 TV_DF_RD
, /* Timing variable. */
678 true /* Reset blocks on dropping out of blocks_to_analyze. */
683 /* Create a new RD instance and add it to the existing instance
687 df_rd_add_problem (void)
689 df_add_problem (&problem_RD
);
694 /*----------------------------------------------------------------------------
697 Find the locations in the function where any use of a pseudo can
698 reach in the backwards direction. In and out bitvectors are built
699 for each basic block. The regno is used to index into these sets.
700 See df.h for details.
701 ----------------------------------------------------------------------------*/
703 /* Private data used to verify the solution for this problem. */
704 struct df_lr_problem_data
708 /* An obstack for the bitmaps we need for this problem. */
709 bitmap_obstack lr_bitmaps
;
712 /* Free basic block info. */
715 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
718 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
721 bitmap_clear (&bb_info
->use
);
722 bitmap_clear (&bb_info
->def
);
723 bitmap_clear (&bb_info
->in
);
724 bitmap_clear (&bb_info
->out
);
729 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
730 not touched unless the block is new. */
733 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
735 unsigned int bb_index
;
737 struct df_lr_problem_data
*problem_data
;
739 df_grow_bb_info (df_lr
);
740 if (df_lr
->problem_data
)
741 problem_data
= (struct df_lr_problem_data
*) df_lr
->problem_data
;
744 problem_data
= XNEW (struct df_lr_problem_data
);
745 df_lr
->problem_data
= problem_data
;
747 problem_data
->out
= NULL
;
748 problem_data
->in
= NULL
;
749 bitmap_obstack_initialize (&problem_data
->lr_bitmaps
);
752 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
754 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
756 /* When bitmaps are already initialized, just clear them. */
757 if (bb_info
->use
.obstack
)
759 bitmap_clear (&bb_info
->def
);
760 bitmap_clear (&bb_info
->use
);
764 bitmap_initialize (&bb_info
->use
, &problem_data
->lr_bitmaps
);
765 bitmap_initialize (&bb_info
->def
, &problem_data
->lr_bitmaps
);
766 bitmap_initialize (&bb_info
->in
, &problem_data
->lr_bitmaps
);
767 bitmap_initialize (&bb_info
->out
, &problem_data
->lr_bitmaps
);
771 df_lr
->optional_p
= false;
775 /* Reset the global solution for recalculation. */
778 df_lr_reset (bitmap all_blocks
)
780 unsigned int bb_index
;
783 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
785 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
786 gcc_assert (bb_info
);
787 bitmap_clear (&bb_info
->in
);
788 bitmap_clear (&bb_info
->out
);
793 /* Compute local live register info for basic block BB. */
796 df_lr_bb_local_compute (unsigned int bb_index
)
798 basic_block bb
= BASIC_BLOCK (bb_index
);
799 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
804 /* Process the registers set in an exception handler. */
805 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
807 df_ref def
= *def_rec
;
808 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
810 unsigned int dregno
= DF_REF_REGNO (def
);
811 bitmap_set_bit (&bb_info
->def
, dregno
);
812 bitmap_clear_bit (&bb_info
->use
, dregno
);
816 /* Process the hardware registers that are always live. */
817 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
819 df_ref use
= *use_rec
;
820 /* Add use to set of uses in this BB. */
821 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
822 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
825 FOR_BB_INSNS_REVERSE (bb
, insn
)
827 unsigned int uid
= INSN_UID (insn
);
829 if (!NONDEBUG_INSN_P (insn
))
832 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
834 df_ref def
= *def_rec
;
835 /* If the def is to only part of the reg, it does
836 not kill the other defs that reach here. */
837 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
839 unsigned int dregno
= DF_REF_REGNO (def
);
840 bitmap_set_bit (&bb_info
->def
, dregno
);
841 bitmap_clear_bit (&bb_info
->use
, dregno
);
845 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
847 df_ref use
= *use_rec
;
848 /* Add use to set of uses in this BB. */
849 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
853 /* Process the registers set in an exception handler or the hard
854 frame pointer if this block is the target of a non local
856 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
858 df_ref def
= *def_rec
;
859 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
861 unsigned int dregno
= DF_REF_REGNO (def
);
862 bitmap_set_bit (&bb_info
->def
, dregno
);
863 bitmap_clear_bit (&bb_info
->use
, dregno
);
868 /* Process the uses that are live into an exception handler. */
869 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
871 df_ref use
= *use_rec
;
872 /* Add use to set of uses in this BB. */
873 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
874 bitmap_set_bit (&bb_info
->use
, DF_REF_REGNO (use
));
878 /* If the df_live problem is not defined, such as at -O0 and -O1, we
879 still need to keep the luids up to date. This is normally done
880 in the df_live problem since this problem has a forwards
883 df_recompute_luids (bb
);
887 /* Compute local live register info for each basic block within BLOCKS. */
890 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
892 unsigned int bb_index
;
895 bitmap_clear (&df
->hardware_regs_used
);
897 /* The all-important stack pointer must always be live. */
898 bitmap_set_bit (&df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
900 /* Before reload, there are a few registers that must be forced
901 live everywhere -- which might not already be the case for
902 blocks within infinite loops. */
903 if (!reload_completed
)
905 /* Any reference to any pseudo before reload is a potential
906 reference of the frame pointer. */
907 bitmap_set_bit (&df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
909 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
910 /* Pseudos with argument area equivalences may require
911 reloading via the argument pointer. */
912 if (fixed_regs
[ARG_POINTER_REGNUM
])
913 bitmap_set_bit (&df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
916 /* Any constant, or pseudo with constant equivalences, may
917 require reloading from memory using the pic register. */
918 if ((unsigned) PIC_OFFSET_TABLE_REGNUM
!= INVALID_REGNUM
919 && fixed_regs
[PIC_OFFSET_TABLE_REGNUM
])
920 bitmap_set_bit (&df
->hardware_regs_used
, PIC_OFFSET_TABLE_REGNUM
);
923 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
925 if (bb_index
== EXIT_BLOCK
)
927 /* The exit block is special for this problem and its bits are
928 computed from thin air. */
929 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
930 bitmap_copy (&bb_info
->use
, df
->exit_block_uses
);
933 df_lr_bb_local_compute (bb_index
);
936 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
940 /* Initialize the solution vectors. */
943 df_lr_init (bitmap all_blocks
)
945 unsigned int bb_index
;
948 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
950 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
951 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
952 bitmap_clear (&bb_info
->out
);
957 /* Confluence function that processes infinite loops. This might be a
958 noreturn function that throws. And even if it isn't, getting the
959 unwind info right helps debugging. */
961 df_lr_confluence_0 (basic_block bb
)
963 bitmap op1
= &df_lr_get_bb_info (bb
->index
)->out
;
964 if (bb
!= EXIT_BLOCK_PTR
)
965 bitmap_copy (op1
, &df
->hardware_regs_used
);
969 /* Confluence function that ignores fake edges. */
972 df_lr_confluence_n (edge e
)
974 bitmap op1
= &df_lr_get_bb_info (e
->src
->index
)->out
;
975 bitmap op2
= &df_lr_get_bb_info (e
->dest
->index
)->in
;
976 bool changed
= false;
978 /* Call-clobbered registers die across exception and call edges. */
979 /* ??? Abnormal call edges ignored for the moment, as this gets
980 confused by sibling call edges, which crashes reg-stack. */
981 if (e
->flags
& EDGE_EH
)
982 changed
= bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
984 changed
= bitmap_ior_into (op1
, op2
);
986 changed
|= bitmap_ior_into (op1
, &df
->hardware_regs_used
);
991 /* Transfer function. */
994 df_lr_transfer_function (int bb_index
)
996 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
997 bitmap in
= &bb_info
->in
;
998 bitmap out
= &bb_info
->out
;
999 bitmap use
= &bb_info
->use
;
1000 bitmap def
= &bb_info
->def
;
1002 return bitmap_ior_and_compl (in
, use
, out
, def
);
1006 /* Run the fast dce as a side effect of building LR. */
1009 df_lr_finalize (bitmap all_blocks
)
1011 df_lr
->solutions_dirty
= false;
1012 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1016 /* If dce deletes some instructions, we need to recompute the lr
1017 solution before proceeding further. The problem is that fast
1018 dce is a pessimestic dataflow algorithm. In the case where
1019 it deletes a statement S inside of a loop, the uses inside of
1020 S may not be deleted from the dataflow solution because they
1021 were carried around the loop. While it is conservatively
1022 correct to leave these extra bits, the standards of df
1023 require that we maintain the best possible (least fixed
1024 point) solution. The only way to do that is to redo the
1025 iteration from the beginning. See PR35805 for an
1027 if (df_lr
->solutions_dirty
)
1029 df_clear_flags (DF_LR_RUN_DCE
);
1030 df_lr_alloc (all_blocks
);
1031 df_lr_local_compute (all_blocks
);
1032 df_worklist_dataflow (df_lr
, all_blocks
, df
->postorder
, df
->n_blocks
);
1033 df_lr_finalize (all_blocks
);
1034 df_set_flags (DF_LR_RUN_DCE
);
1040 /* Free all storage associated with the problem. */
1045 struct df_lr_problem_data
*problem_data
1046 = (struct df_lr_problem_data
*) df_lr
->problem_data
;
1047 if (df_lr
->block_info
)
1050 df_lr
->block_info_size
= 0;
1051 free (df_lr
->block_info
);
1052 df_lr
->block_info
= NULL
;
1053 bitmap_obstack_release (&problem_data
->lr_bitmaps
);
1054 free (df_lr
->problem_data
);
1055 df_lr
->problem_data
= NULL
;
1058 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1063 /* Debugging info at top of bb. */
1066 df_lr_top_dump (basic_block bb
, FILE *file
)
1068 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1069 struct df_lr_problem_data
*problem_data
;
1073 fprintf (file
, ";; lr in \t");
1074 df_print_regset (file
, &bb_info
->in
);
1075 if (df_lr
->problem_data
)
1077 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1078 if (problem_data
->in
)
1080 fprintf (file
, ";; old in \t");
1081 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1084 fprintf (file
, ";; lr use \t");
1085 df_print_regset (file
, &bb_info
->use
);
1086 fprintf (file
, ";; lr def \t");
1087 df_print_regset (file
, &bb_info
->def
);
1091 /* Debugging info at bottom of bb. */
1094 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1096 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1097 struct df_lr_problem_data
*problem_data
;
1101 fprintf (file
, ";; lr out \t");
1102 df_print_regset (file
, &bb_info
->out
);
1103 if (df_lr
->problem_data
)
1105 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1106 if (problem_data
->out
)
1108 fprintf (file
, ";; old out \t");
1109 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1115 /* Build the datastructure to verify that the solution to the dataflow
1116 equations is not dirty. */
1119 df_lr_verify_solution_start (void)
1122 struct df_lr_problem_data
*problem_data
;
1123 if (df_lr
->solutions_dirty
)
1126 /* Set it true so that the solution is recomputed. */
1127 df_lr
->solutions_dirty
= true;
1129 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1130 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block
);
1131 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block
);
1135 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->lr_bitmaps
);
1136 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->lr_bitmaps
);
1137 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1138 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1143 /* Compare the saved datastructure and the new solution to the dataflow
1147 df_lr_verify_solution_end (void)
1149 struct df_lr_problem_data
*problem_data
;
1152 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1154 if (!problem_data
->out
)
1157 if (df_lr
->solutions_dirty
)
1158 /* Do not check if the solution is still dirty. See the comment
1159 in df_lr_finalize for details. */
1160 df_lr
->solutions_dirty
= false;
1164 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1165 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1167 /*df_dump (stderr);*/
1172 /* Cannot delete them immediately because you may want to dump them
1173 if the comparison fails. */
1176 bitmap_clear (&problem_data
->in
[bb
->index
]);
1177 bitmap_clear (&problem_data
->out
[bb
->index
]);
1180 free (problem_data
->in
);
1181 free (problem_data
->out
);
1182 problem_data
->in
= NULL
;
1183 problem_data
->out
= NULL
;
1187 /* All of the information associated with every instance of the problem. */
1189 static struct df_problem problem_LR
=
1191 DF_LR
, /* Problem id. */
1192 DF_BACKWARD
, /* Direction. */
1193 df_lr_alloc
, /* Allocate the problem specific data. */
1194 df_lr_reset
, /* Reset global information. */
1195 df_lr_free_bb_info
, /* Free basic block info. */
1196 df_lr_local_compute
, /* Local compute function. */
1197 df_lr_init
, /* Init the solution specific data. */
1198 df_worklist_dataflow
, /* Worklist solver. */
1199 df_lr_confluence_0
, /* Confluence operator 0. */
1200 df_lr_confluence_n
, /* Confluence operator n. */
1201 df_lr_transfer_function
, /* Transfer function. */
1202 df_lr_finalize
, /* Finalize function. */
1203 df_lr_free
, /* Free all of the problem information. */
1204 NULL
, /* Remove this problem from the stack of dataflow problems. */
1205 NULL
, /* Debugging. */
1206 df_lr_top_dump
, /* Debugging start block. */
1207 df_lr_bottom_dump
, /* Debugging end block. */
1208 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1209 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1210 NULL
, /* Dependent problem. */
1211 sizeof (struct df_lr_bb_info
),/* Size of entry of block_info array. */
1212 TV_DF_LR
, /* Timing variable. */
1213 false /* Reset blocks on dropping out of blocks_to_analyze. */
1217 /* Create a new DATAFLOW instance and add it to an existing instance
1218 of DF. The returned structure is what is used to get at the
1222 df_lr_add_problem (void)
1224 df_add_problem (&problem_LR
);
1225 /* These will be initialized when df_scan_blocks processes each
1227 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1231 /* Verify that all of the lr related info is consistent and
1235 df_lr_verify_transfer_functions (void)
1238 bitmap_head saved_def
;
1239 bitmap_head saved_use
;
1240 bitmap_head all_blocks
;
1245 bitmap_initialize (&saved_def
, &bitmap_default_obstack
);
1246 bitmap_initialize (&saved_use
, &bitmap_default_obstack
);
1247 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1251 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1252 bitmap_set_bit (&all_blocks
, bb
->index
);
1256 /* Make a copy of the transfer functions and then compute
1257 new ones to see if the transfer functions have
1259 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1262 bitmap_copy (&saved_def
, &bb_info
->def
);
1263 bitmap_copy (&saved_use
, &bb_info
->use
);
1264 bitmap_clear (&bb_info
->def
);
1265 bitmap_clear (&bb_info
->use
);
1267 df_lr_bb_local_compute (bb
->index
);
1268 gcc_assert (bitmap_equal_p (&saved_def
, &bb_info
->def
));
1269 gcc_assert (bitmap_equal_p (&saved_use
, &bb_info
->use
));
1274 /* If we do not have basic block info, the block must be in
1275 the list of dirty blocks or else some one has added a
1276 block behind our backs. */
1277 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1280 /* Make sure no one created a block without following
1282 gcc_assert (df_scan_get_bb_info (bb
->index
));
1285 /* Make sure there are no dirty bits in blocks that have been deleted. */
1286 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1289 bitmap_clear (&saved_def
);
1290 bitmap_clear (&saved_use
);
1291 bitmap_clear (&all_blocks
);
1296 /*----------------------------------------------------------------------------
1297 LIVE AND MUST-INITIALIZED REGISTERS.
1299 This problem first computes the IN and OUT bitvectors for the
1300 must-initialized registers problems, which is a forward problem.
1301 It gives the set of registers for which we MUST have an available
1302 definition on any path from the entry block to the entry/exit of
1303 a basic block. Sets generate a definition, while clobbers kill
1306 In and out bitvectors are built for each basic block and are indexed by
1307 regnum (see df.h for details). In and out bitvectors in struct
1308 df_live_bb_info actually refers to the must-initialized problem;
1310 Then, the in and out sets for the LIVE problem itself are computed.
1311 These are the logical AND of the IN and OUT sets from the LR problem
1312 and the must-initialized problem.
1313 ----------------------------------------------------------------------------*/
1315 /* Private data used to verify the solution for this problem. */
1316 struct df_live_problem_data
1320 /* An obstack for the bitmaps we need for this problem. */
1321 bitmap_obstack live_bitmaps
;
1324 /* Scratch var used by transfer functions. This is used to implement
1325 an optimization to reduce the amount of space used to compute the
1326 combined lr and live analysis. */
1327 static bitmap_head df_live_scratch
;
1330 /* Free basic block info. */
1333 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1336 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1339 bitmap_clear (&bb_info
->gen
);
1340 bitmap_clear (&bb_info
->kill
);
1341 bitmap_clear (&bb_info
->in
);
1342 bitmap_clear (&bb_info
->out
);
1347 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1348 not touched unless the block is new. */
1351 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1353 unsigned int bb_index
;
1355 struct df_live_problem_data
*problem_data
;
1357 if (df_live
->problem_data
)
1358 problem_data
= (struct df_live_problem_data
*) df_live
->problem_data
;
1361 problem_data
= XNEW (struct df_live_problem_data
);
1362 df_live
->problem_data
= problem_data
;
1364 problem_data
->out
= NULL
;
1365 problem_data
->in
= NULL
;
1366 bitmap_obstack_initialize (&problem_data
->live_bitmaps
);
1367 bitmap_initialize (&df_live_scratch
, &problem_data
->live_bitmaps
);
1370 df_grow_bb_info (df_live
);
1372 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1374 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1376 /* When bitmaps are already initialized, just clear them. */
1377 if (bb_info
->kill
.obstack
)
1379 bitmap_clear (&bb_info
->kill
);
1380 bitmap_clear (&bb_info
->gen
);
1384 bitmap_initialize (&bb_info
->kill
, &problem_data
->live_bitmaps
);
1385 bitmap_initialize (&bb_info
->gen
, &problem_data
->live_bitmaps
);
1386 bitmap_initialize (&bb_info
->in
, &problem_data
->live_bitmaps
);
1387 bitmap_initialize (&bb_info
->out
, &problem_data
->live_bitmaps
);
1390 df_live
->optional_p
= (optimize
<= 1);
1394 /* Reset the global solution for recalculation. */
1397 df_live_reset (bitmap all_blocks
)
1399 unsigned int bb_index
;
1402 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1404 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1405 gcc_assert (bb_info
);
1406 bitmap_clear (&bb_info
->in
);
1407 bitmap_clear (&bb_info
->out
);
1412 /* Compute local uninitialized register info for basic block BB. */
1415 df_live_bb_local_compute (unsigned int bb_index
)
1417 basic_block bb
= BASIC_BLOCK (bb_index
);
1418 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1423 FOR_BB_INSNS (bb
, insn
)
1425 unsigned int uid
= INSN_UID (insn
);
1426 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1428 /* Inserting labels does not always trigger the incremental
1432 gcc_assert (!INSN_P (insn
));
1433 insn_info
= df_insn_create_insn_record (insn
);
1436 DF_INSN_INFO_LUID (insn_info
) = luid
;
1441 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
1443 df_ref def
= *def_rec
;
1444 unsigned int regno
= DF_REF_REGNO (def
);
1446 if (DF_REF_FLAGS_IS_SET (def
,
1447 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1448 /* All partial or conditional def
1449 seen are included in the gen set. */
1450 bitmap_set_bit (&bb_info
->gen
, regno
);
1451 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1452 /* Only must clobbers for the entire reg destroy the
1454 bitmap_set_bit (&bb_info
->kill
, regno
);
1455 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1456 bitmap_set_bit (&bb_info
->gen
, regno
);
1460 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1462 df_ref def
= *def_rec
;
1463 bitmap_set_bit (&bb_info
->gen
, DF_REF_REGNO (def
));
1468 /* Compute local uninitialized register info. */
1471 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1473 unsigned int bb_index
;
1476 df_grow_insn_info ();
1478 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1481 df_live_bb_local_compute (bb_index
);
1484 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1488 /* Initialize the solution vectors. */
1491 df_live_init (bitmap all_blocks
)
1493 unsigned int bb_index
;
1496 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1498 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1499 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1501 /* No register may reach a location where it is not used. Thus
1502 we trim the rr result to the places where it is used. */
1503 bitmap_and (&bb_info
->out
, &bb_info
->gen
, &bb_lr_info
->out
);
1504 bitmap_clear (&bb_info
->in
);
1508 /* Forward confluence function that ignores fake edges. */
1511 df_live_confluence_n (edge e
)
1513 bitmap op1
= &df_live_get_bb_info (e
->dest
->index
)->in
;
1514 bitmap op2
= &df_live_get_bb_info (e
->src
->index
)->out
;
1516 if (e
->flags
& EDGE_FAKE
)
1519 return bitmap_ior_into (op1
, op2
);
1523 /* Transfer function for the forwards must-initialized problem. */
1526 df_live_transfer_function (int bb_index
)
1528 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1529 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1530 bitmap in
= &bb_info
->in
;
1531 bitmap out
= &bb_info
->out
;
1532 bitmap gen
= &bb_info
->gen
;
1533 bitmap kill
= &bb_info
->kill
;
1535 /* We need to use a scratch set here so that the value returned from this
1536 function invocation properly reflects whether the sets changed in a
1537 significant way; i.e. not just because the lr set was anded in. */
1538 bitmap_and (&df_live_scratch
, gen
, &bb_lr_info
->out
);
1539 /* No register may reach a location where it is not used. Thus
1540 we trim the rr result to the places where it is used. */
1541 bitmap_and_into (in
, &bb_lr_info
->in
);
1543 return bitmap_ior_and_compl (out
, &df_live_scratch
, in
, kill
);
1547 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1550 df_live_finalize (bitmap all_blocks
)
1553 if (df_live
->solutions_dirty
)
1556 unsigned int bb_index
;
1558 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1560 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1561 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1563 /* No register may reach a location where it is not used. Thus
1564 we trim the rr result to the places where it is used. */
1565 bitmap_and_into (&bb_live_info
->in
, &bb_lr_info
->in
);
1566 bitmap_and_into (&bb_live_info
->out
, &bb_lr_info
->out
);
1569 df_live
->solutions_dirty
= false;
1574 /* Free all storage associated with the problem. */
1579 struct df_live_problem_data
*problem_data
1580 = (struct df_live_problem_data
*) df_live
->problem_data
;
1581 if (df_live
->block_info
)
1583 df_live
->block_info_size
= 0;
1584 free (df_live
->block_info
);
1585 df_live
->block_info
= NULL
;
1586 bitmap_clear (&df_live_scratch
);
1587 bitmap_obstack_release (&problem_data
->live_bitmaps
);
1588 free (problem_data
);
1589 df_live
->problem_data
= NULL
;
1591 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1596 /* Debugging info at top of bb. */
1599 df_live_top_dump (basic_block bb
, FILE *file
)
1601 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1602 struct df_live_problem_data
*problem_data
;
1607 fprintf (file
, ";; live in \t");
1608 df_print_regset (file
, &bb_info
->in
);
1609 if (df_live
->problem_data
)
1611 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1612 if (problem_data
->in
)
1614 fprintf (file
, ";; old in \t");
1615 df_print_regset (file
, &problem_data
->in
[bb
->index
]);
1618 fprintf (file
, ";; live gen \t");
1619 df_print_regset (file
, &bb_info
->gen
);
1620 fprintf (file
, ";; live kill\t");
1621 df_print_regset (file
, &bb_info
->kill
);
1625 /* Debugging info at bottom of bb. */
1628 df_live_bottom_dump (basic_block bb
, FILE *file
)
1630 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1631 struct df_live_problem_data
*problem_data
;
1636 fprintf (file
, ";; live out \t");
1637 df_print_regset (file
, &bb_info
->out
);
1638 if (df_live
->problem_data
)
1640 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1641 if (problem_data
->out
)
1643 fprintf (file
, ";; old out \t");
1644 df_print_regset (file
, &problem_data
->out
[bb
->index
]);
1650 /* Build the datastructure to verify that the solution to the dataflow
1651 equations is not dirty. */
1654 df_live_verify_solution_start (void)
1657 struct df_live_problem_data
*problem_data
;
1658 if (df_live
->solutions_dirty
)
1661 /* Set it true so that the solution is recomputed. */
1662 df_live
->solutions_dirty
= true;
1664 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1665 problem_data
->in
= XNEWVEC (bitmap_head
, last_basic_block
);
1666 problem_data
->out
= XNEWVEC (bitmap_head
, last_basic_block
);
1670 bitmap_initialize (&problem_data
->in
[bb
->index
], &problem_data
->live_bitmaps
);
1671 bitmap_initialize (&problem_data
->out
[bb
->index
], &problem_data
->live_bitmaps
);
1672 bitmap_copy (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1673 bitmap_copy (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1678 /* Compare the saved datastructure and the new solution to the dataflow
1682 df_live_verify_solution_end (void)
1684 struct df_live_problem_data
*problem_data
;
1687 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1688 if (!problem_data
->out
)
1693 if ((!bitmap_equal_p (&problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1694 || (!bitmap_equal_p (&problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
1696 /*df_dump (stderr);*/
1701 /* Cannot delete them immediately because you may want to dump them
1702 if the comparison fails. */
1705 bitmap_clear (&problem_data
->in
[bb
->index
]);
1706 bitmap_clear (&problem_data
->out
[bb
->index
]);
1709 free (problem_data
->in
);
1710 free (problem_data
->out
);
1711 free (problem_data
);
1712 df_live
->problem_data
= NULL
;
1716 /* All of the information associated with every instance of the problem. */
1718 static struct df_problem problem_LIVE
=
1720 DF_LIVE
, /* Problem id. */
1721 DF_FORWARD
, /* Direction. */
1722 df_live_alloc
, /* Allocate the problem specific data. */
1723 df_live_reset
, /* Reset global information. */
1724 df_live_free_bb_info
, /* Free basic block info. */
1725 df_live_local_compute
, /* Local compute function. */
1726 df_live_init
, /* Init the solution specific data. */
1727 df_worklist_dataflow
, /* Worklist solver. */
1728 NULL
, /* Confluence operator 0. */
1729 df_live_confluence_n
, /* Confluence operator n. */
1730 df_live_transfer_function
, /* Transfer function. */
1731 df_live_finalize
, /* Finalize function. */
1732 df_live_free
, /* Free all of the problem information. */
1733 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1734 NULL
, /* Debugging. */
1735 df_live_top_dump
, /* Debugging start block. */
1736 df_live_bottom_dump
, /* Debugging end block. */
1737 df_live_verify_solution_start
,/* Incremental solution verify start. */
1738 df_live_verify_solution_end
, /* Incremental solution verify end. */
1739 &problem_LR
, /* Dependent problem. */
1740 sizeof (struct df_live_bb_info
),/* Size of entry of block_info array. */
1741 TV_DF_LIVE
, /* Timing variable. */
1742 false /* Reset blocks on dropping out of blocks_to_analyze. */
1746 /* Create a new DATAFLOW instance and add it to an existing instance
1747 of DF. The returned structure is what is used to get at the
1751 df_live_add_problem (void)
1753 df_add_problem (&problem_LIVE
);
1754 /* These will be initialized when df_scan_blocks processes each
1756 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1760 /* Set all of the blocks as dirty. This needs to be done if this
1761 problem is added after all of the insns have been scanned. */
1764 df_live_set_all_dirty (void)
1768 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1773 /* Verify that all of the lr related info is consistent and
1777 df_live_verify_transfer_functions (void)
1780 bitmap_head saved_gen
;
1781 bitmap_head saved_kill
;
1782 bitmap_head all_blocks
;
1787 bitmap_initialize (&saved_gen
, &bitmap_default_obstack
);
1788 bitmap_initialize (&saved_kill
, &bitmap_default_obstack
);
1789 bitmap_initialize (&all_blocks
, &bitmap_default_obstack
);
1791 df_grow_insn_info ();
1795 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1796 bitmap_set_bit (&all_blocks
, bb
->index
);
1800 /* Make a copy of the transfer functions and then compute
1801 new ones to see if the transfer functions have
1803 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1806 bitmap_copy (&saved_gen
, &bb_info
->gen
);
1807 bitmap_copy (&saved_kill
, &bb_info
->kill
);
1808 bitmap_clear (&bb_info
->gen
);
1809 bitmap_clear (&bb_info
->kill
);
1811 df_live_bb_local_compute (bb
->index
);
1812 gcc_assert (bitmap_equal_p (&saved_gen
, &bb_info
->gen
));
1813 gcc_assert (bitmap_equal_p (&saved_kill
, &bb_info
->kill
));
1818 /* If we do not have basic block info, the block must be in
1819 the list of dirty blocks or else some one has added a
1820 block behind our backs. */
1821 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1824 /* Make sure no one created a block without following
1826 gcc_assert (df_scan_get_bb_info (bb
->index
));
1829 /* Make sure there are no dirty bits in blocks that have been deleted. */
1830 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1832 bitmap_clear (&saved_gen
);
1833 bitmap_clear (&saved_kill
);
1834 bitmap_clear (&all_blocks
);
1837 /*----------------------------------------------------------------------------
1838 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1840 Link either the defs to the uses and / or the uses to the defs.
1842 These problems are set up like the other dataflow problems so that
1843 they nicely fit into the framework. They are much simpler and only
1844 involve a single traversal of instructions and an examination of
1845 the reaching defs information (the dependent problem).
1846 ----------------------------------------------------------------------------*/
1848 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1850 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1853 df_chain_create (df_ref src
, df_ref dst
)
1855 struct df_link
*head
= DF_REF_CHAIN (src
);
1856 struct df_link
*link
= (struct df_link
*) pool_alloc (df_chain
->block_pool
);
1858 DF_REF_CHAIN (src
) = link
;
1865 /* Delete any du or ud chains that start at REF and point to
1868 df_chain_unlink_1 (df_ref ref
, df_ref target
)
1870 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1871 struct df_link
*prev
= NULL
;
1875 if (chain
->ref
== target
)
1878 prev
->next
= chain
->next
;
1880 DF_REF_CHAIN (ref
) = chain
->next
;
1881 pool_free (df_chain
->block_pool
, chain
);
1885 chain
= chain
->next
;
1890 /* Delete a du or ud chain that leave or point to REF. */
1893 df_chain_unlink (df_ref ref
)
1895 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1898 struct df_link
*next
= chain
->next
;
1899 /* Delete the other side if it exists. */
1900 df_chain_unlink_1 (chain
->ref
, ref
);
1901 pool_free (df_chain
->block_pool
, chain
);
1904 DF_REF_CHAIN (ref
) = NULL
;
1908 /* Copy the du or ud chain starting at FROM_REF and attach it to
1912 df_chain_copy (df_ref to_ref
,
1913 struct df_link
*from_ref
)
1917 df_chain_create (to_ref
, from_ref
->ref
);
1918 from_ref
= from_ref
->next
;
1923 /* Remove this problem from the stack of dataflow problems. */
1926 df_chain_remove_problem (void)
1929 unsigned int bb_index
;
1931 /* Wholesale destruction of the old chains. */
1932 if (df_chain
->block_pool
)
1933 free_alloc_pool (df_chain
->block_pool
);
1935 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1940 basic_block bb
= BASIC_BLOCK (bb_index
);
1942 if (df_chain_problem_p (DF_DU_CHAIN
))
1943 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
1944 DF_REF_CHAIN (*def_rec
) = NULL
;
1945 if (df_chain_problem_p (DF_UD_CHAIN
))
1946 for (use_rec
= df_get_artificial_uses (bb
->index
); *use_rec
; use_rec
++)
1947 DF_REF_CHAIN (*use_rec
) = NULL
;
1949 FOR_BB_INSNS (bb
, insn
)
1951 unsigned int uid
= INSN_UID (insn
);
1955 if (df_chain_problem_p (DF_DU_CHAIN
))
1956 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1957 DF_REF_CHAIN (*def_rec
) = NULL
;
1958 if (df_chain_problem_p (DF_UD_CHAIN
))
1960 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1961 DF_REF_CHAIN (*use_rec
) = NULL
;
1962 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
1963 DF_REF_CHAIN (*use_rec
) = NULL
;
1969 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
1970 df_chain
->block_pool
= NULL
;
1974 /* Remove the chain problem completely. */
1977 df_chain_fully_remove_problem (void)
1979 df_chain_remove_problem ();
1980 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
1985 /* Create def-use or use-def chains. */
1988 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1990 df_chain_remove_problem ();
1991 df_chain
->block_pool
= create_alloc_pool ("df_chain_block pool",
1992 sizeof (struct df_link
), 50);
1993 df_chain
->optional_p
= true;
1997 /* Reset all of the chains when the set of basic blocks changes. */
2000 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2002 df_chain_remove_problem ();
2006 /* Create the chains for a list of USEs. */
2009 df_chain_create_bb_process_use (bitmap local_rd
,
2014 unsigned int def_index
;
2018 df_ref use
= *use_rec
;
2019 unsigned int uregno
= DF_REF_REGNO (use
);
2020 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2021 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2023 /* Do not want to go through this for an uninitialized var. */
2024 int count
= DF_DEFS_COUNT (uregno
);
2027 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2029 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2030 unsigned int last_index
= first_index
+ count
- 1;
2032 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2035 if (def_index
> last_index
)
2038 def
= DF_DEFS_GET (def_index
);
2039 if (df_chain_problem_p (DF_DU_CHAIN
))
2040 df_chain_create (def
, use
);
2041 if (df_chain_problem_p (DF_UD_CHAIN
))
2042 df_chain_create (use
, def
);
2053 /* Create chains from reaching defs bitmaps for basic block BB. */
2056 df_chain_create_bb (unsigned int bb_index
)
2058 basic_block bb
= BASIC_BLOCK (bb_index
);
2059 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2063 bitmap_initialize (&cpy
, &bitmap_default_obstack
);
2064 bitmap_copy (&cpy
, &bb_info
->in
);
2065 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2067 /* Since we are going forwards, process the artificial uses first
2068 then the artificial defs second. */
2071 /* Create the chains for the artificial uses from the EH_USES at the
2072 beginning of the block. */
2074 /* Artificials are only hard regs. */
2075 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2076 df_chain_create_bb_process_use (&cpy
,
2077 df_get_artificial_uses (bb
->index
),
2081 df_rd_simulate_artificial_defs_at_top (bb
, &cpy
);
2083 /* Process the regular instructions next. */
2084 FOR_BB_INSNS (bb
, insn
)
2087 unsigned int uid
= INSN_UID (insn
);
2089 /* First scan the uses and link them up with the defs that remain
2090 in the cpy vector. */
2091 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_USES (uid
), 0);
2092 if (df
->changeable_flags
& DF_EQ_NOTES
)
2093 df_chain_create_bb_process_use (&cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2095 /* Since we are going forwards, process the defs second. */
2096 df_rd_simulate_one_insn (bb
, insn
, &cpy
);
2099 /* Create the chains for the artificial uses of the hard registers
2100 at the end of the block. */
2101 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2102 df_chain_create_bb_process_use (&cpy
,
2103 df_get_artificial_uses (bb
->index
),
2106 bitmap_clear (&cpy
);
2109 /* Create def-use chains from reaching use bitmaps for basic blocks
2113 df_chain_finalize (bitmap all_blocks
)
2115 unsigned int bb_index
;
2118 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2120 df_chain_create_bb (bb_index
);
2125 /* Free all storage associated with the problem. */
2128 df_chain_free (void)
2130 free_alloc_pool (df_chain
->block_pool
);
2131 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2136 /* Debugging info. */
2139 df_chain_top_dump (basic_block bb
, FILE *file
)
2141 if (df_chain_problem_p (DF_DU_CHAIN
))
2144 df_ref
*def_rec
= df_get_artificial_defs (bb
->index
);
2148 fprintf (file
, ";; DU chains for artificial defs\n");
2151 df_ref def
= *def_rec
;
2152 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2153 df_chain_dump (DF_REF_CHAIN (def
), file
);
2154 fprintf (file
, "\n");
2159 FOR_BB_INSNS (bb
, insn
)
2163 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2164 def_rec
= DF_INSN_INFO_DEFS (insn_info
);
2167 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2168 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2172 df_ref def
= *def_rec
;
2173 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2174 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
2175 fprintf (file
, "read/write ");
2176 df_chain_dump (DF_REF_CHAIN (def
), file
);
2177 fprintf (file
, "\n");
2188 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2190 if (df_chain_problem_p (DF_UD_CHAIN
))
2193 df_ref
*use_rec
= df_get_artificial_uses (bb
->index
);
2197 fprintf (file
, ";; UD chains for artificial uses\n");
2200 df_ref use
= *use_rec
;
2201 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2202 df_chain_dump (DF_REF_CHAIN (use
), file
);
2203 fprintf (file
, "\n");
2208 FOR_BB_INSNS (bb
, insn
)
2212 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2213 df_ref
*eq_use_rec
= DF_INSN_INFO_EQ_USES (insn_info
);
2214 use_rec
= DF_INSN_INFO_USES (insn_info
);
2215 if (*use_rec
|| *eq_use_rec
)
2217 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2218 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2222 df_ref use
= *use_rec
;
2223 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2224 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
2225 fprintf (file
, "read/write ");
2226 df_chain_dump (DF_REF_CHAIN (use
), file
);
2227 fprintf (file
, "\n");
2232 df_ref use
= *eq_use_rec
;
2233 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2234 df_chain_dump (DF_REF_CHAIN (use
), file
);
2235 fprintf (file
, "\n");
2245 static struct df_problem problem_CHAIN
=
2247 DF_CHAIN
, /* Problem id. */
2248 DF_NONE
, /* Direction. */
2249 df_chain_alloc
, /* Allocate the problem specific data. */
2250 df_chain_reset
, /* Reset global information. */
2251 NULL
, /* Free basic block info. */
2252 NULL
, /* Local compute function. */
2253 NULL
, /* Init the solution specific data. */
2254 NULL
, /* Iterative solver. */
2255 NULL
, /* Confluence operator 0. */
2256 NULL
, /* Confluence operator n. */
2257 NULL
, /* Transfer function. */
2258 df_chain_finalize
, /* Finalize function. */
2259 df_chain_free
, /* Free all of the problem information. */
2260 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2261 NULL
, /* Debugging. */
2262 df_chain_top_dump
, /* Debugging start block. */
2263 df_chain_bottom_dump
, /* Debugging end block. */
2264 NULL
, /* Incremental solution verify start. */
2265 NULL
, /* Incremental solution verify end. */
2266 &problem_RD
, /* Dependent problem. */
2267 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
2268 TV_DF_CHAIN
, /* Timing variable. */
2269 false /* Reset blocks on dropping out of blocks_to_analyze. */
2273 /* Create a new DATAFLOW instance and add it to an existing instance
2274 of DF. The returned structure is what is used to get at the
2278 df_chain_add_problem (unsigned int chain_flags
)
2280 df_add_problem (&problem_CHAIN
);
2281 df_chain
->local_flags
= chain_flags
;
2282 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2285 #undef df_chain_problem_p
2288 /*----------------------------------------------------------------------------
2289 BYTE LEVEL LIVE REGISTERS
2291 Find the locations in the function where any use of a pseudo can
2292 reach in the backwards direction. In and out bitvectors are built
2293 for each basic block. There are two mapping functions,
2294 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2295 used to map regnos into bit vector positions.
2297 This problem differs from the regular df_lr function in the way
2298 that subregs, *_extracts and strict_low_parts are handled. In lr
2299 these are consider partial kills, here, the exact set of bytes is
2300 modeled. Note that any reg that has none of these operations is
2301 only modeled with a single bit since all operations access the
2304 This problem is more brittle that the regular lr. It currently can
2305 be used in dce incrementally, but cannot be used in an environment
2306 where insns are created or modified. The problem is that the
2307 mapping of regnos to bitmap positions is relatively compact, in
2308 that if a pseudo does not do any of the byte wise operations, only
2309 one slot is allocated, rather than a slot for each byte. If insn
2310 are created, where a subreg is used for a reg that had no subregs,
2311 the mapping would be wrong. Likewise, there are no checks to see
2312 that new pseudos have been added. These issues could be addressed
2313 by adding a problem specific flag to not use the compact mapping,
2314 if there was a need to do so.
2316 ----------------------------------------------------------------------------*/
2318 /* Private data used to verify the solution for this problem. */
2319 struct df_byte_lr_problem_data
2321 /* Expanded versions of bitvectors used in lr. */
2322 bitmap_head invalidated_by_call
;
2323 bitmap_head hardware_regs_used
;
2325 /* Indexed by regno, this is true if there are subregs, extracts or
2326 strict_low_parts for this regno. */
2327 bitmap_head needs_expansion
;
2329 /* The start position and len for each regno in the various bit
2331 unsigned int* regno_start
;
2332 unsigned int* regno_len
;
2333 /* An obstack for the bitmaps we need for this problem. */
2334 bitmap_obstack byte_lr_bitmaps
;
2338 /* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2341 df_byte_lr_get_regno_start (unsigned int regno
)
2343 struct df_byte_lr_problem_data
*problem_data
2344 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;;
2345 return problem_data
->regno_start
[regno
];
2349 /* Get the len for REGNO in the df_byte_lr bitmaps. */
2352 df_byte_lr_get_regno_len (unsigned int regno
)
2354 struct df_byte_lr_problem_data
*problem_data
2355 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;;
2356 return problem_data
->regno_len
[regno
];
2360 /* Free basic block info. */
2363 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2366 struct df_byte_lr_bb_info
*bb_info
= (struct df_byte_lr_bb_info
*) vbb_info
;
2369 bitmap_clear (&bb_info
->use
);
2370 bitmap_clear (&bb_info
->def
);
2371 bitmap_clear (&bb_info
->in
);
2372 bitmap_clear (&bb_info
->out
);
2377 /* Check all of the refs in REF_REC to see if any of them are
2378 extracts, subregs or strict_low_parts. */
2381 df_byte_lr_check_regs (df_ref
*ref_rec
)
2383 struct df_byte_lr_problem_data
*problem_data
2384 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2386 for (; *ref_rec
; ref_rec
++)
2388 df_ref ref
= *ref_rec
;
2389 if (DF_REF_FLAGS_IS_SET (ref
, DF_REF_SIGN_EXTRACT
2390 | DF_REF_ZERO_EXTRACT
2391 | DF_REF_STRICT_LOW_PART
)
2392 || GET_CODE (DF_REF_REG (ref
)) == SUBREG
)
2393 bitmap_set_bit (&problem_data
->needs_expansion
, DF_REF_REGNO (ref
));
2398 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2399 regno_start and regno_len. */
2402 df_byte_lr_expand_bitmap (bitmap dest
, bitmap src
)
2404 struct df_byte_lr_problem_data
*problem_data
2405 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2409 bitmap_clear (dest
);
2410 EXECUTE_IF_SET_IN_BITMAP (src
, 0, i
, bi
)
2412 bitmap_set_range (dest
, problem_data
->regno_start
[i
],
2413 problem_data
->regno_len
[i
]);
2418 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2419 not touched unless the block is new. */
2422 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2424 unsigned int bb_index
;
2428 unsigned int index
= 0;
2429 unsigned int max_reg
= max_reg_num();
2430 struct df_byte_lr_problem_data
*problem_data
2431 = XNEW (struct df_byte_lr_problem_data
);
2433 df_byte_lr
->problem_data
= problem_data
;
2435 df_grow_bb_info (df_byte_lr
);
2437 /* Create the mapping from regnos to slots. This does not change
2438 unless the problem is destroyed and recreated. In particular, if
2439 we end up deleting the only insn that used a subreg, we do not
2440 want to redo the mapping because this would invalidate everything
2443 bitmap_obstack_initialize (&problem_data
->byte_lr_bitmaps
);
2444 problem_data
->regno_start
= XNEWVEC (unsigned int, max_reg
);
2445 problem_data
->regno_len
= XNEWVEC (unsigned int, max_reg
);
2446 bitmap_initialize (&problem_data
->hardware_regs_used
,
2447 &problem_data
->byte_lr_bitmaps
);
2448 bitmap_initialize (&problem_data
->invalidated_by_call
,
2449 &problem_data
->byte_lr_bitmaps
);
2450 bitmap_initialize (&problem_data
->needs_expansion
,
2451 &problem_data
->byte_lr_bitmaps
);
2453 /* Discover which regno's use subregs, extracts or
2454 strict_low_parts. */
2458 FOR_BB_INSNS (bb
, insn
)
2462 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2463 df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info
));
2464 df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info
));
2467 bitmap_set_bit (df_byte_lr
->out_of_date_transfer_functions
, bb
->index
);
2470 bitmap_set_bit (df_byte_lr
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
2471 bitmap_set_bit (df_byte_lr
->out_of_date_transfer_functions
, EXIT_BLOCK
);
2473 /* Allocate the slots for each regno. */
2474 for (regno
= 0; regno
< max_reg
; regno
++)
2477 problem_data
->regno_start
[regno
] = index
;
2478 if (bitmap_bit_p (&problem_data
->needs_expansion
, regno
))
2479 len
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
2483 problem_data
->regno_len
[regno
] = len
;
2487 df_byte_lr_expand_bitmap (&problem_data
->hardware_regs_used
,
2488 &df
->hardware_regs_used
);
2489 df_byte_lr_expand_bitmap (&problem_data
->invalidated_by_call
,
2490 regs_invalidated_by_call_regset
);
2492 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2494 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2496 /* When bitmaps are already initialized, just clear them. */
2497 if (bb_info
->use
.obstack
)
2499 bitmap_clear (&bb_info
->def
);
2500 bitmap_clear (&bb_info
->use
);
2504 bitmap_initialize (&bb_info
->use
, &problem_data
->byte_lr_bitmaps
);
2505 bitmap_initialize (&bb_info
->def
, &problem_data
->byte_lr_bitmaps
);
2506 bitmap_initialize (&bb_info
->in
, &problem_data
->byte_lr_bitmaps
);
2507 bitmap_initialize (&bb_info
->out
, &problem_data
->byte_lr_bitmaps
);
2511 df_byte_lr
->optional_p
= true;
2515 /* Reset the global solution for recalculation. */
2518 df_byte_lr_reset (bitmap all_blocks
)
2520 unsigned int bb_index
;
2523 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2525 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2526 gcc_assert (bb_info
);
2527 bitmap_clear (&bb_info
->in
);
2528 bitmap_clear (&bb_info
->out
);
2533 /* Compute local live register info for basic block BB. */
2536 df_byte_lr_bb_local_compute (unsigned int bb_index
)
2538 struct df_byte_lr_problem_data
*problem_data
2539 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2540 basic_block bb
= BASIC_BLOCK (bb_index
);
2541 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2546 /* Process the registers set in an exception handler. */
2547 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2549 df_ref def
= *def_rec
;
2550 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
2552 unsigned int dregno
= DF_REF_REGNO (def
);
2553 unsigned int start
= problem_data
->regno_start
[dregno
];
2554 unsigned int len
= problem_data
->regno_len
[dregno
];
2555 bitmap_set_range (&bb_info
->def
, start
, len
);
2556 bitmap_clear_range (&bb_info
->use
, start
, len
);
2560 /* Process the hardware registers that are always live. */
2561 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2563 df_ref use
= *use_rec
;
2564 /* Add use to set of uses in this BB. */
2565 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
2567 unsigned int uregno
= DF_REF_REGNO (use
);
2568 unsigned int start
= problem_data
->regno_start
[uregno
];
2569 unsigned int len
= problem_data
->regno_len
[uregno
];
2570 bitmap_set_range (&bb_info
->use
, start
, len
);
2574 FOR_BB_INSNS_REVERSE (bb
, insn
)
2576 unsigned int uid
= INSN_UID (insn
);
2581 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2583 df_ref def
= *def_rec
;
2584 /* If the def is to only part of the reg, it does
2585 not kill the other defs that reach here. */
2586 if (!(DF_REF_FLAGS (def
) & (DF_REF_CONDITIONAL
)))
2588 unsigned int dregno
= DF_REF_REGNO (def
);
2589 unsigned int start
= problem_data
->regno_start
[dregno
];
2590 unsigned int len
= problem_data
->regno_len
[dregno
];
2593 if (!df_compute_accessed_bytes (def
, DF_MM_MUST
, &sb
, &lb
))
2600 bitmap_set_range (&bb_info
->def
, start
, len
);
2601 bitmap_clear_range (&bb_info
->use
, start
, len
);
2606 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2608 df_ref use
= *use_rec
;
2609 unsigned int uregno
= DF_REF_REGNO (use
);
2610 unsigned int start
= problem_data
->regno_start
[uregno
];
2611 unsigned int len
= problem_data
->regno_len
[uregno
];
2614 if (!df_compute_accessed_bytes (use
, DF_MM_MAY
, &sb
, &lb
))
2619 /* Add use to set of uses in this BB. */
2621 bitmap_set_range (&bb_info
->use
, start
, len
);
2625 /* Process the registers set in an exception handler or the hard
2626 frame pointer if this block is the target of a non local
2628 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2630 df_ref def
= *def_rec
;
2631 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2633 unsigned int dregno
= DF_REF_REGNO (def
);
2634 unsigned int start
= problem_data
->regno_start
[dregno
];
2635 unsigned int len
= problem_data
->regno_len
[dregno
];
2636 bitmap_set_range (&bb_info
->def
, start
, len
);
2637 bitmap_clear_range (&bb_info
->use
, start
, len
);
2642 /* Process the uses that are live into an exception handler. */
2643 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2645 df_ref use
= *use_rec
;
2646 /* Add use to set of uses in this BB. */
2647 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
2649 unsigned int uregno
= DF_REF_REGNO (use
);
2650 unsigned int start
= problem_data
->regno_start
[uregno
];
2651 unsigned int len
= problem_data
->regno_len
[uregno
];
2652 bitmap_set_range (&bb_info
->use
, start
, len
);
2659 /* Compute local live register info for each basic block within BLOCKS. */
2662 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2664 unsigned int bb_index
;
2667 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2669 if (bb_index
== EXIT_BLOCK
)
2671 /* The exit block is special for this problem and its bits are
2672 computed from thin air. */
2673 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (EXIT_BLOCK
);
2674 df_byte_lr_expand_bitmap (&bb_info
->use
, df
->exit_block_uses
);
2677 df_byte_lr_bb_local_compute (bb_index
);
2680 bitmap_clear (df_byte_lr
->out_of_date_transfer_functions
);
2684 /* Initialize the solution vectors. */
2687 df_byte_lr_init (bitmap all_blocks
)
2689 unsigned int bb_index
;
2692 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2694 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2695 bitmap_copy (&bb_info
->in
, &bb_info
->use
);
2696 bitmap_clear (&bb_info
->out
);
2701 /* Confluence function that processes infinite loops. This might be a
2702 noreturn function that throws. And even if it isn't, getting the
2703 unwind info right helps debugging. */
2705 df_byte_lr_confluence_0 (basic_block bb
)
2707 struct df_byte_lr_problem_data
*problem_data
2708 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2709 bitmap op1
= &df_byte_lr_get_bb_info (bb
->index
)->out
;
2710 if (bb
!= EXIT_BLOCK_PTR
)
2711 bitmap_copy (op1
, &problem_data
->hardware_regs_used
);
2715 /* Confluence function that ignores fake edges. */
2718 df_byte_lr_confluence_n (edge e
)
2720 struct df_byte_lr_problem_data
*problem_data
2721 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2722 bitmap op1
= &df_byte_lr_get_bb_info (e
->src
->index
)->out
;
2723 bitmap op2
= &df_byte_lr_get_bb_info (e
->dest
->index
)->in
;
2724 bool changed
= false;
2726 /* Call-clobbered registers die across exception and call edges. */
2727 /* ??? Abnormal call edges ignored for the moment, as this gets
2728 confused by sibling call edges, which crashes reg-stack. */
2729 if (e
->flags
& EDGE_EH
)
2730 changed
= bitmap_ior_and_compl_into (op1
, op2
,
2731 &problem_data
->invalidated_by_call
);
2733 changed
= bitmap_ior_into (op1
, op2
);
2735 changed
|= bitmap_ior_into (op1
, &problem_data
->hardware_regs_used
);
2740 /* Transfer function. */
2743 df_byte_lr_transfer_function (int bb_index
)
2745 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2746 bitmap in
= &bb_info
->in
;
2747 bitmap out
= &bb_info
->out
;
2748 bitmap use
= &bb_info
->use
;
2749 bitmap def
= &bb_info
->def
;
2751 return bitmap_ior_and_compl (in
, use
, out
, def
);
2755 /* Free all storage associated with the problem. */
2758 df_byte_lr_free (void)
2760 struct df_byte_lr_problem_data
*problem_data
2761 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2764 if (df_byte_lr
->block_info
)
2766 df_byte_lr
->block_info_size
= 0;
2767 free (df_byte_lr
->block_info
);
2768 df_byte_lr
->block_info
= NULL
;
2771 BITMAP_FREE (df_byte_lr
->out_of_date_transfer_functions
);
2772 bitmap_obstack_release (&problem_data
->byte_lr_bitmaps
);
2773 free (problem_data
->regno_start
);
2774 free (problem_data
->regno_len
);
2775 free (problem_data
);
2780 /* Debugging info at top of bb. */
2783 df_byte_lr_top_dump (basic_block bb
, FILE *file
)
2785 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb
->index
);
2789 fprintf (file
, ";; blr in \t");
2790 df_print_byte_regset (file
, &bb_info
->in
);
2791 fprintf (file
, ";; blr use \t");
2792 df_print_byte_regset (file
, &bb_info
->use
);
2793 fprintf (file
, ";; blr def \t");
2794 df_print_byte_regset (file
, &bb_info
->def
);
2798 /* Debugging info at bottom of bb. */
2801 df_byte_lr_bottom_dump (basic_block bb
, FILE *file
)
2803 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb
->index
);
2807 fprintf (file
, ";; blr out \t");
2808 df_print_byte_regset (file
, &bb_info
->out
);
2812 /* All of the information associated with every instance of the problem. */
2814 static struct df_problem problem_BYTE_LR
=
2816 DF_BYTE_LR
, /* Problem id. */
2817 DF_BACKWARD
, /* Direction. */
2818 df_byte_lr_alloc
, /* Allocate the problem specific data. */
2819 df_byte_lr_reset
, /* Reset global information. */
2820 df_byte_lr_free_bb_info
, /* Free basic block info. */
2821 df_byte_lr_local_compute
, /* Local compute function. */
2822 df_byte_lr_init
, /* Init the solution specific data. */
2823 df_worklist_dataflow
, /* Worklist solver. */
2824 df_byte_lr_confluence_0
, /* Confluence operator 0. */
2825 df_byte_lr_confluence_n
, /* Confluence operator n. */
2826 df_byte_lr_transfer_function
, /* Transfer function. */
2827 NULL
, /* Finalize function. */
2828 df_byte_lr_free
, /* Free all of the problem information. */
2829 df_byte_lr_free
, /* Remove this problem from the stack of dataflow problems. */
2830 NULL
, /* Debugging. */
2831 df_byte_lr_top_dump
, /* Debugging start block. */
2832 df_byte_lr_bottom_dump
, /* Debugging end block. */
2833 NULL
, /* Incremental solution verify start. */
2834 NULL
, /* Incremental solution verify end. */
2835 NULL
, /* Dependent problem. */
2836 sizeof (struct df_byte_lr_bb_info
),/* Size of entry of block_info array. */
2837 TV_DF_BYTE_LR
, /* Timing variable. */
2838 false /* Reset blocks on dropping out of blocks_to_analyze. */
2842 /* Create a new DATAFLOW instance and add it to an existing instance
2843 of DF. The returned structure is what is used to get at the
2847 df_byte_lr_add_problem (void)
2849 df_add_problem (&problem_BYTE_LR
);
2850 /* These will be initialized when df_scan_blocks processes each
2852 df_byte_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2856 /* Simulate the effects of the defs of INSN on LIVE. */
2859 df_byte_lr_simulate_defs (rtx insn
, bitmap live
)
2861 struct df_byte_lr_problem_data
*problem_data
2862 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2864 unsigned int uid
= INSN_UID (insn
);
2866 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2868 df_ref def
= *def_rec
;
2870 /* If the def is to only part of the reg, it does
2871 not kill the other defs that reach here. */
2872 if (!(DF_REF_FLAGS (def
) & DF_REF_CONDITIONAL
))
2874 unsigned int dregno
= DF_REF_REGNO (def
);
2875 unsigned int start
= problem_data
->regno_start
[dregno
];
2876 unsigned int len
= problem_data
->regno_len
[dregno
];
2879 if (!df_compute_accessed_bytes (def
, DF_MM_MUST
, &sb
, &lb
))
2886 bitmap_clear_range (live
, start
, len
);
2892 /* Simulate the effects of the uses of INSN on LIVE. */
2895 df_byte_lr_simulate_uses (rtx insn
, bitmap live
)
2897 struct df_byte_lr_problem_data
*problem_data
2898 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2900 unsigned int uid
= INSN_UID (insn
);
2902 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2904 df_ref use
= *use_rec
;
2905 unsigned int uregno
= DF_REF_REGNO (use
);
2906 unsigned int start
= problem_data
->regno_start
[uregno
];
2907 unsigned int len
= problem_data
->regno_len
[uregno
];
2911 if (!df_compute_accessed_bytes (use
, DF_MM_MAY
, &sb
, &lb
))
2917 /* Add use to set of uses in this BB. */
2919 bitmap_set_range (live
, start
, len
);
2924 /* Apply the artificial uses and defs at the top of BB in a forwards
2928 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb
, bitmap live
)
2930 struct df_byte_lr_problem_data
*problem_data
2931 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2936 int bb_index
= bb
->index
;
2939 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2941 df_ref use
= *use_rec
;
2942 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
2944 unsigned int uregno
= DF_REF_REGNO (use
);
2945 unsigned int start
= problem_data
->regno_start
[uregno
];
2946 unsigned int len
= problem_data
->regno_len
[uregno
];
2947 bitmap_set_range (live
, start
, len
);
2952 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2954 df_ref def
= *def_rec
;
2955 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2957 unsigned int dregno
= DF_REF_REGNO (def
);
2958 unsigned int start
= problem_data
->regno_start
[dregno
];
2959 unsigned int len
= problem_data
->regno_len
[dregno
];
2960 bitmap_clear_range (live
, start
, len
);
2966 /* Apply the artificial uses and defs at the end of BB in a backwards
2970 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb
, bitmap live
)
2972 struct df_byte_lr_problem_data
*problem_data
2973 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2976 int bb_index
= bb
->index
;
2978 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2980 df_ref def
= *def_rec
;
2981 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
2983 unsigned int dregno
= DF_REF_REGNO (def
);
2984 unsigned int start
= problem_data
->regno_start
[dregno
];
2985 unsigned int len
= problem_data
->regno_len
[dregno
];
2986 bitmap_clear_range (live
, start
, len
);
2990 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2992 df_ref use
= *use_rec
;
2993 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
2995 unsigned int uregno
= DF_REF_REGNO (use
);
2996 unsigned int start
= problem_data
->regno_start
[uregno
];
2997 unsigned int len
= problem_data
->regno_len
[uregno
];
2998 bitmap_set_range (live
, start
, len
);
3005 /*----------------------------------------------------------------------------
3006 This problem computes REG_DEAD and REG_UNUSED notes.
3007 ----------------------------------------------------------------------------*/
3010 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
3012 df_note
->optional_p
= true;
3015 #ifdef REG_DEAD_DEBUGGING
3017 df_print_note (const char *prefix
, rtx insn
, rtx note
)
3021 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
3022 print_rtl (dump_file
, note
);
3023 fprintf (dump_file
, "\n");
3029 /* After reg-stack, the x86 floating point stack regs are difficult to
3030 analyze because of all of the pushes, pops and rotations. Thus, we
3031 just leave the notes alone. */
3035 df_ignore_stack_reg (int regno
)
3037 return regstack_completed
3038 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
3042 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
3049 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3050 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3053 df_kill_notes (rtx insn
, rtx
*old_dead_notes
, rtx
*old_unused_notes
)
3055 rtx
*pprev
= ®_NOTES (insn
);
3062 switch (REG_NOTE_KIND (link
))
3065 /* After reg-stack, we need to ignore any unused notes
3066 for the stack registers. */
3067 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3069 pprev
= &XEXP (link
, 1);
3074 rtx next
= XEXP (link
, 1);
3075 #ifdef REG_DEAD_DEBUGGING
3076 df_print_note ("deleting: ", insn
, link
);
3078 XEXP (link
, 1) = dead
;
3080 *pprev
= link
= next
;
3085 /* After reg-stack, we need to ignore any unused notes
3086 for the stack registers. */
3087 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3089 pprev
= &XEXP (link
, 1);
3094 rtx next
= XEXP (link
, 1);
3095 #ifdef REG_DEAD_DEBUGGING
3096 df_print_note ("deleting: ", insn
, link
);
3098 XEXP (link
, 1) = unused
;
3100 *pprev
= link
= next
;
3105 pprev
= &XEXP (link
, 1);
3111 *old_dead_notes
= dead
;
3112 *old_unused_notes
= unused
;
3116 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3117 list, otherwise create a new one. */
3120 df_set_note (enum reg_note note_type
, rtx insn
, rtx old
, rtx reg
)
3125 gcc_assert (!DEBUG_INSN_P (insn
));
3128 if (XEXP (curr
, 0) == reg
)
3131 XEXP (prev
, 1) = XEXP (curr
, 1);
3133 old
= XEXP (curr
, 1);
3134 XEXP (curr
, 1) = REG_NOTES (insn
);
3135 REG_NOTES (insn
) = curr
;
3141 curr
= XEXP (curr
, 1);
3144 /* Did not find the note. */
3145 add_reg_note (insn
, note_type
, reg
);
3149 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3150 arguments. Return true if the register value described by MWS's
3151 mw_reg is known to be completely unused, and if mw_reg can therefore
3152 be used in a REG_UNUSED note. */
3155 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
3156 bitmap live
, bitmap artificial_uses
)
3160 /* If MWS describes a partial reference, create REG_UNUSED notes for
3161 individual hard registers. */
3162 if (mws
->flags
& DF_REF_PARTIAL
)
3165 /* Likewise if some part of the register is used. */
3166 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3167 if (bitmap_bit_p (live
, r
)
3168 || bitmap_bit_p (artificial_uses
, r
))
3171 gcc_assert (REG_P (mws
->mw_reg
));
3175 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3176 based on the bits in LIVE. Do not generate notes for registers in
3177 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3178 not generated if the reg is both read and written by the
3183 df_set_unused_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3184 bitmap live
, bitmap do_not_gen
,
3185 bitmap artificial_uses
)
3189 #ifdef REG_DEAD_DEBUGGING
3191 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
3192 mws
->start_regno
, mws
->end_regno
);
3195 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
3197 unsigned int regno
= mws
->start_regno
;
3198 old
= df_set_note (REG_UNUSED
, insn
, old
, mws
->mw_reg
);
3200 #ifdef REG_DEAD_DEBUGGING
3201 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3203 bitmap_set_bit (do_not_gen
, regno
);
3204 /* Only do this if the value is totally dead. */
3207 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3209 if (!bitmap_bit_p (live
, r
)
3210 && !bitmap_bit_p (artificial_uses
, r
))
3212 old
= df_set_note (REG_UNUSED
, insn
, old
, regno_reg_rtx
[r
]);
3213 #ifdef REG_DEAD_DEBUGGING
3214 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3217 bitmap_set_bit (do_not_gen
, r
);
3223 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3224 arguments. Return true if the register value described by MWS's
3225 mw_reg is known to be completely dead, and if mw_reg can therefore
3226 be used in a REG_DEAD note. */
3229 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
3230 bitmap live
, bitmap artificial_uses
,
3235 /* If MWS describes a partial reference, create REG_DEAD notes for
3236 individual hard registers. */
3237 if (mws
->flags
& DF_REF_PARTIAL
)
3240 /* Likewise if some part of the register is not dead. */
3241 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3242 if (bitmap_bit_p (live
, r
)
3243 || bitmap_bit_p (artificial_uses
, r
)
3244 || bitmap_bit_p (do_not_gen
, r
))
3247 gcc_assert (REG_P (mws
->mw_reg
));
3251 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3252 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3253 from being set if the instruction both reads and writes the
3257 df_set_dead_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3258 bitmap live
, bitmap do_not_gen
,
3259 bitmap artificial_uses
, bool *added_notes_p
)
3262 bool is_debug
= *added_notes_p
;
3264 *added_notes_p
= false;
3266 #ifdef REG_DEAD_DEBUGGING
3269 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3270 mws
->start_regno
, mws
->end_regno
);
3271 df_print_regset (dump_file
, do_not_gen
);
3272 fprintf (dump_file
, " live =");
3273 df_print_regset (dump_file
, live
);
3274 fprintf (dump_file
, " artificial uses =");
3275 df_print_regset (dump_file
, artificial_uses
);
3279 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3281 /* Add a dead note for the entire multi word register. */
3284 *added_notes_p
= true;
3287 old
= df_set_note (REG_DEAD
, insn
, old
, mws
->mw_reg
);
3288 #ifdef REG_DEAD_DEBUGGING
3289 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3294 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3295 if (!bitmap_bit_p (live
, r
)
3296 && !bitmap_bit_p (artificial_uses
, r
)
3297 && !bitmap_bit_p (do_not_gen
, r
))
3301 *added_notes_p
= true;
3304 old
= df_set_note (REG_DEAD
, insn
, old
, regno_reg_rtx
[r
]);
3305 #ifdef REG_DEAD_DEBUGGING
3306 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3314 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3315 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3318 df_create_unused_note (rtx insn
, rtx old
, df_ref def
,
3319 bitmap live
, bitmap artificial_uses
)
3321 unsigned int dregno
= DF_REF_REGNO (def
);
3323 #ifdef REG_DEAD_DEBUGGING
3326 fprintf (dump_file
, " regular looking at def ");
3327 df_ref_debug (def
, dump_file
);
3331 if (!((DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3332 || bitmap_bit_p (live
, dregno
)
3333 || bitmap_bit_p (artificial_uses
, dregno
)
3334 || df_ignore_stack_reg (dregno
)))
3336 rtx reg
= (DF_REF_LOC (def
))
3337 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3338 old
= df_set_note (REG_UNUSED
, insn
, old
, reg
);
3339 #ifdef REG_DEAD_DEBUGGING
3340 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3347 /* Node of a linked list of uses of dead REGs in debug insns. */
3348 struct dead_debug_use
3351 struct dead_debug_use
*next
;
3354 /* Linked list of the above, with a bitmap of the REGs in the
3358 struct dead_debug_use
*head
;
3363 /* Initialize DEBUG to an empty list, and clear USED, if given. */
3365 dead_debug_init (struct dead_debug
*debug
, bitmap used
)
3369 debug
->to_rescan
= NULL
;
3371 bitmap_clear (used
);
3374 /* Reset all debug insns with pending uses. Release the bitmap in it,
3375 unless it is USED. USED must be the same bitmap passed to
3378 dead_debug_finish (struct dead_debug
*debug
, bitmap used
)
3380 struct dead_debug_use
*head
;
3383 if (debug
->used
!= used
)
3384 BITMAP_FREE (debug
->used
);
3386 while ((head
= debug
->head
))
3388 insn
= DF_REF_INSN (head
->use
);
3389 if (!head
->next
|| DF_REF_INSN (head
->next
->use
) != insn
)
3391 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3392 df_insn_rescan_debug_internal (insn
);
3393 if (debug
->to_rescan
)
3394 bitmap_clear_bit (debug
->to_rescan
, INSN_UID (insn
));
3396 debug
->head
= head
->next
;
3400 if (debug
->to_rescan
)
3405 EXECUTE_IF_SET_IN_BITMAP (debug
->to_rescan
, 0, uid
, bi
)
3407 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
3409 df_insn_rescan (insn_info
->insn
);
3411 BITMAP_FREE (debug
->to_rescan
);
3415 /* Add USE to DEBUG. It must be a dead reference to UREGNO in a debug
3416 insn. Create a bitmap for DEBUG as needed. */
3418 dead_debug_add (struct dead_debug
*debug
, df_ref use
, unsigned int uregno
)
3420 struct dead_debug_use
*newddu
= XNEW (struct dead_debug_use
);
3423 newddu
->next
= debug
->head
;
3424 debug
->head
= newddu
;
3427 debug
->used
= BITMAP_ALLOC (NULL
);
3429 bitmap_set_bit (debug
->used
, uregno
);
3432 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3433 before INSN that binds the REG to a debug temp, and replace all
3434 uses of UREGNO in DEBUG with uses of the debug temp. INSN must be
3435 the insn where UREGNO dies. */
3437 dead_debug_insert_before (struct dead_debug
*debug
, unsigned int uregno
,
3440 struct dead_debug_use
**tailp
= &debug
->head
;
3441 struct dead_debug_use
*cur
;
3442 struct dead_debug_use
*uses
= NULL
;
3443 struct dead_debug_use
**usesp
= &uses
;
3448 if (!debug
->used
|| !bitmap_clear_bit (debug
->used
, uregno
))
3451 /* Move all uses of uregno from debug->head to uses, setting mode to
3452 the widest referenced mode. */
3453 while ((cur
= *tailp
))
3455 if (DF_REF_REGNO (cur
->use
) == uregno
)
3462 || (GET_MODE_BITSIZE (GET_MODE (reg
))
3463 < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur
->use
)))))
3464 reg
= *DF_REF_REAL_LOC (cur
->use
);
3467 tailp
= &(*tailp
)->next
;
3472 /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL). */
3473 dval
= make_debug_expr_from_rtl (reg
);
3475 /* Emit a debug bind insn before the insn in which reg dies. */
3476 bind
= gen_rtx_VAR_LOCATION (GET_MODE (reg
),
3477 DEBUG_EXPR_TREE_DECL (dval
), reg
,
3478 VAR_INIT_STATUS_INITIALIZED
);
3480 bind
= emit_debug_insn_before (bind
, insn
);
3481 df_insn_rescan (bind
);
3483 /* Adjust all uses. */
3484 while ((cur
= uses
))
3486 if (GET_MODE (*DF_REF_REAL_LOC (cur
->use
)) == GET_MODE (reg
))
3487 *DF_REF_REAL_LOC (cur
->use
) = dval
;
3489 *DF_REF_REAL_LOC (cur
->use
)
3490 = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur
->use
)), dval
);
3491 /* ??? Should we simplify subreg of subreg? */
3492 if (debug
->to_rescan
== NULL
)
3493 debug
->to_rescan
= BITMAP_ALLOC (NULL
);
3494 bitmap_set_bit (debug
->to_rescan
, INSN_UID (DF_REF_INSN (cur
->use
)));
3500 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3501 info: lifetime, bb, and number of defs and uses for basic block
3502 BB. The three bitvectors are scratch regs used here. */
3505 df_note_bb_compute (unsigned int bb_index
,
3506 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3508 basic_block bb
= BASIC_BLOCK (bb_index
);
3512 struct dead_debug debug
;
3514 dead_debug_init (&debug
, NULL
);
3516 bitmap_copy (live
, df_get_live_out (bb
));
3517 bitmap_clear (artificial_uses
);
3519 #ifdef REG_DEAD_DEBUGGING
3522 fprintf (dump_file
, "live at bottom ");
3523 df_print_regset (dump_file
, live
);
3527 /* Process the artificial defs and uses at the bottom of the block
3528 to begin processing. */
3529 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3531 df_ref def
= *def_rec
;
3532 #ifdef REG_DEAD_DEBUGGING
3534 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3537 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3538 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3541 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3543 df_ref use
= *use_rec
;
3544 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3546 unsigned int regno
= DF_REF_REGNO (use
);
3547 bitmap_set_bit (live
, regno
);
3549 /* Notes are not generated for any of the artificial registers
3550 at the bottom of the block. */
3551 bitmap_set_bit (artificial_uses
, regno
);
3555 #ifdef REG_DEAD_DEBUGGING
3558 fprintf (dump_file
, "live before artificials out ");
3559 df_print_regset (dump_file
, live
);
3563 FOR_BB_INSNS_REVERSE (bb
, insn
)
3565 unsigned int uid
= INSN_UID (insn
);
3566 struct df_mw_hardreg
**mws_rec
;
3568 rtx old_unused_notes
;
3574 debug_insn
= DEBUG_INSN_P (insn
);
3576 bitmap_clear (do_not_gen
);
3577 df_kill_notes (insn
, &old_dead_notes
, &old_unused_notes
);
3579 /* Process the defs. */
3582 #ifdef REG_DEAD_DEBUGGING
3585 fprintf (dump_file
, "processing call %d\n live =", INSN_UID (insn
));
3586 df_print_regset (dump_file
, live
);
3589 /* We only care about real sets for calls. Clobbers cannot
3590 be depended on to really die. */
3591 mws_rec
= DF_INSN_UID_MWS (uid
);
3594 struct df_mw_hardreg
*mws
= *mws_rec
;
3595 if ((DF_MWS_REG_DEF_P (mws
))
3596 && !df_ignore_stack_reg (mws
->start_regno
))
3598 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3599 mws
, live
, do_not_gen
,
3604 /* All of the defs except the return value are some sort of
3605 clobber. This code is for the return. */
3606 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3608 df_ref def
= *def_rec
;
3609 unsigned int dregno
= DF_REF_REGNO (def
);
3610 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3613 = df_create_unused_note (insn
, old_unused_notes
,
3614 def
, live
, artificial_uses
);
3615 bitmap_set_bit (do_not_gen
, dregno
);
3618 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3619 bitmap_clear_bit (live
, dregno
);
3625 mws_rec
= DF_INSN_UID_MWS (uid
);
3628 struct df_mw_hardreg
*mws
= *mws_rec
;
3629 if (DF_MWS_REG_DEF_P (mws
))
3631 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3632 mws
, live
, do_not_gen
,
3637 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3639 df_ref def
= *def_rec
;
3640 unsigned int dregno
= DF_REF_REGNO (def
);
3642 = df_create_unused_note (insn
, old_unused_notes
,
3643 def
, live
, artificial_uses
);
3645 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3646 bitmap_set_bit (do_not_gen
, dregno
);
3648 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3649 bitmap_clear_bit (live
, dregno
);
3653 /* Process the uses. */
3654 mws_rec
= DF_INSN_UID_MWS (uid
);
3657 struct df_mw_hardreg
*mws
= *mws_rec
;
3658 if ((DF_MWS_REG_DEF_P (mws
))
3659 && !df_ignore_stack_reg (mws
->start_regno
))
3661 bool really_add_notes
= debug_insn
!= 0;
3664 = df_set_dead_notes_for_mw (insn
, old_dead_notes
,
3665 mws
, live
, do_not_gen
,
3669 if (really_add_notes
)
3675 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3677 df_ref use
= *use_rec
;
3678 unsigned int uregno
= DF_REF_REGNO (use
);
3680 #ifdef REG_DEAD_DEBUGGING
3681 if (dump_file
&& !debug_insn
)
3683 fprintf (dump_file
, " regular looking at use ");
3684 df_ref_debug (use
, dump_file
);
3687 if (!bitmap_bit_p (live
, uregno
))
3693 dead_debug_add (&debug
, use
, uregno
);
3699 dead_debug_insert_before (&debug
, uregno
, insn
);
3701 if ( (!(DF_REF_FLAGS (use
)
3702 & (DF_REF_MW_HARDREG
| DF_REF_READ_WRITE
)))
3703 && (!bitmap_bit_p (do_not_gen
, uregno
))
3704 && (!bitmap_bit_p (artificial_uses
, uregno
))
3705 && (!df_ignore_stack_reg (uregno
)))
3707 rtx reg
= (DF_REF_LOC (use
))
3708 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3709 old_dead_notes
= df_set_note (REG_DEAD
, insn
, old_dead_notes
, reg
);
3711 #ifdef REG_DEAD_DEBUGGING
3712 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3715 /* This register is now live. */
3716 bitmap_set_bit (live
, uregno
);
3720 while (old_unused_notes
)
3722 rtx next
= XEXP (old_unused_notes
, 1);
3723 free_EXPR_LIST_node (old_unused_notes
);
3724 old_unused_notes
= next
;
3726 while (old_dead_notes
)
3728 rtx next
= XEXP (old_dead_notes
, 1);
3729 free_EXPR_LIST_node (old_dead_notes
);
3730 old_dead_notes
= next
;
3733 if (debug_insn
== -1)
3735 /* ??? We could probably do better here, replacing dead
3736 registers with their definitions. */
3737 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3738 df_insn_rescan_debug_internal (insn
);
3742 dead_debug_finish (&debug
, NULL
);
3746 /* Compute register info: lifetime, bb, and number of defs and uses. */
3748 df_note_compute (bitmap all_blocks
)
3750 unsigned int bb_index
;
3752 bitmap_head live
, do_not_gen
, artificial_uses
;
3754 bitmap_initialize (&live
, &df_bitmap_obstack
);
3755 bitmap_initialize (&do_not_gen
, &df_bitmap_obstack
);
3756 bitmap_initialize (&artificial_uses
, &df_bitmap_obstack
);
3758 #ifdef REG_DEAD_DEBUGGING
3760 print_rtl_with_bb (dump_file
, get_insns());
3763 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3765 df_note_bb_compute (bb_index
, &live
, &do_not_gen
, &artificial_uses
);
3768 bitmap_clear (&live
);
3769 bitmap_clear (&do_not_gen
);
3770 bitmap_clear (&artificial_uses
);
3774 /* Free all storage associated with the problem. */
3783 /* All of the information associated every instance of the problem. */
3785 static struct df_problem problem_NOTE
=
3787 DF_NOTE
, /* Problem id. */
3788 DF_NONE
, /* Direction. */
3789 df_note_alloc
, /* Allocate the problem specific data. */
3790 NULL
, /* Reset global information. */
3791 NULL
, /* Free basic block info. */
3792 df_note_compute
, /* Local compute function. */
3793 NULL
, /* Init the solution specific data. */
3794 NULL
, /* Iterative solver. */
3795 NULL
, /* Confluence operator 0. */
3796 NULL
, /* Confluence operator n. */
3797 NULL
, /* Transfer function. */
3798 NULL
, /* Finalize function. */
3799 df_note_free
, /* Free all of the problem information. */
3800 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3801 NULL
, /* Debugging. */
3802 NULL
, /* Debugging start block. */
3803 NULL
, /* Debugging end block. */
3804 NULL
, /* Incremental solution verify start. */
3805 NULL
, /* Incremental solution verify end. */
3806 &problem_LR
, /* Dependent problem. */
3807 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
3808 TV_DF_NOTE
, /* Timing variable. */
3809 false /* Reset blocks on dropping out of blocks_to_analyze. */
3813 /* Create a new DATAFLOW instance and add it to an existing instance
3814 of DF. The returned structure is what is used to get at the
3818 df_note_add_problem (void)
3820 df_add_problem (&problem_NOTE
);
3826 /*----------------------------------------------------------------------------
3827 Functions for simulating the effects of single insns.
3829 You can either simulate in the forwards direction, starting from
3830 the top of a block or the backwards direction from the end of the
3831 block. If you go backwards, defs are examined first to clear bits,
3832 then uses are examined to set bits. If you go forwards, defs are
3833 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3834 are examined to clear bits. In either case, the result of examining
3835 a def can be undone (respectively by a use or a REG_UNUSED note).
3837 If you start at the top of the block, use one of DF_LIVE_IN or
3838 DF_LR_IN. If you start at the bottom of the block use one of
3839 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3840 THEY WILL BE DESTROYED.
3841 ----------------------------------------------------------------------------*/
3844 /* Find the set of DEFs for INSN. */
3847 df_simulate_find_defs (rtx insn
, bitmap defs
)
3850 unsigned int uid
= INSN_UID (insn
);
3852 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3854 df_ref def
= *def_rec
;
3855 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3859 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3862 df_simulate_find_noclobber_defs (rtx insn
, bitmap defs
)
3865 unsigned int uid
= INSN_UID (insn
);
3867 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3869 df_ref def
= *def_rec
;
3870 if (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
3871 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3876 /* Simulate the effects of the defs of INSN on LIVE. */
3879 df_simulate_defs (rtx insn
, bitmap live
)
3882 unsigned int uid
= INSN_UID (insn
);
3884 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3886 df_ref def
= *def_rec
;
3887 unsigned int dregno
= DF_REF_REGNO (def
);
3889 /* If the def is to only part of the reg, it does
3890 not kill the other defs that reach here. */
3891 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3892 bitmap_clear_bit (live
, dregno
);
3897 /* Simulate the effects of the uses of INSN on LIVE. */
3900 df_simulate_uses (rtx insn
, bitmap live
)
3903 unsigned int uid
= INSN_UID (insn
);
3905 if (DEBUG_INSN_P (insn
))
3908 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3910 df_ref use
= *use_rec
;
3911 /* Add use to set of uses in this BB. */
3912 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3917 /* Add back the always live regs in BB to LIVE. */
3920 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3922 /* These regs are considered always live so if they end up dying
3923 because of some def, we need to bring the back again. */
3924 if (bb_has_eh_pred (bb
))
3925 bitmap_ior_into (live
, &df
->eh_block_artificial_uses
);
3927 bitmap_ior_into (live
, &df
->regular_block_artificial_uses
);
3931 /*----------------------------------------------------------------------------
3932 The following three functions are used only for BACKWARDS scanning:
3933 i.e. they process the defs before the uses.
3935 df_simulate_initialize_backwards should be called first with a
3936 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3937 df_simulate_one_insn_backwards should be called for each insn in
3938 the block, starting with the last one. Finally,
3939 df_simulate_finalize_backwards can be called to get a new value
3940 of the sets at the top of the block (this is rarely used).
3941 ----------------------------------------------------------------------------*/
3943 /* Apply the artificial uses and defs at the end of BB in a backwards
3947 df_simulate_initialize_backwards (basic_block bb
, bitmap live
)
3951 int bb_index
= bb
->index
;
3953 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3955 df_ref def
= *def_rec
;
3956 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3957 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3960 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3962 df_ref use
= *use_rec
;
3963 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3964 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3969 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3972 df_simulate_one_insn_backwards (basic_block bb
, rtx insn
, bitmap live
)
3974 if (!NONDEBUG_INSN_P (insn
))
3977 df_simulate_defs (insn
, live
);
3978 df_simulate_uses (insn
, live
);
3979 df_simulate_fixup_sets (bb
, live
);
3983 /* Apply the artificial uses and defs at the top of BB in a backwards
3987 df_simulate_finalize_backwards (basic_block bb
, bitmap live
)
3993 int bb_index
= bb
->index
;
3995 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3997 df_ref def
= *def_rec
;
3998 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3999 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
4003 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
4005 df_ref use
= *use_rec
;
4006 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
4007 bitmap_set_bit (live
, DF_REF_REGNO (use
));
4011 /*----------------------------------------------------------------------------
4012 The following three functions are used only for FORWARDS scanning:
4013 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
4014 Thus it is important to add the DF_NOTES problem to the stack of
4015 problems computed before using these functions.
4017 df_simulate_initialize_forwards should be called first with a
4018 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
4019 df_simulate_one_insn_forwards should be called for each insn in
4020 the block, starting with the first one.
4021 ----------------------------------------------------------------------------*/
4023 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
4024 DF_LR_IN for basic block BB, for forward scanning by marking artificial
4028 df_simulate_initialize_forwards (basic_block bb
, bitmap live
)
4031 int bb_index
= bb
->index
;
4033 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4035 df_ref def
= *def_rec
;
4036 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4037 bitmap_set_bit (live
, DF_REF_REGNO (def
));
4041 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4044 df_simulate_one_insn_forwards (basic_block bb
, rtx insn
, bitmap live
)
4047 if (! INSN_P (insn
))
4050 /* Make sure that DF_NOTE really is an active df problem. */
4051 gcc_assert (df_note
);
4053 /* Note that this is the opposite as how the problem is defined, because
4054 in the LR problem defs _kill_ liveness. However, they do so backwards,
4055 while here the scan is performed forwards! So, first assume that the
4056 def is live, and if this is not true REG_UNUSED notes will rectify the
4058 df_simulate_find_noclobber_defs (insn
, live
);
4060 /* Clear all of the registers that go dead. */
4061 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
4063 switch (REG_NOTE_KIND (link
))
4068 rtx reg
= XEXP (link
, 0);
4069 int regno
= REGNO (reg
);
4070 if (regno
< FIRST_PSEUDO_REGISTER
)
4072 int n
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
4074 bitmap_clear_bit (live
, regno
+ n
);
4077 bitmap_clear_bit (live
, regno
);
4084 df_simulate_fixup_sets (bb
, live
);
4089 /*----------------------------------------------------------------------------
4090 MULTIPLE DEFINITIONS
4092 Find the locations in the function reached by multiple definition sites
4093 for a live pseudo. In and out bitvectors are built for each basic
4094 block. They are restricted for efficiency to live registers.
4096 The gen and kill sets for the problem are obvious. Together they
4097 include all defined registers in a basic block; the gen set includes
4098 registers where a partial or conditional or may-clobber definition is
4099 last in the BB, while the kill set includes registers with a complete
4100 definition coming last. However, the computation of the dataflow
4101 itself is interesting.
4103 The idea behind it comes from SSA form's iterated dominance frontier
4104 criterion for inserting PHI functions. Just like in that case, we can use
4105 the dominance frontier to find places where multiple definitions meet;
4106 a register X defined in a basic block BB1 has multiple definitions in
4107 basic blocks in BB1's dominance frontier.
4109 So, the in-set of a basic block BB2 is not just the union of the
4110 out-sets of BB2's predecessors, but includes some more bits that come
4111 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4112 the previous paragraph). I called this set the init-set of BB2.
4114 (Note: I actually use the kill-set only to build the init-set.
4115 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4117 For example, if you have
4121 if <...> goto BB2 else goto BB3;
4129 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4130 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4131 not need to iterate the dominance frontier, because we do not insert
4132 anything like PHI functions there! Instead, dataflow will take care of
4133 propagating the information to BB3's successors.
4134 ---------------------------------------------------------------------------*/
4136 /* Private data used to verify the solution for this problem. */
4137 struct df_md_problem_data
4139 /* An obstack for the bitmaps we need for this problem. */
4140 bitmap_obstack md_bitmaps
;
4143 /* Scratch var used by transfer functions. This is used to do md analysis
4144 only for live registers. */
4145 static bitmap_head df_md_scratch
;
4149 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
4152 struct df_md_bb_info
*bb_info
= (struct df_md_bb_info
*) vbb_info
;
4155 bitmap_clear (&bb_info
->kill
);
4156 bitmap_clear (&bb_info
->gen
);
4157 bitmap_clear (&bb_info
->init
);
4158 bitmap_clear (&bb_info
->in
);
4159 bitmap_clear (&bb_info
->out
);
4164 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4165 not touched unless the block is new. */
4168 df_md_alloc (bitmap all_blocks
)
4170 unsigned int bb_index
;
4172 struct df_md_problem_data
*problem_data
;
4174 df_grow_bb_info (df_md
);
4175 if (df_md
->problem_data
)
4176 problem_data
= (struct df_md_problem_data
*) df_md
->problem_data
;
4179 problem_data
= XNEW (struct df_md_problem_data
);
4180 df_md
->problem_data
= problem_data
;
4181 bitmap_obstack_initialize (&problem_data
->md_bitmaps
);
4183 bitmap_initialize (&df_md_scratch
, &problem_data
->md_bitmaps
);
4185 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4187 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4188 /* When bitmaps are already initialized, just clear them. */
4189 if (bb_info
->init
.obstack
)
4191 bitmap_clear (&bb_info
->init
);
4192 bitmap_clear (&bb_info
->gen
);
4193 bitmap_clear (&bb_info
->kill
);
4194 bitmap_clear (&bb_info
->in
);
4195 bitmap_clear (&bb_info
->out
);
4199 bitmap_initialize (&bb_info
->init
, &problem_data
->md_bitmaps
);
4200 bitmap_initialize (&bb_info
->gen
, &problem_data
->md_bitmaps
);
4201 bitmap_initialize (&bb_info
->kill
, &problem_data
->md_bitmaps
);
4202 bitmap_initialize (&bb_info
->in
, &problem_data
->md_bitmaps
);
4203 bitmap_initialize (&bb_info
->out
, &problem_data
->md_bitmaps
);
4207 df_md
->optional_p
= true;
4210 /* Add the effect of the top artificial defs of BB to the multiple definitions
4214 df_md_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_md
)
4216 int bb_index
= bb
->index
;
4218 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4220 df_ref def
= *def_rec
;
4221 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4223 unsigned int dregno
= DF_REF_REGNO (def
);
4224 if (DF_REF_FLAGS (def
)
4225 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4226 bitmap_set_bit (local_md
, dregno
);
4228 bitmap_clear_bit (local_md
, dregno
);
4234 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4238 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
4241 unsigned uid
= INSN_UID (insn
);
4244 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4246 df_ref def
= *def_rec
;
4247 unsigned int dregno
= DF_REF_REGNO (def
);
4248 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4249 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4251 if (DF_REF_FLAGS (def
)
4252 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4253 bitmap_set_bit (local_md
, DF_REF_ID (def
));
4255 bitmap_clear_bit (local_md
, DF_REF_ID (def
));
4261 df_md_bb_local_compute_process_def (struct df_md_bb_info
*bb_info
,
4266 bitmap_clear (&seen_in_insn
);
4268 while ((def
= *def_rec
++) != NULL
)
4270 unsigned int dregno
= DF_REF_REGNO (def
);
4271 if (((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4272 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4273 && top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
4275 if (!bitmap_bit_p (&seen_in_insn
, dregno
))
4277 if (DF_REF_FLAGS (def
)
4278 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4280 bitmap_set_bit (&bb_info
->gen
, dregno
);
4281 bitmap_clear_bit (&bb_info
->kill
, dregno
);
4285 /* When we find a clobber and a regular def,
4286 make sure the regular def wins. */
4287 bitmap_set_bit (&seen_in_insn
, dregno
);
4288 bitmap_set_bit (&bb_info
->kill
, dregno
);
4289 bitmap_clear_bit (&bb_info
->gen
, dregno
);
4297 /* Compute local multiple def info for basic block BB. */
4300 df_md_bb_local_compute (unsigned int bb_index
)
4302 basic_block bb
= BASIC_BLOCK (bb_index
);
4303 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4306 /* Artificials are only hard regs. */
4307 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4308 df_md_bb_local_compute_process_def (bb_info
,
4309 df_get_artificial_defs (bb_index
),
4312 FOR_BB_INSNS (bb
, insn
)
4314 unsigned int uid
= INSN_UID (insn
);
4318 df_md_bb_local_compute_process_def (bb_info
, DF_INSN_UID_DEFS (uid
), 0);
4321 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4322 df_md_bb_local_compute_process_def (bb_info
,
4323 df_get_artificial_defs (bb_index
),
4327 /* Compute local reaching def info for each basic block within BLOCKS. */
4330 df_md_local_compute (bitmap all_blocks
)
4332 unsigned int bb_index
, df_bb_index
;
4333 bitmap_iterator bi1
, bi2
;
4335 bitmap_head
*frontiers
;
4337 bitmap_initialize (&seen_in_insn
, &bitmap_default_obstack
);
4339 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4341 df_md_bb_local_compute (bb_index
);
4344 bitmap_clear (&seen_in_insn
);
4346 frontiers
= XNEWVEC (bitmap_head
, last_basic_block
);
4348 bitmap_initialize (&frontiers
[bb
->index
], &bitmap_default_obstack
);
4350 compute_dominance_frontiers (frontiers
);
4352 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4353 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4355 bitmap kill
= &df_md_get_bb_info (bb_index
)->kill
;
4356 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[bb_index
], 0, df_bb_index
, bi2
)
4358 basic_block bb
= BASIC_BLOCK (df_bb_index
);
4359 if (bitmap_bit_p (all_blocks
, df_bb_index
))
4360 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index
)->init
, kill
,
4361 df_get_live_in (bb
));
4366 bitmap_clear (&frontiers
[bb
->index
]);
4371 /* Reset the global solution for recalculation. */
4374 df_md_reset (bitmap all_blocks
)
4376 unsigned int bb_index
;
4379 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4381 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4382 gcc_assert (bb_info
);
4383 bitmap_clear (&bb_info
->in
);
4384 bitmap_clear (&bb_info
->out
);
4389 df_md_transfer_function (int bb_index
)
4391 basic_block bb
= BASIC_BLOCK (bb_index
);
4392 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4393 bitmap in
= &bb_info
->in
;
4394 bitmap out
= &bb_info
->out
;
4395 bitmap gen
= &bb_info
->gen
;
4396 bitmap kill
= &bb_info
->kill
;
4398 /* We need to use a scratch set here so that the value returned from this
4399 function invocation properly reflects whether the sets changed in a
4400 significant way; i.e. not just because the live set was anded in. */
4401 bitmap_and (&df_md_scratch
, gen
, df_get_live_out (bb
));
4403 /* Multiple definitions of a register are not relevant if it is not
4404 live. Thus we trim the result to the places where it is live. */
4405 bitmap_and_into (in
, df_get_live_in (bb
));
4407 return bitmap_ior_and_compl (out
, &df_md_scratch
, in
, kill
);
4410 /* Initialize the solution bit vectors for problem. */
4413 df_md_init (bitmap all_blocks
)
4415 unsigned int bb_index
;
4418 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4420 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4422 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4423 df_md_transfer_function (bb_index
);
4428 df_md_confluence_0 (basic_block bb
)
4430 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4431 bitmap_copy (&bb_info
->in
, &bb_info
->init
);
4434 /* In of target gets or of out of source. */
4437 df_md_confluence_n (edge e
)
4439 bitmap op1
= &df_md_get_bb_info (e
->dest
->index
)->in
;
4440 bitmap op2
= &df_md_get_bb_info (e
->src
->index
)->out
;
4442 if (e
->flags
& EDGE_FAKE
)
4445 if (e
->flags
& EDGE_EH
)
4446 return bitmap_ior_and_compl_into (op1
, op2
,
4447 regs_invalidated_by_call_regset
);
4449 return bitmap_ior_into (op1
, op2
);
4452 /* Free all storage associated with the problem. */
4457 struct df_md_problem_data
*problem_data
4458 = (struct df_md_problem_data
*) df_md
->problem_data
;
4460 bitmap_obstack_release (&problem_data
->md_bitmaps
);
4461 free (problem_data
);
4462 df_md
->problem_data
= NULL
;
4464 df_md
->block_info_size
= 0;
4465 free (df_md
->block_info
);
4466 df_md
->block_info
= NULL
;
4471 /* Debugging info at top of bb. */
4474 df_md_top_dump (basic_block bb
, FILE *file
)
4476 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4480 fprintf (file
, ";; md in \t");
4481 df_print_regset (file
, &bb_info
->in
);
4482 fprintf (file
, ";; md init \t");
4483 df_print_regset (file
, &bb_info
->init
);
4484 fprintf (file
, ";; md gen \t");
4485 df_print_regset (file
, &bb_info
->gen
);
4486 fprintf (file
, ";; md kill \t");
4487 df_print_regset (file
, &bb_info
->kill
);
4490 /* Debugging info at bottom of bb. */
4493 df_md_bottom_dump (basic_block bb
, FILE *file
)
4495 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4499 fprintf (file
, ";; md out \t");
4500 df_print_regset (file
, &bb_info
->out
);
4503 static struct df_problem problem_MD
=
4505 DF_MD
, /* Problem id. */
4506 DF_FORWARD
, /* Direction. */
4507 df_md_alloc
, /* Allocate the problem specific data. */
4508 df_md_reset
, /* Reset global information. */
4509 df_md_free_bb_info
, /* Free basic block info. */
4510 df_md_local_compute
, /* Local compute function. */
4511 df_md_init
, /* Init the solution specific data. */
4512 df_worklist_dataflow
, /* Worklist solver. */
4513 df_md_confluence_0
, /* Confluence operator 0. */
4514 df_md_confluence_n
, /* Confluence operator n. */
4515 df_md_transfer_function
, /* Transfer function. */
4516 NULL
, /* Finalize function. */
4517 df_md_free
, /* Free all of the problem information. */
4518 df_md_free
, /* Remove this problem from the stack of dataflow problems. */
4519 NULL
, /* Debugging. */
4520 df_md_top_dump
, /* Debugging start block. */
4521 df_md_bottom_dump
, /* Debugging end block. */
4522 NULL
, /* Incremental solution verify start. */
4523 NULL
, /* Incremental solution verify end. */
4524 NULL
, /* Dependent problem. */
4525 sizeof (struct df_md_bb_info
),/* Size of entry of block_info array. */
4526 TV_DF_MD
, /* Timing variable. */
4527 false /* Reset blocks on dropping out of blocks_to_analyze. */
4530 /* Create a new MD instance and add it to the existing instance
4534 df_md_add_problem (void)
4536 df_add_problem (&problem_MD
);