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;
488 if (e->flags & EDGE_FAKE)
491 if (e->flags & EDGE_EH)
493 struct df_rd_problem_data *problem_data
494 = (struct df_rd_problem_data *) df_rd->problem_data;
495 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
496 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
501 bitmap_initialize (&tmp, &df_bitmap_obstack);
502 bitmap_copy (&tmp, op2);
503 bitmap_and_compl_into (&tmp, dense_invalidated);
505 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
507 bitmap_clear_range (&tmp,
508 DF_DEFS_BEGIN (regno),
509 DF_DEFS_COUNT (regno));
511 bitmap_ior_into (op1, &tmp);
515 bitmap_ior_into (op1, op2);
519 /* Transfer function. */
522 df_rd_transfer_function (int bb_index)
524 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
527 bitmap in = &bb_info->in;
528 bitmap out = &bb_info->out;
529 bitmap gen = &bb_info->gen;
530 bitmap kill = &bb_info->kill;
531 bitmap sparse_kill = &bb_info->sparse_kill;
533 if (bitmap_empty_p (sparse_kill))
534 return bitmap_ior_and_compl (out, gen, in, kill);
537 struct df_rd_problem_data *problem_data;
538 bool changed = false;
541 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
542 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
543 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
544 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
546 bitmap_copy (&tmp, in);
547 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
549 bitmap_clear_range (&tmp,
550 DF_DEFS_BEGIN (regno),
551 DF_DEFS_COUNT (regno));
553 bitmap_and_compl_into (&tmp, kill);
554 bitmap_ior_into (&tmp, gen);
555 changed = !bitmap_equal_p (&tmp, out);
568 /* Free all storage associated with the problem. */
573 struct df_rd_problem_data *problem_data
574 = (struct df_rd_problem_data *) df_rd->problem_data;
578 bitmap_obstack_release (&problem_data->rd_bitmaps);
580 df_rd->block_info_size = 0;
581 free (df_rd->block_info);
582 df_rd->block_info = NULL;
583 free (df_rd->problem_data);
589 /* Debugging info. */
592 df_rd_start_dump (FILE *file)
594 struct df_rd_problem_data *problem_data
595 = (struct df_rd_problem_data *) df_rd->problem_data;
596 unsigned int m = DF_REG_SIZE(df);
599 if (!df_rd->block_info)
602 fprintf (file, ";; Reaching defs:\n\n");
604 fprintf (file, " sparse invalidated \t");
605 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
606 fprintf (file, " dense invalidated \t");
607 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
609 for (regno = 0; regno < m; regno++)
610 if (DF_DEFS_COUNT (regno))
611 fprintf (file, "%d[%d,%d] ", regno,
612 DF_DEFS_BEGIN (regno),
613 DF_DEFS_COUNT (regno));
614 fprintf (file, "\n");
619 /* Debugging info at top of bb. */
622 df_rd_top_dump (basic_block bb, FILE *file)
624 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
628 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (&bb_info->in));
629 dump_bitmap (file, &bb_info->in);
630 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (&bb_info->gen));
631 dump_bitmap (file, &bb_info->gen);
632 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (&bb_info->kill));
633 dump_bitmap (file, &bb_info->kill);
637 /* Debugging info at top of bb. */
640 df_rd_bottom_dump (basic_block bb, FILE *file)
642 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
646 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (&bb_info->out));
647 dump_bitmap (file, &bb_info->out);
650 /* All of the information associated with every instance of the problem. */
652 static struct df_problem problem_RD =
654 DF_RD, /* Problem id. */
655 DF_FORWARD, /* Direction. */
656 df_rd_alloc, /* Allocate the problem specific data. */
657 NULL, /* Reset global information. */
658 df_rd_free_bb_info, /* Free basic block info. */
659 df_rd_local_compute, /* Local compute function. */
660 df_rd_init_solution, /* Init the solution specific data. */
661 df_worklist_dataflow, /* Worklist solver. */
662 NULL, /* Confluence operator 0. */
663 df_rd_confluence_n, /* Confluence operator n. */
664 df_rd_transfer_function, /* Transfer function. */
665 NULL, /* Finalize function. */
666 df_rd_free, /* Free all of the problem information. */
667 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
668 df_rd_start_dump, /* Debugging. */
669 df_rd_top_dump, /* Debugging start block. */
670 df_rd_bottom_dump, /* Debugging end block. */
671 NULL, /* Incremental solution verify start. */
672 NULL, /* Incremental solution verify end. */
673 NULL, /* Dependent problem. */
674 sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */
675 TV_DF_RD, /* Timing variable. */
676 true /* Reset blocks on dropping out of blocks_to_analyze. */
681 /* Create a new RD instance and add it to the existing instance
685 df_rd_add_problem (void)
687 df_add_problem (&problem_RD);
692 /*----------------------------------------------------------------------------
695 Find the locations in the function where any use of a pseudo can
696 reach in the backwards direction. In and out bitvectors are built
697 for each basic block. The regno is used to index into these sets.
698 See df.h for details.
699 ----------------------------------------------------------------------------*/
701 /* Private data used to verify the solution for this problem. */
702 struct df_lr_problem_data
706 /* An obstack for the bitmaps we need for this problem. */
707 bitmap_obstack lr_bitmaps;
710 /* Free basic block info. */
713 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
716 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
719 bitmap_clear (&bb_info->use);
720 bitmap_clear (&bb_info->def);
721 bitmap_clear (&bb_info->in);
722 bitmap_clear (&bb_info->out);
727 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
728 not touched unless the block is new. */
731 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
733 unsigned int bb_index;
735 struct df_lr_problem_data *problem_data;
737 df_grow_bb_info (df_lr);
738 if (df_lr->problem_data)
739 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
742 problem_data = XNEW (struct df_lr_problem_data);
743 df_lr->problem_data = problem_data;
745 problem_data->out = NULL;
746 problem_data->in = NULL;
747 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
750 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
752 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
754 /* When bitmaps are already initialized, just clear them. */
755 if (bb_info->use.obstack)
757 bitmap_clear (&bb_info->def);
758 bitmap_clear (&bb_info->use);
762 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
763 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
764 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
765 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
769 df_lr->optional_p = false;
773 /* Reset the global solution for recalculation. */
776 df_lr_reset (bitmap all_blocks)
778 unsigned int bb_index;
781 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
783 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
784 gcc_assert (bb_info);
785 bitmap_clear (&bb_info->in);
786 bitmap_clear (&bb_info->out);
791 /* Compute local live register info for basic block BB. */
794 df_lr_bb_local_compute (unsigned int bb_index)
796 basic_block bb = BASIC_BLOCK (bb_index);
797 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
802 /* Process the registers set in an exception handler. */
803 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
805 df_ref def = *def_rec;
806 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
808 unsigned int dregno = DF_REF_REGNO (def);
809 bitmap_set_bit (&bb_info->def, dregno);
810 bitmap_clear_bit (&bb_info->use, dregno);
814 /* Process the hardware registers that are always live. */
815 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
817 df_ref use = *use_rec;
818 /* Add use to set of uses in this BB. */
819 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
820 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
823 FOR_BB_INSNS_REVERSE (bb, insn)
825 unsigned int uid = INSN_UID (insn);
827 if (!NONDEBUG_INSN_P (insn))
830 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
832 df_ref def = *def_rec;
833 /* If the def is to only part of the reg, it does
834 not kill the other defs that reach here. */
835 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
837 unsigned int dregno = DF_REF_REGNO (def);
838 bitmap_set_bit (&bb_info->def, dregno);
839 bitmap_clear_bit (&bb_info->use, dregno);
843 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
845 df_ref use = *use_rec;
846 /* Add use to set of uses in this BB. */
847 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
851 /* Process the registers set in an exception handler or the hard
852 frame pointer if this block is the target of a non local
854 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
856 df_ref def = *def_rec;
857 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
859 unsigned int dregno = DF_REF_REGNO (def);
860 bitmap_set_bit (&bb_info->def, dregno);
861 bitmap_clear_bit (&bb_info->use, dregno);
866 /* Process the uses that are live into an exception handler. */
867 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
869 df_ref use = *use_rec;
870 /* Add use to set of uses in this BB. */
871 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
872 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
876 /* If the df_live problem is not defined, such as at -O0 and -O1, we
877 still need to keep the luids up to date. This is normally done
878 in the df_live problem since this problem has a forwards
881 df_recompute_luids (bb);
885 /* Compute local live register info for each basic block within BLOCKS. */
888 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
890 unsigned int bb_index;
893 bitmap_clear (&df->hardware_regs_used);
895 /* The all-important stack pointer must always be live. */
896 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
898 /* Before reload, there are a few registers that must be forced
899 live everywhere -- which might not already be the case for
900 blocks within infinite loops. */
901 if (!reload_completed)
903 /* Any reference to any pseudo before reload is a potential
904 reference of the frame pointer. */
905 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
907 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
908 /* Pseudos with argument area equivalences may require
909 reloading via the argument pointer. */
910 if (fixed_regs[ARG_POINTER_REGNUM])
911 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
914 /* Any constant, or pseudo with constant equivalences, may
915 require reloading from memory using the pic register. */
916 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
917 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
918 bitmap_set_bit (&df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
921 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
923 if (bb_index == EXIT_BLOCK)
925 /* The exit block is special for this problem and its bits are
926 computed from thin air. */
927 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
928 bitmap_copy (&bb_info->use, df->exit_block_uses);
931 df_lr_bb_local_compute (bb_index);
934 bitmap_clear (df_lr->out_of_date_transfer_functions);
938 /* Initialize the solution vectors. */
941 df_lr_init (bitmap all_blocks)
943 unsigned int bb_index;
946 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
948 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
949 bitmap_copy (&bb_info->in, &bb_info->use);
950 bitmap_clear (&bb_info->out);
955 /* Confluence function that processes infinite loops. This might be a
956 noreturn function that throws. And even if it isn't, getting the
957 unwind info right helps debugging. */
959 df_lr_confluence_0 (basic_block bb)
961 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
962 if (bb != EXIT_BLOCK_PTR)
963 bitmap_copy (op1, &df->hardware_regs_used);
967 /* Confluence function that ignores fake edges. */
970 df_lr_confluence_n (edge e)
972 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
973 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
975 /* Call-clobbered registers die across exception and call edges. */
976 /* ??? Abnormal call edges ignored for the moment, as this gets
977 confused by sibling call edges, which crashes reg-stack. */
978 if (e->flags & EDGE_EH)
979 bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
981 bitmap_ior_into (op1, op2);
983 bitmap_ior_into (op1, &df->hardware_regs_used);
987 /* Transfer function. */
990 df_lr_transfer_function (int bb_index)
992 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
993 bitmap in = &bb_info->in;
994 bitmap out = &bb_info->out;
995 bitmap use = &bb_info->use;
996 bitmap def = &bb_info->def;
998 return bitmap_ior_and_compl (in, use, out, def);
1002 /* Run the fast dce as a side effect of building LR. */
1005 df_lr_finalize (bitmap all_blocks)
1007 df_lr->solutions_dirty = false;
1008 if (df->changeable_flags & DF_LR_RUN_DCE)
1012 /* If dce deletes some instructions, we need to recompute the lr
1013 solution before proceeding further. The problem is that fast
1014 dce is a pessimestic dataflow algorithm. In the case where
1015 it deletes a statement S inside of a loop, the uses inside of
1016 S may not be deleted from the dataflow solution because they
1017 were carried around the loop. While it is conservatively
1018 correct to leave these extra bits, the standards of df
1019 require that we maintain the best possible (least fixed
1020 point) solution. The only way to do that is to redo the
1021 iteration from the beginning. See PR35805 for an
1023 if (df_lr->solutions_dirty)
1025 df_clear_flags (DF_LR_RUN_DCE);
1026 df_lr_alloc (all_blocks);
1027 df_lr_local_compute (all_blocks);
1028 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1029 df_lr_finalize (all_blocks);
1030 df_set_flags (DF_LR_RUN_DCE);
1036 /* Free all storage associated with the problem. */
1041 struct df_lr_problem_data *problem_data
1042 = (struct df_lr_problem_data *) df_lr->problem_data;
1043 if (df_lr->block_info)
1046 df_lr->block_info_size = 0;
1047 free (df_lr->block_info);
1048 df_lr->block_info = NULL;
1049 bitmap_obstack_release (&problem_data->lr_bitmaps);
1050 free (df_lr->problem_data);
1051 df_lr->problem_data = NULL;
1054 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1059 /* Debugging info at top of bb. */
1062 df_lr_top_dump (basic_block bb, FILE *file)
1064 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1065 struct df_lr_problem_data *problem_data;
1069 fprintf (file, ";; lr in \t");
1070 df_print_regset (file, &bb_info->in);
1071 if (df_lr->problem_data)
1073 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1074 if (problem_data->in)
1076 fprintf (file, ";; old in \t");
1077 df_print_regset (file, &problem_data->in[bb->index]);
1080 fprintf (file, ";; lr use \t");
1081 df_print_regset (file, &bb_info->use);
1082 fprintf (file, ";; lr def \t");
1083 df_print_regset (file, &bb_info->def);
1087 /* Debugging info at bottom of bb. */
1090 df_lr_bottom_dump (basic_block bb, FILE *file)
1092 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1093 struct df_lr_problem_data *problem_data;
1097 fprintf (file, ";; lr out \t");
1098 df_print_regset (file, &bb_info->out);
1099 if (df_lr->problem_data)
1101 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1102 if (problem_data->out)
1104 fprintf (file, ";; old out \t");
1105 df_print_regset (file, &problem_data->out[bb->index]);
1111 /* Build the datastructure to verify that the solution to the dataflow
1112 equations is not dirty. */
1115 df_lr_verify_solution_start (void)
1118 struct df_lr_problem_data *problem_data;
1119 if (df_lr->solutions_dirty)
1122 /* Set it true so that the solution is recomputed. */
1123 df_lr->solutions_dirty = true;
1125 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1126 problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
1127 problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
1131 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1132 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1133 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1134 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1139 /* Compare the saved datastructure and the new solution to the dataflow
1143 df_lr_verify_solution_end (void)
1145 struct df_lr_problem_data *problem_data;
1148 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1150 if (!problem_data->out)
1153 if (df_lr->solutions_dirty)
1154 /* Do not check if the solution is still dirty. See the comment
1155 in df_lr_finalize for details. */
1156 df_lr->solutions_dirty = false;
1160 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1161 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1163 /*df_dump (stderr);*/
1168 /* Cannot delete them immediately because you may want to dump them
1169 if the comparison fails. */
1172 bitmap_clear (&problem_data->in[bb->index]);
1173 bitmap_clear (&problem_data->out[bb->index]);
1176 free (problem_data->in);
1177 free (problem_data->out);
1178 problem_data->in = NULL;
1179 problem_data->out = NULL;
1183 /* All of the information associated with every instance of the problem. */
1185 static struct df_problem problem_LR =
1187 DF_LR, /* Problem id. */
1188 DF_BACKWARD, /* Direction. */
1189 df_lr_alloc, /* Allocate the problem specific data. */
1190 df_lr_reset, /* Reset global information. */
1191 df_lr_free_bb_info, /* Free basic block info. */
1192 df_lr_local_compute, /* Local compute function. */
1193 df_lr_init, /* Init the solution specific data. */
1194 df_worklist_dataflow, /* Worklist solver. */
1195 df_lr_confluence_0, /* Confluence operator 0. */
1196 df_lr_confluence_n, /* Confluence operator n. */
1197 df_lr_transfer_function, /* Transfer function. */
1198 df_lr_finalize, /* Finalize function. */
1199 df_lr_free, /* Free all of the problem information. */
1200 NULL, /* Remove this problem from the stack of dataflow problems. */
1201 NULL, /* Debugging. */
1202 df_lr_top_dump, /* Debugging start block. */
1203 df_lr_bottom_dump, /* Debugging end block. */
1204 df_lr_verify_solution_start,/* Incremental solution verify start. */
1205 df_lr_verify_solution_end, /* Incremental solution verify end. */
1206 NULL, /* Dependent problem. */
1207 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */
1208 TV_DF_LR, /* Timing variable. */
1209 false /* Reset blocks on dropping out of blocks_to_analyze. */
1213 /* Create a new DATAFLOW instance and add it to an existing instance
1214 of DF. The returned structure is what is used to get at the
1218 df_lr_add_problem (void)
1220 df_add_problem (&problem_LR);
1221 /* These will be initialized when df_scan_blocks processes each
1223 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1227 /* Verify that all of the lr related info is consistent and
1231 df_lr_verify_transfer_functions (void)
1234 bitmap_head saved_def;
1235 bitmap_head saved_use;
1236 bitmap_head all_blocks;
1241 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1242 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1243 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1247 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1248 bitmap_set_bit (&all_blocks, bb->index);
1252 /* Make a copy of the transfer functions and then compute
1253 new ones to see if the transfer functions have
1255 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1258 bitmap_copy (&saved_def, &bb_info->def);
1259 bitmap_copy (&saved_use, &bb_info->use);
1260 bitmap_clear (&bb_info->def);
1261 bitmap_clear (&bb_info->use);
1263 df_lr_bb_local_compute (bb->index);
1264 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1265 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1270 /* If we do not have basic block info, the block must be in
1271 the list of dirty blocks or else some one has added a
1272 block behind our backs. */
1273 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1276 /* Make sure no one created a block without following
1278 gcc_assert (df_scan_get_bb_info (bb->index));
1281 /* Make sure there are no dirty bits in blocks that have been deleted. */
1282 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1285 bitmap_clear (&saved_def);
1286 bitmap_clear (&saved_use);
1287 bitmap_clear (&all_blocks);
1292 /*----------------------------------------------------------------------------
1293 LIVE AND MUST-INITIALIZED REGISTERS.
1295 This problem first computes the IN and OUT bitvectors for the
1296 must-initialized registers problems, which is a forward problem.
1297 It gives the set of registers for which we MUST have an available
1298 definition on any path from the entry block to the entry/exit of
1299 a basic block. Sets generate a definition, while clobbers kill
1302 In and out bitvectors are built for each basic block and are indexed by
1303 regnum (see df.h for details). In and out bitvectors in struct
1304 df_live_bb_info actually refers to the must-initialized problem;
1306 Then, the in and out sets for the LIVE problem itself are computed.
1307 These are the logical AND of the IN and OUT sets from the LR problem
1308 and the must-initialized problem.
1309 ----------------------------------------------------------------------------*/
1311 /* Private data used to verify the solution for this problem. */
1312 struct df_live_problem_data
1316 /* An obstack for the bitmaps we need for this problem. */
1317 bitmap_obstack live_bitmaps;
1320 /* Scratch var used by transfer functions. This is used to implement
1321 an optimization to reduce the amount of space used to compute the
1322 combined lr and live analysis. */
1323 static bitmap_head df_live_scratch;
1326 /* Free basic block info. */
1329 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1332 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1335 bitmap_clear (&bb_info->gen);
1336 bitmap_clear (&bb_info->kill);
1337 bitmap_clear (&bb_info->in);
1338 bitmap_clear (&bb_info->out);
1343 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1344 not touched unless the block is new. */
1347 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1349 unsigned int bb_index;
1351 struct df_live_problem_data *problem_data;
1353 if (df_live->problem_data)
1354 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1357 problem_data = XNEW (struct df_live_problem_data);
1358 df_live->problem_data = problem_data;
1360 problem_data->out = NULL;
1361 problem_data->in = NULL;
1362 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1363 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1366 df_grow_bb_info (df_live);
1368 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1370 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1372 /* When bitmaps are already initialized, just clear them. */
1373 if (bb_info->kill.obstack)
1375 bitmap_clear (&bb_info->kill);
1376 bitmap_clear (&bb_info->gen);
1380 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1381 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1382 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1383 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1386 df_live->optional_p = (optimize <= 1);
1390 /* Reset the global solution for recalculation. */
1393 df_live_reset (bitmap all_blocks)
1395 unsigned int bb_index;
1398 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1400 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1401 gcc_assert (bb_info);
1402 bitmap_clear (&bb_info->in);
1403 bitmap_clear (&bb_info->out);
1408 /* Compute local uninitialized register info for basic block BB. */
1411 df_live_bb_local_compute (unsigned int bb_index)
1413 basic_block bb = BASIC_BLOCK (bb_index);
1414 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1419 FOR_BB_INSNS (bb, insn)
1421 unsigned int uid = INSN_UID (insn);
1422 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1424 /* Inserting labels does not always trigger the incremental
1428 gcc_assert (!INSN_P (insn));
1429 insn_info = df_insn_create_insn_record (insn);
1432 DF_INSN_INFO_LUID (insn_info) = luid;
1437 for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
1439 df_ref def = *def_rec;
1440 unsigned int regno = DF_REF_REGNO (def);
1442 if (DF_REF_FLAGS_IS_SET (def,
1443 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1444 /* All partial or conditional def
1445 seen are included in the gen set. */
1446 bitmap_set_bit (&bb_info->gen, regno);
1447 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1448 /* Only must clobbers for the entire reg destroy the
1450 bitmap_set_bit (&bb_info->kill, regno);
1451 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1452 bitmap_set_bit (&bb_info->gen, regno);
1456 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1458 df_ref def = *def_rec;
1459 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1464 /* Compute local uninitialized register info. */
1467 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1469 unsigned int bb_index;
1472 df_grow_insn_info ();
1474 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1477 df_live_bb_local_compute (bb_index);
1480 bitmap_clear (df_live->out_of_date_transfer_functions);
1484 /* Initialize the solution vectors. */
1487 df_live_init (bitmap all_blocks)
1489 unsigned int bb_index;
1492 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1494 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1495 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1497 /* No register may reach a location where it is not used. Thus
1498 we trim the rr result to the places where it is used. */
1499 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1500 bitmap_clear (&bb_info->in);
1504 /* Forward confluence function that ignores fake edges. */
1507 df_live_confluence_n (edge e)
1509 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1510 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1512 if (e->flags & EDGE_FAKE)
1515 bitmap_ior_into (op1, op2);
1519 /* Transfer function for the forwards must-initialized problem. */
1522 df_live_transfer_function (int bb_index)
1524 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1525 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1526 bitmap in = &bb_info->in;
1527 bitmap out = &bb_info->out;
1528 bitmap gen = &bb_info->gen;
1529 bitmap kill = &bb_info->kill;
1531 /* We need to use a scratch set here so that the value returned from this
1532 function invocation properly reflects whether the sets changed in a
1533 significant way; i.e. not just because the lr set was anded in. */
1534 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1535 /* No register may reach a location where it is not used. Thus
1536 we trim the rr result to the places where it is used. */
1537 bitmap_and_into (in, &bb_lr_info->in);
1539 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1543 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1546 df_live_finalize (bitmap all_blocks)
1549 if (df_live->solutions_dirty)
1552 unsigned int bb_index;
1554 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1556 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1557 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1559 /* No register may reach a location where it is not used. Thus
1560 we trim the rr result to the places where it is used. */
1561 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1562 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1565 df_live->solutions_dirty = false;
1570 /* Free all storage associated with the problem. */
1575 struct df_live_problem_data *problem_data
1576 = (struct df_live_problem_data *) df_live->problem_data;
1577 if (df_live->block_info)
1579 df_live->block_info_size = 0;
1580 free (df_live->block_info);
1581 df_live->block_info = NULL;
1582 bitmap_clear (&df_live_scratch);
1583 bitmap_obstack_release (&problem_data->live_bitmaps);
1584 free (problem_data);
1585 df_live->problem_data = NULL;
1587 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1592 /* Debugging info at top of bb. */
1595 df_live_top_dump (basic_block bb, FILE *file)
1597 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1598 struct df_live_problem_data *problem_data;
1603 fprintf (file, ";; live in \t");
1604 df_print_regset (file, &bb_info->in);
1605 if (df_live->problem_data)
1607 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1608 if (problem_data->in)
1610 fprintf (file, ";; old in \t");
1611 df_print_regset (file, &problem_data->in[bb->index]);
1614 fprintf (file, ";; live gen \t");
1615 df_print_regset (file, &bb_info->gen);
1616 fprintf (file, ";; live kill\t");
1617 df_print_regset (file, &bb_info->kill);
1621 /* Debugging info at bottom of bb. */
1624 df_live_bottom_dump (basic_block bb, FILE *file)
1626 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1627 struct df_live_problem_data *problem_data;
1632 fprintf (file, ";; live out \t");
1633 df_print_regset (file, &bb_info->out);
1634 if (df_live->problem_data)
1636 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1637 if (problem_data->out)
1639 fprintf (file, ";; old out \t");
1640 df_print_regset (file, &problem_data->out[bb->index]);
1646 /* Build the datastructure to verify that the solution to the dataflow
1647 equations is not dirty. */
1650 df_live_verify_solution_start (void)
1653 struct df_live_problem_data *problem_data;
1654 if (df_live->solutions_dirty)
1657 /* Set it true so that the solution is recomputed. */
1658 df_live->solutions_dirty = true;
1660 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1661 problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
1662 problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
1666 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1667 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1668 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1669 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1674 /* Compare the saved datastructure and the new solution to the dataflow
1678 df_live_verify_solution_end (void)
1680 struct df_live_problem_data *problem_data;
1683 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1684 if (!problem_data->out)
1689 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1690 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1692 /*df_dump (stderr);*/
1697 /* Cannot delete them immediately because you may want to dump them
1698 if the comparison fails. */
1701 bitmap_clear (&problem_data->in[bb->index]);
1702 bitmap_clear (&problem_data->out[bb->index]);
1705 free (problem_data->in);
1706 free (problem_data->out);
1707 free (problem_data);
1708 df_live->problem_data = NULL;
1712 /* All of the information associated with every instance of the problem. */
1714 static struct df_problem problem_LIVE =
1716 DF_LIVE, /* Problem id. */
1717 DF_FORWARD, /* Direction. */
1718 df_live_alloc, /* Allocate the problem specific data. */
1719 df_live_reset, /* Reset global information. */
1720 df_live_free_bb_info, /* Free basic block info. */
1721 df_live_local_compute, /* Local compute function. */
1722 df_live_init, /* Init the solution specific data. */
1723 df_worklist_dataflow, /* Worklist solver. */
1724 NULL, /* Confluence operator 0. */
1725 df_live_confluence_n, /* Confluence operator n. */
1726 df_live_transfer_function, /* Transfer function. */
1727 df_live_finalize, /* Finalize function. */
1728 df_live_free, /* Free all of the problem information. */
1729 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1730 NULL, /* Debugging. */
1731 df_live_top_dump, /* Debugging start block. */
1732 df_live_bottom_dump, /* Debugging end block. */
1733 df_live_verify_solution_start,/* Incremental solution verify start. */
1734 df_live_verify_solution_end, /* Incremental solution verify end. */
1735 &problem_LR, /* Dependent problem. */
1736 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */
1737 TV_DF_LIVE, /* Timing variable. */
1738 false /* Reset blocks on dropping out of blocks_to_analyze. */
1742 /* Create a new DATAFLOW instance and add it to an existing instance
1743 of DF. The returned structure is what is used to get at the
1747 df_live_add_problem (void)
1749 df_add_problem (&problem_LIVE);
1750 /* These will be initialized when df_scan_blocks processes each
1752 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1756 /* Set all of the blocks as dirty. This needs to be done if this
1757 problem is added after all of the insns have been scanned. */
1760 df_live_set_all_dirty (void)
1764 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1769 /* Verify that all of the lr related info is consistent and
1773 df_live_verify_transfer_functions (void)
1776 bitmap_head saved_gen;
1777 bitmap_head saved_kill;
1778 bitmap_head all_blocks;
1783 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1784 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1785 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1787 df_grow_insn_info ();
1791 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1792 bitmap_set_bit (&all_blocks, bb->index);
1796 /* Make a copy of the transfer functions and then compute
1797 new ones to see if the transfer functions have
1799 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1802 bitmap_copy (&saved_gen, &bb_info->gen);
1803 bitmap_copy (&saved_kill, &bb_info->kill);
1804 bitmap_clear (&bb_info->gen);
1805 bitmap_clear (&bb_info->kill);
1807 df_live_bb_local_compute (bb->index);
1808 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1809 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1814 /* If we do not have basic block info, the block must be in
1815 the list of dirty blocks or else some one has added a
1816 block behind our backs. */
1817 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1820 /* Make sure no one created a block without following
1822 gcc_assert (df_scan_get_bb_info (bb->index));
1825 /* Make sure there are no dirty bits in blocks that have been deleted. */
1826 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1828 bitmap_clear (&saved_gen);
1829 bitmap_clear (&saved_kill);
1830 bitmap_clear (&all_blocks);
1833 /*----------------------------------------------------------------------------
1834 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1836 Link either the defs to the uses and / or the uses to the defs.
1838 These problems are set up like the other dataflow problems so that
1839 they nicely fit into the framework. They are much simpler and only
1840 involve a single traversal of instructions and an examination of
1841 the reaching defs information (the dependent problem).
1842 ----------------------------------------------------------------------------*/
1844 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1846 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1849 df_chain_create (df_ref src, df_ref dst)
1851 struct df_link *head = DF_REF_CHAIN (src);
1852 struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1854 DF_REF_CHAIN (src) = link;
1861 /* Delete any du or ud chains that start at REF and point to
1864 df_chain_unlink_1 (df_ref ref, df_ref target)
1866 struct df_link *chain = DF_REF_CHAIN (ref);
1867 struct df_link *prev = NULL;
1871 if (chain->ref == target)
1874 prev->next = chain->next;
1876 DF_REF_CHAIN (ref) = chain->next;
1877 pool_free (df_chain->block_pool, chain);
1881 chain = chain->next;
1886 /* Delete a du or ud chain that leave or point to REF. */
1889 df_chain_unlink (df_ref ref)
1891 struct df_link *chain = DF_REF_CHAIN (ref);
1894 struct df_link *next = chain->next;
1895 /* Delete the other side if it exists. */
1896 df_chain_unlink_1 (chain->ref, ref);
1897 pool_free (df_chain->block_pool, chain);
1900 DF_REF_CHAIN (ref) = NULL;
1904 /* Copy the du or ud chain starting at FROM_REF and attach it to
1908 df_chain_copy (df_ref to_ref,
1909 struct df_link *from_ref)
1913 df_chain_create (to_ref, from_ref->ref);
1914 from_ref = from_ref->next;
1919 /* Remove this problem from the stack of dataflow problems. */
1922 df_chain_remove_problem (void)
1925 unsigned int bb_index;
1927 /* Wholesale destruction of the old chains. */
1928 if (df_chain->block_pool)
1929 free_alloc_pool (df_chain->block_pool);
1931 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1936 basic_block bb = BASIC_BLOCK (bb_index);
1938 if (df_chain_problem_p (DF_DU_CHAIN))
1939 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1940 DF_REF_CHAIN (*def_rec) = NULL;
1941 if (df_chain_problem_p (DF_UD_CHAIN))
1942 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1943 DF_REF_CHAIN (*use_rec) = NULL;
1945 FOR_BB_INSNS (bb, insn)
1947 unsigned int uid = INSN_UID (insn);
1951 if (df_chain_problem_p (DF_DU_CHAIN))
1952 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1953 DF_REF_CHAIN (*def_rec) = NULL;
1954 if (df_chain_problem_p (DF_UD_CHAIN))
1956 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1957 DF_REF_CHAIN (*use_rec) = NULL;
1958 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1959 DF_REF_CHAIN (*use_rec) = NULL;
1965 bitmap_clear (df_chain->out_of_date_transfer_functions);
1966 df_chain->block_pool = NULL;
1970 /* Remove the chain problem completely. */
1973 df_chain_fully_remove_problem (void)
1975 df_chain_remove_problem ();
1976 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1981 /* Create def-use or use-def chains. */
1984 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1986 df_chain_remove_problem ();
1987 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
1988 sizeof (struct df_link), 50);
1989 df_chain->optional_p = true;
1993 /* Reset all of the chains when the set of basic blocks changes. */
1996 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
1998 df_chain_remove_problem ();
2002 /* Create the chains for a list of USEs. */
2005 df_chain_create_bb_process_use (bitmap local_rd,
2010 unsigned int def_index;
2014 df_ref use = *use_rec;
2015 unsigned int uregno = DF_REF_REGNO (use);
2016 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2017 || (uregno >= FIRST_PSEUDO_REGISTER))
2019 /* Do not want to go through this for an uninitialized var. */
2020 int count = DF_DEFS_COUNT (uregno);
2023 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2025 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2026 unsigned int last_index = first_index + count - 1;
2028 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2031 if (def_index > last_index)
2034 def = DF_DEFS_GET (def_index);
2035 if (df_chain_problem_p (DF_DU_CHAIN))
2036 df_chain_create (def, use);
2037 if (df_chain_problem_p (DF_UD_CHAIN))
2038 df_chain_create (use, def);
2049 /* Create chains from reaching defs bitmaps for basic block BB. */
2052 df_chain_create_bb (unsigned int bb_index)
2054 basic_block bb = BASIC_BLOCK (bb_index);
2055 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2059 bitmap_initialize (&cpy, &bitmap_default_obstack);
2060 bitmap_copy (&cpy, &bb_info->in);
2061 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2063 /* Since we are going forwards, process the artificial uses first
2064 then the artificial defs second. */
2067 /* Create the chains for the artificial uses from the EH_USES at the
2068 beginning of the block. */
2070 /* Artificials are only hard regs. */
2071 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2072 df_chain_create_bb_process_use (&cpy,
2073 df_get_artificial_uses (bb->index),
2077 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2079 /* Process the regular instructions next. */
2080 FOR_BB_INSNS (bb, insn)
2083 unsigned int uid = INSN_UID (insn);
2085 /* First scan the uses and link them up with the defs that remain
2086 in the cpy vector. */
2087 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2088 if (df->changeable_flags & DF_EQ_NOTES)
2089 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2091 /* Since we are going forwards, process the defs second. */
2092 df_rd_simulate_one_insn (bb, insn, &cpy);
2095 /* Create the chains for the artificial uses of the hard registers
2096 at the end of the block. */
2097 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2098 df_chain_create_bb_process_use (&cpy,
2099 df_get_artificial_uses (bb->index),
2102 bitmap_clear (&cpy);
2105 /* Create def-use chains from reaching use bitmaps for basic blocks
2109 df_chain_finalize (bitmap all_blocks)
2111 unsigned int bb_index;
2114 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2116 df_chain_create_bb (bb_index);
2121 /* Free all storage associated with the problem. */
2124 df_chain_free (void)
2126 free_alloc_pool (df_chain->block_pool);
2127 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2132 /* Debugging info. */
2135 df_chain_top_dump (basic_block bb, FILE *file)
2137 if (df_chain_problem_p (DF_DU_CHAIN))
2140 df_ref *def_rec = df_get_artificial_defs (bb->index);
2144 fprintf (file, ";; DU chains for artificial defs\n");
2147 df_ref def = *def_rec;
2148 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2149 df_chain_dump (DF_REF_CHAIN (def), file);
2150 fprintf (file, "\n");
2155 FOR_BB_INSNS (bb, insn)
2159 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2160 def_rec = DF_INSN_INFO_DEFS (insn_info);
2163 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2164 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2168 df_ref def = *def_rec;
2169 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2170 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2171 fprintf (file, "read/write ");
2172 df_chain_dump (DF_REF_CHAIN (def), file);
2173 fprintf (file, "\n");
2184 df_chain_bottom_dump (basic_block bb, FILE *file)
2186 if (df_chain_problem_p (DF_UD_CHAIN))
2189 df_ref *use_rec = df_get_artificial_uses (bb->index);
2193 fprintf (file, ";; UD chains for artificial uses\n");
2196 df_ref use = *use_rec;
2197 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2198 df_chain_dump (DF_REF_CHAIN (use), file);
2199 fprintf (file, "\n");
2204 FOR_BB_INSNS (bb, insn)
2208 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2209 df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2210 use_rec = DF_INSN_INFO_USES (insn_info);
2211 if (*use_rec || *eq_use_rec)
2213 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2214 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2218 df_ref use = *use_rec;
2219 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2220 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2221 fprintf (file, "read/write ");
2222 df_chain_dump (DF_REF_CHAIN (use), file);
2223 fprintf (file, "\n");
2228 df_ref use = *eq_use_rec;
2229 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2230 df_chain_dump (DF_REF_CHAIN (use), file);
2231 fprintf (file, "\n");
2241 static struct df_problem problem_CHAIN =
2243 DF_CHAIN, /* Problem id. */
2244 DF_NONE, /* Direction. */
2245 df_chain_alloc, /* Allocate the problem specific data. */
2246 df_chain_reset, /* Reset global information. */
2247 NULL, /* Free basic block info. */
2248 NULL, /* Local compute function. */
2249 NULL, /* Init the solution specific data. */
2250 NULL, /* Iterative solver. */
2251 NULL, /* Confluence operator 0. */
2252 NULL, /* Confluence operator n. */
2253 NULL, /* Transfer function. */
2254 df_chain_finalize, /* Finalize function. */
2255 df_chain_free, /* Free all of the problem information. */
2256 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2257 NULL, /* Debugging. */
2258 df_chain_top_dump, /* Debugging start block. */
2259 df_chain_bottom_dump, /* Debugging end block. */
2260 NULL, /* Incremental solution verify start. */
2261 NULL, /* Incremental solution verify end. */
2262 &problem_RD, /* Dependent problem. */
2263 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2264 TV_DF_CHAIN, /* Timing variable. */
2265 false /* Reset blocks on dropping out of blocks_to_analyze. */
2269 /* Create a new DATAFLOW instance and add it to an existing instance
2270 of DF. The returned structure is what is used to get at the
2274 df_chain_add_problem (unsigned int chain_flags)
2276 df_add_problem (&problem_CHAIN);
2277 df_chain->local_flags = chain_flags;
2278 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2281 #undef df_chain_problem_p
2284 /*----------------------------------------------------------------------------
2285 BYTE LEVEL LIVE REGISTERS
2287 Find the locations in the function where any use of a pseudo can
2288 reach in the backwards direction. In and out bitvectors are built
2289 for each basic block. There are two mapping functions,
2290 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2291 used to map regnos into bit vector positions.
2293 This problem differs from the regular df_lr function in the way
2294 that subregs, *_extracts and strict_low_parts are handled. In lr
2295 these are consider partial kills, here, the exact set of bytes is
2296 modeled. Note that any reg that has none of these operations is
2297 only modeled with a single bit since all operations access the
2300 This problem is more brittle that the regular lr. It currently can
2301 be used in dce incrementally, but cannot be used in an environment
2302 where insns are created or modified. The problem is that the
2303 mapping of regnos to bitmap positions is relatively compact, in
2304 that if a pseudo does not do any of the byte wise operations, only
2305 one slot is allocated, rather than a slot for each byte. If insn
2306 are created, where a subreg is used for a reg that had no subregs,
2307 the mapping would be wrong. Likewise, there are no checks to see
2308 that new pseudos have been added. These issues could be addressed
2309 by adding a problem specific flag to not use the compact mapping,
2310 if there was a need to do so.
2312 ----------------------------------------------------------------------------*/
2314 /* Private data used to verify the solution for this problem. */
2315 struct df_byte_lr_problem_data
2317 /* Expanded versions of bitvectors used in lr. */
2318 bitmap_head invalidated_by_call;
2319 bitmap_head hardware_regs_used;
2321 /* Indexed by regno, this is true if there are subregs, extracts or
2322 strict_low_parts for this regno. */
2323 bitmap_head needs_expansion;
2325 /* The start position and len for each regno in the various bit
2327 unsigned int* regno_start;
2328 unsigned int* regno_len;
2329 /* An obstack for the bitmaps we need for this problem. */
2330 bitmap_obstack byte_lr_bitmaps;
2334 /* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2337 df_byte_lr_get_regno_start (unsigned int regno)
2339 struct df_byte_lr_problem_data *problem_data
2340 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2341 return problem_data->regno_start[regno];
2345 /* Get the len for REGNO in the df_byte_lr bitmaps. */
2348 df_byte_lr_get_regno_len (unsigned int regno)
2350 struct df_byte_lr_problem_data *problem_data
2351 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2352 return problem_data->regno_len[regno];
2356 /* Free basic block info. */
2359 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2362 struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2365 bitmap_clear (&bb_info->use);
2366 bitmap_clear (&bb_info->def);
2367 bitmap_clear (&bb_info->in);
2368 bitmap_clear (&bb_info->out);
2373 /* Check all of the refs in REF_REC to see if any of them are
2374 extracts, subregs or strict_low_parts. */
2377 df_byte_lr_check_regs (df_ref *ref_rec)
2379 struct df_byte_lr_problem_data *problem_data
2380 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2382 for (; *ref_rec; ref_rec++)
2384 df_ref ref = *ref_rec;
2385 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2386 | DF_REF_ZERO_EXTRACT
2387 | DF_REF_STRICT_LOW_PART)
2388 || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2389 bitmap_set_bit (&problem_data->needs_expansion, DF_REF_REGNO (ref));
2394 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2395 regno_start and regno_len. */
2398 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2400 struct df_byte_lr_problem_data *problem_data
2401 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2405 bitmap_clear (dest);
2406 EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2408 bitmap_set_range (dest, problem_data->regno_start[i],
2409 problem_data->regno_len[i]);
2414 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2415 not touched unless the block is new. */
2418 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2420 unsigned int bb_index;
2424 unsigned int index = 0;
2425 unsigned int max_reg = max_reg_num();
2426 struct df_byte_lr_problem_data *problem_data
2427 = XNEW (struct df_byte_lr_problem_data);
2429 df_byte_lr->problem_data = problem_data;
2431 df_grow_bb_info (df_byte_lr);
2433 /* Create the mapping from regnos to slots. This does not change
2434 unless the problem is destroyed and recreated. In particular, if
2435 we end up deleting the only insn that used a subreg, we do not
2436 want to redo the mapping because this would invalidate everything
2439 bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2440 problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2441 problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2442 bitmap_initialize (&problem_data->hardware_regs_used,
2443 &problem_data->byte_lr_bitmaps);
2444 bitmap_initialize (&problem_data->invalidated_by_call,
2445 &problem_data->byte_lr_bitmaps);
2446 bitmap_initialize (&problem_data->needs_expansion,
2447 &problem_data->byte_lr_bitmaps);
2449 /* Discover which regno's use subregs, extracts or
2450 strict_low_parts. */
2454 FOR_BB_INSNS (bb, insn)
2458 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2459 df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2460 df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
2463 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2466 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2467 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2469 /* Allocate the slots for each regno. */
2470 for (regno = 0; regno < max_reg; regno++)
2473 problem_data->regno_start[regno] = index;
2474 if (bitmap_bit_p (&problem_data->needs_expansion, regno))
2475 len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2479 problem_data->regno_len[regno] = len;
2483 df_byte_lr_expand_bitmap (&problem_data->hardware_regs_used,
2484 &df->hardware_regs_used);
2485 df_byte_lr_expand_bitmap (&problem_data->invalidated_by_call,
2486 regs_invalidated_by_call_regset);
2488 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2490 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2492 /* When bitmaps are already initialized, just clear them. */
2493 if (bb_info->use.obstack)
2495 bitmap_clear (&bb_info->def);
2496 bitmap_clear (&bb_info->use);
2500 bitmap_initialize (&bb_info->use, &problem_data->byte_lr_bitmaps);
2501 bitmap_initialize (&bb_info->def, &problem_data->byte_lr_bitmaps);
2502 bitmap_initialize (&bb_info->in, &problem_data->byte_lr_bitmaps);
2503 bitmap_initialize (&bb_info->out, &problem_data->byte_lr_bitmaps);
2507 df_byte_lr->optional_p = true;
2511 /* Reset the global solution for recalculation. */
2514 df_byte_lr_reset (bitmap all_blocks)
2516 unsigned int bb_index;
2519 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2521 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2522 gcc_assert (bb_info);
2523 bitmap_clear (&bb_info->in);
2524 bitmap_clear (&bb_info->out);
2529 /* Compute local live register info for basic block BB. */
2532 df_byte_lr_bb_local_compute (unsigned int bb_index)
2534 struct df_byte_lr_problem_data *problem_data
2535 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2536 basic_block bb = BASIC_BLOCK (bb_index);
2537 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2542 /* Process the registers set in an exception handler. */
2543 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2545 df_ref def = *def_rec;
2546 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2548 unsigned int dregno = DF_REF_REGNO (def);
2549 unsigned int start = problem_data->regno_start[dregno];
2550 unsigned int len = problem_data->regno_len[dregno];
2551 bitmap_set_range (&bb_info->def, start, len);
2552 bitmap_clear_range (&bb_info->use, start, len);
2556 /* Process the hardware registers that are always live. */
2557 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2559 df_ref use = *use_rec;
2560 /* Add use to set of uses in this BB. */
2561 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2563 unsigned int uregno = DF_REF_REGNO (use);
2564 unsigned int start = problem_data->regno_start[uregno];
2565 unsigned int len = problem_data->regno_len[uregno];
2566 bitmap_set_range (&bb_info->use, start, len);
2570 FOR_BB_INSNS_REVERSE (bb, insn)
2572 unsigned int uid = INSN_UID (insn);
2577 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2579 df_ref def = *def_rec;
2580 /* If the def is to only part of the reg, it does
2581 not kill the other defs that reach here. */
2582 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2584 unsigned int dregno = DF_REF_REGNO (def);
2585 unsigned int start = problem_data->regno_start[dregno];
2586 unsigned int len = problem_data->regno_len[dregno];
2589 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2596 bitmap_set_range (&bb_info->def, start, len);
2597 bitmap_clear_range (&bb_info->use, start, len);
2602 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2604 df_ref use = *use_rec;
2605 unsigned int uregno = DF_REF_REGNO (use);
2606 unsigned int start = problem_data->regno_start[uregno];
2607 unsigned int len = problem_data->regno_len[uregno];
2610 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2615 /* Add use to set of uses in this BB. */
2617 bitmap_set_range (&bb_info->use, start, len);
2621 /* Process the registers set in an exception handler or the hard
2622 frame pointer if this block is the target of a non local
2624 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2626 df_ref def = *def_rec;
2627 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2629 unsigned int dregno = DF_REF_REGNO (def);
2630 unsigned int start = problem_data->regno_start[dregno];
2631 unsigned int len = problem_data->regno_len[dregno];
2632 bitmap_set_range (&bb_info->def, start, len);
2633 bitmap_clear_range (&bb_info->use, start, len);
2638 /* Process the uses that are live into an exception handler. */
2639 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2641 df_ref use = *use_rec;
2642 /* Add use to set of uses in this BB. */
2643 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2645 unsigned int uregno = DF_REF_REGNO (use);
2646 unsigned int start = problem_data->regno_start[uregno];
2647 unsigned int len = problem_data->regno_len[uregno];
2648 bitmap_set_range (&bb_info->use, start, len);
2655 /* Compute local live register info for each basic block within BLOCKS. */
2658 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2660 unsigned int bb_index;
2663 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2665 if (bb_index == EXIT_BLOCK)
2667 /* The exit block is special for this problem and its bits are
2668 computed from thin air. */
2669 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2670 df_byte_lr_expand_bitmap (&bb_info->use, df->exit_block_uses);
2673 df_byte_lr_bb_local_compute (bb_index);
2676 bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2680 /* Initialize the solution vectors. */
2683 df_byte_lr_init (bitmap all_blocks)
2685 unsigned int bb_index;
2688 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2690 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2691 bitmap_copy (&bb_info->in, &bb_info->use);
2692 bitmap_clear (&bb_info->out);
2697 /* Confluence function that processes infinite loops. This might be a
2698 noreturn function that throws. And even if it isn't, getting the
2699 unwind info right helps debugging. */
2701 df_byte_lr_confluence_0 (basic_block bb)
2703 struct df_byte_lr_problem_data *problem_data
2704 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2705 bitmap op1 = &df_byte_lr_get_bb_info (bb->index)->out;
2706 if (bb != EXIT_BLOCK_PTR)
2707 bitmap_copy (op1, &problem_data->hardware_regs_used);
2711 /* Confluence function that ignores fake edges. */
2714 df_byte_lr_confluence_n (edge e)
2716 struct df_byte_lr_problem_data *problem_data
2717 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2718 bitmap op1 = &df_byte_lr_get_bb_info (e->src->index)->out;
2719 bitmap op2 = &df_byte_lr_get_bb_info (e->dest->index)->in;
2721 /* Call-clobbered registers die across exception and call edges. */
2722 /* ??? Abnormal call edges ignored for the moment, as this gets
2723 confused by sibling call edges, which crashes reg-stack. */
2724 if (e->flags & EDGE_EH)
2725 bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);
2727 bitmap_ior_into (op1, op2);
2729 bitmap_ior_into (op1, &problem_data->hardware_regs_used);
2733 /* Transfer function. */
2736 df_byte_lr_transfer_function (int bb_index)
2738 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2739 bitmap in = &bb_info->in;
2740 bitmap out = &bb_info->out;
2741 bitmap use = &bb_info->use;
2742 bitmap def = &bb_info->def;
2744 return bitmap_ior_and_compl (in, use, out, def);
2748 /* Free all storage associated with the problem. */
2751 df_byte_lr_free (void)
2753 struct df_byte_lr_problem_data *problem_data
2754 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2757 if (df_byte_lr->block_info)
2759 df_byte_lr->block_info_size = 0;
2760 free (df_byte_lr->block_info);
2761 df_byte_lr->block_info = NULL;
2764 BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2765 bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2766 free (problem_data->regno_start);
2767 free (problem_data->regno_len);
2768 free (problem_data);
2773 /* Debugging info at top of bb. */
2776 df_byte_lr_top_dump (basic_block bb, FILE *file)
2778 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2782 fprintf (file, ";; blr in \t");
2783 df_print_byte_regset (file, &bb_info->in);
2784 fprintf (file, ";; blr use \t");
2785 df_print_byte_regset (file, &bb_info->use);
2786 fprintf (file, ";; blr def \t");
2787 df_print_byte_regset (file, &bb_info->def);
2791 /* Debugging info at bottom of bb. */
2794 df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2796 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2800 fprintf (file, ";; blr out \t");
2801 df_print_byte_regset (file, &bb_info->out);
2805 /* All of the information associated with every instance of the problem. */
2807 static struct df_problem problem_BYTE_LR =
2809 DF_BYTE_LR, /* Problem id. */
2810 DF_BACKWARD, /* Direction. */
2811 df_byte_lr_alloc, /* Allocate the problem specific data. */
2812 df_byte_lr_reset, /* Reset global information. */
2813 df_byte_lr_free_bb_info, /* Free basic block info. */
2814 df_byte_lr_local_compute, /* Local compute function. */
2815 df_byte_lr_init, /* Init the solution specific data. */
2816 df_worklist_dataflow, /* Worklist solver. */
2817 df_byte_lr_confluence_0, /* Confluence operator 0. */
2818 df_byte_lr_confluence_n, /* Confluence operator n. */
2819 df_byte_lr_transfer_function, /* Transfer function. */
2820 NULL, /* Finalize function. */
2821 df_byte_lr_free, /* Free all of the problem information. */
2822 df_byte_lr_free, /* Remove this problem from the stack of dataflow problems. */
2823 NULL, /* Debugging. */
2824 df_byte_lr_top_dump, /* Debugging start block. */
2825 df_byte_lr_bottom_dump, /* Debugging end block. */
2826 NULL, /* Incremental solution verify start. */
2827 NULL, /* Incremental solution verify end. */
2828 NULL, /* Dependent problem. */
2829 sizeof (struct df_byte_lr_bb_info),/* Size of entry of block_info array. */
2830 TV_DF_BYTE_LR, /* Timing variable. */
2831 false /* Reset blocks on dropping out of blocks_to_analyze. */
2835 /* Create a new DATAFLOW instance and add it to an existing instance
2836 of DF. The returned structure is what is used to get at the
2840 df_byte_lr_add_problem (void)
2842 df_add_problem (&problem_BYTE_LR);
2843 /* These will be initialized when df_scan_blocks processes each
2845 df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2849 /* Simulate the effects of the defs of INSN on LIVE. */
2852 df_byte_lr_simulate_defs (rtx insn, bitmap live)
2854 struct df_byte_lr_problem_data *problem_data
2855 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2857 unsigned int uid = INSN_UID (insn);
2859 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2861 df_ref def = *def_rec;
2863 /* If the def is to only part of the reg, it does
2864 not kill the other defs that reach here. */
2865 if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2867 unsigned int dregno = DF_REF_REGNO (def);
2868 unsigned int start = problem_data->regno_start[dregno];
2869 unsigned int len = problem_data->regno_len[dregno];
2872 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2879 bitmap_clear_range (live, start, len);
2885 /* Simulate the effects of the uses of INSN on LIVE. */
2888 df_byte_lr_simulate_uses (rtx insn, bitmap live)
2890 struct df_byte_lr_problem_data *problem_data
2891 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2893 unsigned int uid = INSN_UID (insn);
2895 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2897 df_ref use = *use_rec;
2898 unsigned int uregno = DF_REF_REGNO (use);
2899 unsigned int start = problem_data->regno_start[uregno];
2900 unsigned int len = problem_data->regno_len[uregno];
2904 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2910 /* Add use to set of uses in this BB. */
2912 bitmap_set_range (live, start, len);
2917 /* Apply the artificial uses and defs at the top of BB in a forwards
2921 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2923 struct df_byte_lr_problem_data *problem_data
2924 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2929 int bb_index = bb->index;
2932 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2934 df_ref use = *use_rec;
2935 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2937 unsigned int uregno = DF_REF_REGNO (use);
2938 unsigned int start = problem_data->regno_start[uregno];
2939 unsigned int len = problem_data->regno_len[uregno];
2940 bitmap_set_range (live, start, len);
2945 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2947 df_ref def = *def_rec;
2948 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2950 unsigned int dregno = DF_REF_REGNO (def);
2951 unsigned int start = problem_data->regno_start[dregno];
2952 unsigned int len = problem_data->regno_len[dregno];
2953 bitmap_clear_range (live, start, len);
2959 /* Apply the artificial uses and defs at the end of BB in a backwards
2963 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
2965 struct df_byte_lr_problem_data *problem_data
2966 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2969 int bb_index = bb->index;
2971 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2973 df_ref def = *def_rec;
2974 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2976 unsigned int dregno = DF_REF_REGNO (def);
2977 unsigned int start = problem_data->regno_start[dregno];
2978 unsigned int len = problem_data->regno_len[dregno];
2979 bitmap_clear_range (live, start, len);
2983 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2985 df_ref use = *use_rec;
2986 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2988 unsigned int uregno = DF_REF_REGNO (use);
2989 unsigned int start = problem_data->regno_start[uregno];
2990 unsigned int len = problem_data->regno_len[uregno];
2991 bitmap_set_range (live, start, len);
2998 /*----------------------------------------------------------------------------
2999 This problem computes REG_DEAD and REG_UNUSED notes.
3000 ----------------------------------------------------------------------------*/
3003 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3005 df_note->optional_p = true;
3008 #ifdef REG_DEAD_DEBUGGING
3010 df_print_note (const char *prefix, rtx insn, rtx note)
3014 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3015 print_rtl (dump_file, note);
3016 fprintf (dump_file, "\n");
3022 /* After reg-stack, the x86 floating point stack regs are difficult to
3023 analyze because of all of the pushes, pops and rotations. Thus, we
3024 just leave the notes alone. */
3028 df_ignore_stack_reg (int regno)
3030 return regstack_completed
3031 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3035 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3042 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3043 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3046 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3048 rtx *pprev = ®_NOTES (insn);
3055 switch (REG_NOTE_KIND (link))
3058 /* After reg-stack, we need to ignore any unused notes
3059 for the stack registers. */
3060 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3062 pprev = &XEXP (link, 1);
3067 rtx next = XEXP (link, 1);
3068 #ifdef REG_DEAD_DEBUGGING
3069 df_print_note ("deleting: ", insn, link);
3071 XEXP (link, 1) = dead;
3073 *pprev = link = next;
3078 /* After reg-stack, we need to ignore any unused notes
3079 for the stack registers. */
3080 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3082 pprev = &XEXP (link, 1);
3087 rtx next = XEXP (link, 1);
3088 #ifdef REG_DEAD_DEBUGGING
3089 df_print_note ("deleting: ", insn, link);
3091 XEXP (link, 1) = unused;
3093 *pprev = link = next;
3098 pprev = &XEXP (link, 1);
3104 *old_dead_notes = dead;
3105 *old_unused_notes = unused;
3109 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3110 list, otherwise create a new one. */
3113 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3118 gcc_assert (!DEBUG_INSN_P (insn));
3121 if (XEXP (curr, 0) == reg)
3124 XEXP (prev, 1) = XEXP (curr, 1);
3126 old = XEXP (curr, 1);
3127 XEXP (curr, 1) = REG_NOTES (insn);
3128 REG_NOTES (insn) = curr;
3134 curr = XEXP (curr, 1);
3137 /* Did not find the note. */
3138 add_reg_note (insn, note_type, reg);
3142 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3143 arguments. Return true if the register value described by MWS's
3144 mw_reg is known to be completely unused, and if mw_reg can therefore
3145 be used in a REG_UNUSED note. */
3148 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3149 bitmap live, bitmap artificial_uses)
3153 /* If MWS describes a partial reference, create REG_UNUSED notes for
3154 individual hard registers. */
3155 if (mws->flags & DF_REF_PARTIAL)
3158 /* Likewise if some part of the register is used. */
3159 for (r = mws->start_regno; r <= mws->end_regno; r++)
3160 if (bitmap_bit_p (live, r)
3161 || bitmap_bit_p (artificial_uses, r))
3164 gcc_assert (REG_P (mws->mw_reg));
3168 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3169 based on the bits in LIVE. Do not generate notes for registers in
3170 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3171 not generated if the reg is both read and written by the
3176 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3177 bitmap live, bitmap do_not_gen,
3178 bitmap artificial_uses)
3182 #ifdef REG_DEAD_DEBUGGING
3184 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3185 mws->start_regno, mws->end_regno);
3188 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3190 unsigned int regno = mws->start_regno;
3191 old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3193 #ifdef REG_DEAD_DEBUGGING
3194 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3196 bitmap_set_bit (do_not_gen, regno);
3197 /* Only do this if the value is totally dead. */
3200 for (r = mws->start_regno; r <= mws->end_regno; r++)
3202 if (!bitmap_bit_p (live, r)
3203 && !bitmap_bit_p (artificial_uses, r))
3205 old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3206 #ifdef REG_DEAD_DEBUGGING
3207 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3210 bitmap_set_bit (do_not_gen, r);
3216 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3217 arguments. Return true if the register value described by MWS's
3218 mw_reg is known to be completely dead, and if mw_reg can therefore
3219 be used in a REG_DEAD note. */
3222 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3223 bitmap live, bitmap artificial_uses,
3228 /* If MWS describes a partial reference, create REG_DEAD notes for
3229 individual hard registers. */
3230 if (mws->flags & DF_REF_PARTIAL)
3233 /* Likewise if some part of the register is not dead. */
3234 for (r = mws->start_regno; r <= mws->end_regno; r++)
3235 if (bitmap_bit_p (live, r)
3236 || bitmap_bit_p (artificial_uses, r)
3237 || bitmap_bit_p (do_not_gen, r))
3240 gcc_assert (REG_P (mws->mw_reg));
3244 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3245 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3246 from being set if the instruction both reads and writes the
3250 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3251 bitmap live, bitmap do_not_gen,
3252 bitmap artificial_uses, bool *added_notes_p)
3255 bool is_debug = *added_notes_p;
3257 *added_notes_p = false;
3259 #ifdef REG_DEAD_DEBUGGING
3262 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3263 mws->start_regno, mws->end_regno);
3264 df_print_regset (dump_file, do_not_gen);
3265 fprintf (dump_file, " live =");
3266 df_print_regset (dump_file, live);
3267 fprintf (dump_file, " artificial uses =");
3268 df_print_regset (dump_file, artificial_uses);
3272 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3274 /* Add a dead note for the entire multi word register. */
3277 *added_notes_p = true;
3280 old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3281 #ifdef REG_DEAD_DEBUGGING
3282 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3287 for (r = mws->start_regno; r <= mws->end_regno; r++)
3288 if (!bitmap_bit_p (live, r)
3289 && !bitmap_bit_p (artificial_uses, r)
3290 && !bitmap_bit_p (do_not_gen, r))
3294 *added_notes_p = true;
3297 old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3298 #ifdef REG_DEAD_DEBUGGING
3299 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3307 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3308 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3311 df_create_unused_note (rtx insn, rtx old, df_ref def,
3312 bitmap live, bitmap artificial_uses)
3314 unsigned int dregno = DF_REF_REGNO (def);
3316 #ifdef REG_DEAD_DEBUGGING
3319 fprintf (dump_file, " regular looking at def ");
3320 df_ref_debug (def, dump_file);
3324 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3325 || bitmap_bit_p (live, dregno)
3326 || bitmap_bit_p (artificial_uses, dregno)
3327 || df_ignore_stack_reg (dregno)))
3329 rtx reg = (DF_REF_LOC (def))
3330 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3331 old = df_set_note (REG_UNUSED, insn, old, reg);
3332 #ifdef REG_DEAD_DEBUGGING
3333 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3340 /* Node of a linked list of uses of dead REGs in debug insns. */
3341 struct dead_debug_use
3344 struct dead_debug_use *next;
3347 /* Linked list of the above, with a bitmap of the REGs in the
3351 struct dead_debug_use *head;
3356 /* Initialize DEBUG to an empty list, and clear USED, if given. */
3358 dead_debug_init (struct dead_debug *debug, bitmap used)
3362 debug->to_rescan = NULL;
3364 bitmap_clear (used);
3367 /* Reset all debug insns with pending uses. Release the bitmap in it,
3368 unless it is USED. USED must be the same bitmap passed to
3371 dead_debug_finish (struct dead_debug *debug, bitmap used)
3373 struct dead_debug_use *head;
3376 if (debug->used != used)
3377 BITMAP_FREE (debug->used);
3379 while ((head = debug->head))
3381 insn = DF_REF_INSN (head->use);
3382 if (!head->next || DF_REF_INSN (head->next->use) != insn)
3384 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3385 df_insn_rescan_debug_internal (insn);
3386 if (debug->to_rescan)
3387 bitmap_clear_bit (debug->to_rescan, INSN_UID (insn));
3389 debug->head = head->next;
3393 if (debug->to_rescan)
3398 EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi)
3400 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
3402 df_insn_rescan (insn_info->insn);
3404 BITMAP_FREE (debug->to_rescan);
3408 /* Add USE to DEBUG. It must be a dead reference to UREGNO in a debug
3409 insn. Create a bitmap for DEBUG as needed. */
3411 dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno)
3413 struct dead_debug_use *newddu = XNEW (struct dead_debug_use);
3416 newddu->next = debug->head;
3417 debug->head = newddu;
3420 debug->used = BITMAP_ALLOC (NULL);
3422 bitmap_set_bit (debug->used, uregno);
3425 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3426 before INSN that binds the REG to a debug temp, and replace all
3427 uses of UREGNO in DEBUG with uses of the debug temp. INSN must be
3428 the insn where UREGNO dies. */
3430 dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno,
3433 struct dead_debug_use **tailp = &debug->head;
3434 struct dead_debug_use *cur;
3435 struct dead_debug_use *uses = NULL;
3436 struct dead_debug_use **usesp = &uses;
3441 if (!debug->used || !bitmap_clear_bit (debug->used, uregno))
3444 /* Move all uses of uregno from debug->head to uses, setting mode to
3445 the widest referenced mode. */
3446 while ((cur = *tailp))
3448 if (DF_REF_REGNO (cur->use) == uregno)
3455 || (GET_MODE_BITSIZE (GET_MODE (reg))
3456 < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use)))))
3457 reg = *DF_REF_REAL_LOC (cur->use);
3460 tailp = &(*tailp)->next;
3465 /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL). */
3466 dval = make_debug_expr_from_rtl (reg);
3468 /* Emit a debug bind insn before the insn in which reg dies. */
3469 bind = gen_rtx_VAR_LOCATION (GET_MODE (reg),
3470 DEBUG_EXPR_TREE_DECL (dval), reg,
3471 VAR_INIT_STATUS_INITIALIZED);
3473 bind = emit_debug_insn_before (bind, insn);
3474 df_insn_rescan (bind);
3476 /* Adjust all uses. */
3477 while ((cur = uses))
3479 if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg))
3480 *DF_REF_REAL_LOC (cur->use) = dval;
3482 *DF_REF_REAL_LOC (cur->use)
3483 = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval);
3484 /* ??? Should we simplify subreg of subreg? */
3485 if (debug->to_rescan == NULL)
3486 debug->to_rescan = BITMAP_ALLOC (NULL);
3487 bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use)));
3493 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3494 info: lifetime, bb, and number of defs and uses for basic block
3495 BB. The three bitvectors are scratch regs used here. */
3498 df_note_bb_compute (unsigned int bb_index,
3499 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3501 basic_block bb = BASIC_BLOCK (bb_index);
3505 struct dead_debug debug;
3507 dead_debug_init (&debug, NULL);
3509 bitmap_copy (live, df_get_live_out (bb));
3510 bitmap_clear (artificial_uses);
3512 #ifdef REG_DEAD_DEBUGGING
3515 fprintf (dump_file, "live at bottom ");
3516 df_print_regset (dump_file, live);
3520 /* Process the artificial defs and uses at the bottom of the block
3521 to begin processing. */
3522 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3524 df_ref def = *def_rec;
3525 #ifdef REG_DEAD_DEBUGGING
3527 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3530 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3531 bitmap_clear_bit (live, DF_REF_REGNO (def));
3534 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3536 df_ref use = *use_rec;
3537 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3539 unsigned int regno = DF_REF_REGNO (use);
3540 bitmap_set_bit (live, regno);
3542 /* Notes are not generated for any of the artificial registers
3543 at the bottom of the block. */
3544 bitmap_set_bit (artificial_uses, regno);
3548 #ifdef REG_DEAD_DEBUGGING
3551 fprintf (dump_file, "live before artificials out ");
3552 df_print_regset (dump_file, live);
3556 FOR_BB_INSNS_REVERSE (bb, insn)
3558 unsigned int uid = INSN_UID (insn);
3559 struct df_mw_hardreg **mws_rec;
3561 rtx old_unused_notes;
3567 debug_insn = DEBUG_INSN_P (insn);
3569 bitmap_clear (do_not_gen);
3570 df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3572 /* Process the defs. */
3575 #ifdef REG_DEAD_DEBUGGING
3578 fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
3579 df_print_regset (dump_file, live);
3582 /* We only care about real sets for calls. Clobbers cannot
3583 be depended on to really die. */
3584 mws_rec = DF_INSN_UID_MWS (uid);
3587 struct df_mw_hardreg *mws = *mws_rec;
3588 if ((DF_MWS_REG_DEF_P (mws))
3589 && !df_ignore_stack_reg (mws->start_regno))
3591 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3592 mws, live, do_not_gen,
3597 /* All of the defs except the return value are some sort of
3598 clobber. This code is for the return. */
3599 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3601 df_ref def = *def_rec;
3602 unsigned int dregno = DF_REF_REGNO (def);
3603 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3606 = df_create_unused_note (insn, old_unused_notes,
3607 def, live, artificial_uses);
3608 bitmap_set_bit (do_not_gen, dregno);
3611 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3612 bitmap_clear_bit (live, dregno);
3618 mws_rec = DF_INSN_UID_MWS (uid);
3621 struct df_mw_hardreg *mws = *mws_rec;
3622 if (DF_MWS_REG_DEF_P (mws))
3624 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3625 mws, live, do_not_gen,
3630 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3632 df_ref def = *def_rec;
3633 unsigned int dregno = DF_REF_REGNO (def);
3635 = df_create_unused_note (insn, old_unused_notes,
3636 def, live, artificial_uses);
3638 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3639 bitmap_set_bit (do_not_gen, dregno);
3641 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3642 bitmap_clear_bit (live, dregno);
3646 /* Process the uses. */
3647 mws_rec = DF_INSN_UID_MWS (uid);
3650 struct df_mw_hardreg *mws = *mws_rec;
3651 if ((DF_MWS_REG_DEF_P (mws))
3652 && !df_ignore_stack_reg (mws->start_regno))
3654 bool really_add_notes = debug_insn != 0;
3657 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3658 mws, live, do_not_gen,
3662 if (really_add_notes)
3668 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3670 df_ref use = *use_rec;
3671 unsigned int uregno = DF_REF_REGNO (use);
3673 #ifdef REG_DEAD_DEBUGGING
3674 if (dump_file && !debug_insn)
3676 fprintf (dump_file, " regular looking at use ");
3677 df_ref_debug (use, dump_file);
3680 if (!bitmap_bit_p (live, uregno))
3686 dead_debug_add (&debug, use, uregno);
3692 dead_debug_insert_before (&debug, uregno, insn);
3694 if ( (!(DF_REF_FLAGS (use)
3695 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3696 && (!bitmap_bit_p (do_not_gen, uregno))
3697 && (!bitmap_bit_p (artificial_uses, uregno))
3698 && (!df_ignore_stack_reg (uregno)))
3700 rtx reg = (DF_REF_LOC (use))
3701 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3702 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3704 #ifdef REG_DEAD_DEBUGGING
3705 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3708 /* This register is now live. */
3709 bitmap_set_bit (live, uregno);
3713 while (old_unused_notes)
3715 rtx next = XEXP (old_unused_notes, 1);
3716 free_EXPR_LIST_node (old_unused_notes);
3717 old_unused_notes = next;
3719 while (old_dead_notes)
3721 rtx next = XEXP (old_dead_notes, 1);
3722 free_EXPR_LIST_node (old_dead_notes);
3723 old_dead_notes = next;
3726 if (debug_insn == -1)
3728 /* ??? We could probably do better here, replacing dead
3729 registers with their definitions. */
3730 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3731 df_insn_rescan_debug_internal (insn);
3735 dead_debug_finish (&debug, NULL);
3739 /* Compute register info: lifetime, bb, and number of defs and uses. */
3741 df_note_compute (bitmap all_blocks)
3743 unsigned int bb_index;
3745 bitmap_head live, do_not_gen, artificial_uses;
3747 bitmap_initialize (&live, &df_bitmap_obstack);
3748 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3749 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3751 #ifdef REG_DEAD_DEBUGGING
3753 print_rtl_with_bb (dump_file, get_insns());
3756 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3758 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3761 bitmap_clear (&live);
3762 bitmap_clear (&do_not_gen);
3763 bitmap_clear (&artificial_uses);
3767 /* Free all storage associated with the problem. */
3776 /* All of the information associated every instance of the problem. */
3778 static struct df_problem problem_NOTE =
3780 DF_NOTE, /* Problem id. */
3781 DF_NONE, /* Direction. */
3782 df_note_alloc, /* Allocate the problem specific data. */
3783 NULL, /* Reset global information. */
3784 NULL, /* Free basic block info. */
3785 df_note_compute, /* Local compute function. */
3786 NULL, /* Init the solution specific data. */
3787 NULL, /* Iterative solver. */
3788 NULL, /* Confluence operator 0. */
3789 NULL, /* Confluence operator n. */
3790 NULL, /* Transfer function. */
3791 NULL, /* Finalize function. */
3792 df_note_free, /* Free all of the problem information. */
3793 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3794 NULL, /* Debugging. */
3795 NULL, /* Debugging start block. */
3796 NULL, /* Debugging end block. */
3797 NULL, /* Incremental solution verify start. */
3798 NULL, /* Incremental solution verify end. */
3799 &problem_LR, /* Dependent problem. */
3800 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3801 TV_DF_NOTE, /* Timing variable. */
3802 false /* Reset blocks on dropping out of blocks_to_analyze. */
3806 /* Create a new DATAFLOW instance and add it to an existing instance
3807 of DF. The returned structure is what is used to get at the
3811 df_note_add_problem (void)
3813 df_add_problem (&problem_NOTE);
3819 /*----------------------------------------------------------------------------
3820 Functions for simulating the effects of single insns.
3822 You can either simulate in the forwards direction, starting from
3823 the top of a block or the backwards direction from the end of the
3824 block. If you go backwards, defs are examined first to clear bits,
3825 then uses are examined to set bits. If you go forwards, defs are
3826 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3827 are examined to clear bits. In either case, the result of examining
3828 a def can be undone (respectively by a use or a REG_UNUSED note).
3830 If you start at the top of the block, use one of DF_LIVE_IN or
3831 DF_LR_IN. If you start at the bottom of the block use one of
3832 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3833 THEY WILL BE DESTROYED.
3834 ----------------------------------------------------------------------------*/
3837 /* Find the set of DEFs for INSN. */
3840 df_simulate_find_defs (rtx insn, bitmap defs)
3843 unsigned int uid = INSN_UID (insn);
3845 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3847 df_ref def = *def_rec;
3848 bitmap_set_bit (defs, DF_REF_REGNO (def));
3852 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3855 df_simulate_find_noclobber_defs (rtx insn, bitmap defs)
3858 unsigned int uid = INSN_UID (insn);
3860 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3862 df_ref def = *def_rec;
3863 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3864 bitmap_set_bit (defs, DF_REF_REGNO (def));
3869 /* Simulate the effects of the defs of INSN on LIVE. */
3872 df_simulate_defs (rtx insn, bitmap live)
3875 unsigned int uid = INSN_UID (insn);
3877 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3879 df_ref def = *def_rec;
3880 unsigned int dregno = DF_REF_REGNO (def);
3882 /* If the def is to only part of the reg, it does
3883 not kill the other defs that reach here. */
3884 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3885 bitmap_clear_bit (live, dregno);
3890 /* Simulate the effects of the uses of INSN on LIVE. */
3893 df_simulate_uses (rtx insn, bitmap live)
3896 unsigned int uid = INSN_UID (insn);
3898 if (DEBUG_INSN_P (insn))
3901 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3903 df_ref use = *use_rec;
3904 /* Add use to set of uses in this BB. */
3905 bitmap_set_bit (live, DF_REF_REGNO (use));
3910 /* Add back the always live regs in BB to LIVE. */
3913 df_simulate_fixup_sets (basic_block bb, bitmap live)
3915 /* These regs are considered always live so if they end up dying
3916 because of some def, we need to bring the back again. */
3917 if (bb_has_eh_pred (bb))
3918 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3920 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3924 /*----------------------------------------------------------------------------
3925 The following three functions are used only for BACKWARDS scanning:
3926 i.e. they process the defs before the uses.
3928 df_simulate_initialize_backwards should be called first with a
3929 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3930 df_simulate_one_insn_backwards should be called for each insn in
3931 the block, starting with the last one. Finally,
3932 df_simulate_finalize_backwards can be called to get a new value
3933 of the sets at the top of the block (this is rarely used).
3934 ----------------------------------------------------------------------------*/
3936 /* Apply the artificial uses and defs at the end of BB in a backwards
3940 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3944 int bb_index = bb->index;
3946 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3948 df_ref def = *def_rec;
3949 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3950 bitmap_clear_bit (live, DF_REF_REGNO (def));
3953 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3955 df_ref use = *use_rec;
3956 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3957 bitmap_set_bit (live, DF_REF_REGNO (use));
3962 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3965 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3967 if (!NONDEBUG_INSN_P (insn))
3970 df_simulate_defs (insn, live);
3971 df_simulate_uses (insn, live);
3972 df_simulate_fixup_sets (bb, live);
3976 /* Apply the artificial uses and defs at the top of BB in a backwards
3980 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3986 int bb_index = bb->index;
3988 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3990 df_ref def = *def_rec;
3991 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3992 bitmap_clear_bit (live, DF_REF_REGNO (def));
3996 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3998 df_ref use = *use_rec;
3999 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4000 bitmap_set_bit (live, DF_REF_REGNO (use));
4004 /*----------------------------------------------------------------------------
4005 The following three functions are used only for FORWARDS scanning:
4006 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
4007 Thus it is important to add the DF_NOTES problem to the stack of
4008 problems computed before using these functions.
4010 df_simulate_initialize_forwards should be called first with a
4011 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
4012 df_simulate_one_insn_forwards should be called for each insn in
4013 the block, starting with the first one.
4014 ----------------------------------------------------------------------------*/
4016 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
4017 DF_LR_IN for basic block BB, for forward scanning by marking artificial
4021 df_simulate_initialize_forwards (basic_block bb, bitmap live)
4024 int bb_index = bb->index;
4026 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4028 df_ref def = *def_rec;
4029 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4030 bitmap_set_bit (live, DF_REF_REGNO (def));
4034 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4037 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
4040 if (! INSN_P (insn))
4043 /* Make sure that DF_NOTE really is an active df problem. */
4044 gcc_assert (df_note);
4046 /* Note that this is the opposite as how the problem is defined, because
4047 in the LR problem defs _kill_ liveness. However, they do so backwards,
4048 while here the scan is performed forwards! So, first assume that the
4049 def is live, and if this is not true REG_UNUSED notes will rectify the
4051 df_simulate_find_noclobber_defs (insn, live);
4053 /* Clear all of the registers that go dead. */
4054 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4056 switch (REG_NOTE_KIND (link))
4061 rtx reg = XEXP (link, 0);
4062 int regno = REGNO (reg);
4063 if (regno < FIRST_PSEUDO_REGISTER)
4065 int n = hard_regno_nregs[regno][GET_MODE (reg)];
4067 bitmap_clear_bit (live, regno + n);
4070 bitmap_clear_bit (live, regno);
4077 df_simulate_fixup_sets (bb, live);
4082 /*----------------------------------------------------------------------------
4083 MULTIPLE DEFINITIONS
4085 Find the locations in the function reached by multiple definition sites
4086 for a live pseudo. In and out bitvectors are built for each basic
4087 block. They are restricted for efficiency to live registers.
4089 The gen and kill sets for the problem are obvious. Together they
4090 include all defined registers in a basic block; the gen set includes
4091 registers where a partial or conditional or may-clobber definition is
4092 last in the BB, while the kill set includes registers with a complete
4093 definition coming last. However, the computation of the dataflow
4094 itself is interesting.
4096 The idea behind it comes from SSA form's iterated dominance frontier
4097 criterion for inserting PHI functions. Just like in that case, we can use
4098 the dominance frontier to find places where multiple definitions meet;
4099 a register X defined in a basic block BB1 has multiple definitions in
4100 basic blocks in BB1's dominance frontier.
4102 So, the in-set of a basic block BB2 is not just the union of the
4103 out-sets of BB2's predecessors, but includes some more bits that come
4104 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4105 the previous paragraph). I called this set the init-set of BB2.
4107 (Note: I actually use the kill-set only to build the init-set.
4108 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4110 For example, if you have
4114 if <...> goto BB2 else goto BB3;
4122 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4123 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4124 not need to iterate the dominance frontier, because we do not insert
4125 anything like PHI functions there! Instead, dataflow will take care of
4126 propagating the information to BB3's successors.
4127 ---------------------------------------------------------------------------*/
4129 /* Private data used to verify the solution for this problem. */
4130 struct df_md_problem_data
4132 /* An obstack for the bitmaps we need for this problem. */
4133 bitmap_obstack md_bitmaps;
4136 /* Scratch var used by transfer functions. This is used to do md analysis
4137 only for live registers. */
4138 static bitmap_head df_md_scratch;
4142 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4145 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4148 bitmap_clear (&bb_info->kill);
4149 bitmap_clear (&bb_info->gen);
4150 bitmap_clear (&bb_info->init);
4151 bitmap_clear (&bb_info->in);
4152 bitmap_clear (&bb_info->out);
4157 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4158 not touched unless the block is new. */
4161 df_md_alloc (bitmap all_blocks)
4163 unsigned int bb_index;
4165 struct df_md_problem_data *problem_data;
4167 df_grow_bb_info (df_md);
4168 if (df_md->problem_data)
4169 problem_data = (struct df_md_problem_data *) df_md->problem_data;
4172 problem_data = XNEW (struct df_md_problem_data);
4173 df_md->problem_data = problem_data;
4174 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4176 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4178 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4180 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4181 /* When bitmaps are already initialized, just clear them. */
4182 if (bb_info->init.obstack)
4184 bitmap_clear (&bb_info->init);
4185 bitmap_clear (&bb_info->gen);
4186 bitmap_clear (&bb_info->kill);
4187 bitmap_clear (&bb_info->in);
4188 bitmap_clear (&bb_info->out);
4192 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4193 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4194 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4195 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4196 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4200 df_md->optional_p = true;
4203 /* Add the effect of the top artificial defs of BB to the multiple definitions
4207 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4209 int bb_index = bb->index;
4211 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4213 df_ref def = *def_rec;
4214 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4216 unsigned int dregno = DF_REF_REGNO (def);
4217 if (DF_REF_FLAGS (def)
4218 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4219 bitmap_set_bit (local_md, dregno);
4221 bitmap_clear_bit (local_md, dregno);
4227 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4231 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
4234 unsigned uid = INSN_UID (insn);
4237 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4239 df_ref def = *def_rec;
4240 unsigned int dregno = DF_REF_REGNO (def);
4241 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4242 || (dregno >= FIRST_PSEUDO_REGISTER))
4244 if (DF_REF_FLAGS (def)
4245 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4246 bitmap_set_bit (local_md, DF_REF_ID (def));
4248 bitmap_clear_bit (local_md, DF_REF_ID (def));
4254 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4259 bitmap_clear (&seen_in_insn);
4261 while ((def = *def_rec++) != NULL)
4263 unsigned int dregno = DF_REF_REGNO (def);
4264 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4265 || (dregno >= FIRST_PSEUDO_REGISTER))
4266 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4268 if (!bitmap_bit_p (&seen_in_insn, dregno))
4270 if (DF_REF_FLAGS (def)
4271 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4273 bitmap_set_bit (&bb_info->gen, dregno);
4274 bitmap_clear_bit (&bb_info->kill, dregno);
4278 /* When we find a clobber and a regular def,
4279 make sure the regular def wins. */
4280 bitmap_set_bit (&seen_in_insn, dregno);
4281 bitmap_set_bit (&bb_info->kill, dregno);
4282 bitmap_clear_bit (&bb_info->gen, dregno);
4290 /* Compute local multiple def info for basic block BB. */
4293 df_md_bb_local_compute (unsigned int bb_index)
4295 basic_block bb = BASIC_BLOCK (bb_index);
4296 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4299 /* Artificials are only hard regs. */
4300 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4301 df_md_bb_local_compute_process_def (bb_info,
4302 df_get_artificial_defs (bb_index),
4305 FOR_BB_INSNS (bb, insn)
4307 unsigned int uid = INSN_UID (insn);
4311 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4314 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4315 df_md_bb_local_compute_process_def (bb_info,
4316 df_get_artificial_defs (bb_index),
4320 /* Compute local reaching def info for each basic block within BLOCKS. */
4323 df_md_local_compute (bitmap all_blocks)
4325 unsigned int bb_index, df_bb_index;
4326 bitmap_iterator bi1, bi2;
4328 bitmap_head *frontiers;
4330 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4332 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4334 df_md_bb_local_compute (bb_index);
4337 bitmap_clear (&seen_in_insn);
4339 frontiers = XNEWVEC (bitmap_head, last_basic_block);
4341 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4343 compute_dominance_frontiers (frontiers);
4345 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4346 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4348 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4349 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4351 basic_block bb = BASIC_BLOCK (df_bb_index);
4352 if (bitmap_bit_p (all_blocks, df_bb_index))
4353 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4354 df_get_live_in (bb));
4359 bitmap_clear (&frontiers[bb->index]);
4364 /* Reset the global solution for recalculation. */
4367 df_md_reset (bitmap all_blocks)
4369 unsigned int bb_index;
4372 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4374 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4375 gcc_assert (bb_info);
4376 bitmap_clear (&bb_info->in);
4377 bitmap_clear (&bb_info->out);
4382 df_md_transfer_function (int bb_index)
4384 basic_block bb = BASIC_BLOCK (bb_index);
4385 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4386 bitmap in = &bb_info->in;
4387 bitmap out = &bb_info->out;
4388 bitmap gen = &bb_info->gen;
4389 bitmap kill = &bb_info->kill;
4391 /* We need to use a scratch set here so that the value returned from this
4392 function invocation properly reflects whether the sets changed in a
4393 significant way; i.e. not just because the live set was anded in. */
4394 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4396 /* Multiple definitions of a register are not relevant if it is not
4397 live. Thus we trim the result to the places where it is live. */
4398 bitmap_and_into (in, df_get_live_in (bb));
4400 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4403 /* Initialize the solution bit vectors for problem. */
4406 df_md_init (bitmap all_blocks)
4408 unsigned int bb_index;
4411 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4413 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4415 bitmap_copy (&bb_info->in, &bb_info->init);
4416 df_md_transfer_function (bb_index);
4421 df_md_confluence_0 (basic_block bb)
4423 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4424 bitmap_copy (&bb_info->in, &bb_info->init);
4427 /* In of target gets or of out of source. */
4430 df_md_confluence_n (edge e)
4432 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4433 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4435 if (e->flags & EDGE_FAKE)
4438 if (e->flags & EDGE_EH)
4439 bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
4441 bitmap_ior_into (op1, op2);
4444 /* Free all storage associated with the problem. */
4449 struct df_md_problem_data *problem_data
4450 = (struct df_md_problem_data *) df_md->problem_data;
4452 bitmap_obstack_release (&problem_data->md_bitmaps);
4453 free (problem_data);
4454 df_md->problem_data = NULL;
4456 df_md->block_info_size = 0;
4457 free (df_md->block_info);
4458 df_md->block_info = NULL;
4463 /* Debugging info at top of bb. */
4466 df_md_top_dump (basic_block bb, FILE *file)
4468 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4472 fprintf (file, ";; md in \t");
4473 df_print_regset (file, &bb_info->in);
4474 fprintf (file, ";; md init \t");
4475 df_print_regset (file, &bb_info->init);
4476 fprintf (file, ";; md gen \t");
4477 df_print_regset (file, &bb_info->gen);
4478 fprintf (file, ";; md kill \t");
4479 df_print_regset (file, &bb_info->kill);
4482 /* Debugging info at bottom of bb. */
4485 df_md_bottom_dump (basic_block bb, FILE *file)
4487 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4491 fprintf (file, ";; md out \t");
4492 df_print_regset (file, &bb_info->out);
4495 static struct df_problem problem_MD =
4497 DF_MD, /* Problem id. */
4498 DF_FORWARD, /* Direction. */
4499 df_md_alloc, /* Allocate the problem specific data. */
4500 df_md_reset, /* Reset global information. */
4501 df_md_free_bb_info, /* Free basic block info. */
4502 df_md_local_compute, /* Local compute function. */
4503 df_md_init, /* Init the solution specific data. */
4504 df_worklist_dataflow, /* Worklist solver. */
4505 df_md_confluence_0, /* Confluence operator 0. */
4506 df_md_confluence_n, /* Confluence operator n. */
4507 df_md_transfer_function, /* Transfer function. */
4508 NULL, /* Finalize function. */
4509 df_md_free, /* Free all of the problem information. */
4510 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4511 NULL, /* Debugging. */
4512 df_md_top_dump, /* Debugging start block. */
4513 df_md_bottom_dump, /* Debugging end block. */
4514 NULL, /* Incremental solution verify start. */
4515 NULL, /* Incremental solution verify end. */
4516 NULL, /* Dependent problem. */
4517 sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */
4518 TV_DF_MD, /* Timing variable. */
4519 false /* Reset blocks on dropping out of blocks_to_analyze. */
4522 /* Create a new MD instance and add it to the existing instance
4526 df_md_add_problem (void)
4528 df_add_problem (&problem_MD);