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 /* Grow the bb_info array. */
106 df_grow_bb_info (struct dataflow *dflow)
108 unsigned int new_size = last_basic_block + 1;
109 if (dflow->block_info_size < new_size)
111 new_size += new_size / 4;
112 dflow->block_info = XRESIZEVEC (void *, dflow->block_info, new_size);
113 memset (dflow->block_info + dflow->block_info_size, 0,
114 (new_size - dflow->block_info_size) *sizeof (void *));
115 dflow->block_info_size = new_size;
119 /* Dump a def-use or use-def chain for REF to FILE. */
122 df_chain_dump (struct df_link *link, FILE *file)
124 fprintf (file, "{ ");
125 for (; link; link = link->next)
127 fprintf (file, "%c%d(bb %d insn %d) ",
128 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
129 DF_REF_ID (link->ref),
130 DF_REF_BBNO (link->ref),
131 DF_REF_IS_ARTIFICIAL (link->ref) ? -1 : DF_REF_INSN_UID (link->ref));
137 /* Print some basic block info as part of df_dump. */
140 df_print_bb_index (basic_block bb, FILE *file)
145 fprintf (file, "\n( ");
146 FOR_EACH_EDGE (e, ei, bb->preds)
148 basic_block pred = e->src;
149 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
151 fprintf (file, ")->[%d]->( ", bb->index);
152 FOR_EACH_EDGE (e, ei, bb->succs)
154 basic_block succ = e->dest;
155 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
157 fprintf (file, ")\n");
161 /*----------------------------------------------------------------------------
164 Find the locations in the function where each definition site for a
165 pseudo reaches. In and out bitvectors are built for each basic
166 block. The id field in the ref is used to index into these sets.
167 See df.h for details.
168 ----------------------------------------------------------------------------*/
170 /* This problem plays a large number of games for the sake of
173 1) The order of the bits in the bitvectors. After the scanning
174 phase, all of the defs are sorted. All of the defs for the reg 0
175 are first, followed by all defs for reg 1 and so on.
177 2) There are two kill sets, one if the number of defs is less or
178 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
181 <= : Data is built directly in the kill set.
183 > : One level of indirection is used to keep from generating long
184 strings of 1 bits in the kill sets. Bitvectors that are indexed
185 by the regnum are used to represent that there is a killing def
186 for the register. The confluence and transfer functions use
187 these along with the bitmap_clear_range call to remove ranges of
188 bits without actually generating a knockout vector.
190 The kill and sparse_kill and the dense_invalidated_by_call and
191 sparse_invalidated_by_call both play this game. */
193 /* Private data used to compute the solution for this problem. These
194 data structures are not accessible outside of this module. */
195 struct df_rd_problem_data
197 /* The set of defs to regs invalidated by call. */
198 bitmap_head sparse_invalidated_by_call;
199 /* The set of defs to regs invalidate by call for rd. */
200 bitmap_head dense_invalidated_by_call;
201 /* An obstack for the bitmaps we need for this problem. */
202 bitmap_obstack rd_bitmaps;
205 /* Set basic block info. */
208 df_rd_set_bb_info (unsigned int index,
209 struct df_rd_bb_info *bb_info)
212 gcc_assert (index < df_rd->block_info_size);
213 df_rd->block_info[index] = bb_info;
217 /* Free basic block info. */
220 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
223 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
226 bitmap_clear (&bb_info->kill);
227 bitmap_clear (&bb_info->sparse_kill);
228 bitmap_clear (&bb_info->gen);
229 bitmap_clear (&bb_info->in);
230 bitmap_clear (&bb_info->out);
231 pool_free (df_rd->block_pool, bb_info);
236 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
237 not touched unless the block is new. */
240 df_rd_alloc (bitmap all_blocks)
242 unsigned int bb_index;
244 struct df_rd_problem_data *problem_data;
246 if (!df_rd->block_pool)
247 df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
248 sizeof (struct df_rd_bb_info), 50);
250 if (df_rd->problem_data)
252 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
253 bitmap_clear (&problem_data->sparse_invalidated_by_call);
254 bitmap_clear (&problem_data->dense_invalidated_by_call);
258 problem_data = XNEW (struct df_rd_problem_data);
259 df_rd->problem_data = problem_data;
261 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
262 bitmap_initialize (&problem_data->sparse_invalidated_by_call,
263 &problem_data->rd_bitmaps);
264 bitmap_initialize (&problem_data->dense_invalidated_by_call,
265 &problem_data->rd_bitmaps);
268 df_grow_bb_info (df_rd);
270 /* Because of the clustering of all use sites for the same pseudo,
271 we have to process all of the blocks before doing the
274 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
276 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
279 bitmap_clear (&bb_info->kill);
280 bitmap_clear (&bb_info->sparse_kill);
281 bitmap_clear (&bb_info->gen);
285 bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
286 df_rd_set_bb_info (bb_index, bb_info);
287 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
288 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
289 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
290 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
291 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
294 df_rd->optional_p = true;
298 /* Add the effect of the top artificial defs of BB to the reaching definitions
302 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
304 int bb_index = bb->index;
306 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
308 df_ref def = *def_rec;
309 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
311 unsigned int dregno = DF_REF_REGNO (def);
312 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
313 bitmap_clear_range (local_rd,
314 DF_DEFS_BEGIN (dregno),
315 DF_DEFS_COUNT (dregno));
316 bitmap_set_bit (local_rd, DF_REF_ID (def));
321 /* Add the effect of the defs of INSN to the reaching definitions bitmap
325 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
328 unsigned uid = INSN_UID (insn);
331 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
333 df_ref def = *def_rec;
334 unsigned int dregno = DF_REF_REGNO (def);
335 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
336 || (dregno >= FIRST_PSEUDO_REGISTER))
338 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
339 bitmap_clear_range (local_rd,
340 DF_DEFS_BEGIN (dregno),
341 DF_DEFS_COUNT (dregno));
342 if (!(DF_REF_FLAGS (def)
343 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
344 bitmap_set_bit (local_rd, DF_REF_ID (def));
349 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
350 more complicated than just simulating, because we must produce the
351 gen and kill sets and hence deal with the two possible representations
355 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
361 df_ref def = *def_rec;
362 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
364 unsigned int regno = DF_REF_REGNO (def);
365 unsigned int begin = DF_DEFS_BEGIN (regno);
366 unsigned int n_defs = DF_DEFS_COUNT (regno);
368 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
369 || (regno >= FIRST_PSEUDO_REGISTER))
371 /* Only the last def(s) for a regno in the block has any
373 if (!bitmap_bit_p (&seen_in_block, regno))
375 /* The first def for regno in insn gets to knock out the
376 defs from other instructions. */
377 if ((!bitmap_bit_p (&seen_in_insn, regno))
378 /* If the def is to only part of the reg, it does
379 not kill the other defs that reach here. */
380 && (!(DF_REF_FLAGS (def) &
381 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
383 if (n_defs > DF_SPARSE_THRESHOLD)
385 bitmap_set_bit (&bb_info->sparse_kill, regno);
386 bitmap_clear_range(&bb_info->gen, begin, n_defs);
390 bitmap_set_range (&bb_info->kill, begin, n_defs);
391 bitmap_clear_range (&bb_info->gen, begin, n_defs);
395 bitmap_set_bit (&seen_in_insn, regno);
396 /* All defs for regno in the instruction may be put into
398 if (!(DF_REF_FLAGS (def)
399 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
400 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
408 /* Compute local reaching def info for basic block BB. */
411 df_rd_bb_local_compute (unsigned int bb_index)
413 basic_block bb = BASIC_BLOCK (bb_index);
414 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
417 bitmap_clear (&seen_in_block);
418 bitmap_clear (&seen_in_insn);
420 /* Artificials are only hard regs. */
421 if (!(df->changeable_flags & DF_NO_HARD_REGS))
422 df_rd_bb_local_compute_process_def (bb_info,
423 df_get_artificial_defs (bb_index),
426 FOR_BB_INSNS_REVERSE (bb, insn)
428 unsigned int uid = INSN_UID (insn);
433 df_rd_bb_local_compute_process_def (bb_info,
434 DF_INSN_UID_DEFS (uid), 0);
436 /* This complex dance with the two bitmaps is required because
437 instructions can assign twice to the same pseudo. This
438 generally happens with calls that will have one def for the
439 result and another def for the clobber. If only one vector
440 is used and the clobber goes first, the result will be
442 bitmap_ior_into (&seen_in_block, &seen_in_insn);
443 bitmap_clear (&seen_in_insn);
446 /* Process the artificial defs at the top of the block last since we
447 are going backwards through the block and these are logically at
449 if (!(df->changeable_flags & DF_NO_HARD_REGS))
450 df_rd_bb_local_compute_process_def (bb_info,
451 df_get_artificial_defs (bb_index),
456 /* Compute local reaching def info for each basic block within BLOCKS. */
459 df_rd_local_compute (bitmap all_blocks)
461 unsigned int bb_index;
464 struct df_rd_problem_data *problem_data
465 = (struct df_rd_problem_data *) df_rd->problem_data;
466 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
467 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
469 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
470 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
472 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
474 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
476 df_rd_bb_local_compute (bb_index);
479 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
480 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
482 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
483 bitmap_set_bit (sparse_invalidated, regno);
485 bitmap_set_range (dense_invalidated,
486 DF_DEFS_BEGIN (regno),
487 DF_DEFS_COUNT (regno));
490 bitmap_clear (&seen_in_block);
491 bitmap_clear (&seen_in_insn);
495 /* Initialize the solution bit vectors for problem. */
498 df_rd_init_solution (bitmap all_blocks)
500 unsigned int bb_index;
503 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
505 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
507 bitmap_copy (&bb_info->out, &bb_info->gen);
508 bitmap_clear (&bb_info->in);
512 /* In of target gets or of out of source. */
515 df_rd_confluence_n (edge e)
517 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
518 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
520 if (e->flags & EDGE_FAKE)
523 if (e->flags & EDGE_EH)
525 struct df_rd_problem_data *problem_data
526 = (struct df_rd_problem_data *) df_rd->problem_data;
527 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
528 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
533 bitmap_initialize (&tmp, &df_bitmap_obstack);
534 bitmap_copy (&tmp, op2);
535 bitmap_and_compl_into (&tmp, dense_invalidated);
537 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
539 bitmap_clear_range (&tmp,
540 DF_DEFS_BEGIN (regno),
541 DF_DEFS_COUNT (regno));
543 bitmap_ior_into (op1, &tmp);
547 bitmap_ior_into (op1, op2);
551 /* Transfer function. */
554 df_rd_transfer_function (int bb_index)
556 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
559 bitmap in = &bb_info->in;
560 bitmap out = &bb_info->out;
561 bitmap gen = &bb_info->gen;
562 bitmap kill = &bb_info->kill;
563 bitmap sparse_kill = &bb_info->sparse_kill;
565 if (bitmap_empty_p (sparse_kill))
566 return bitmap_ior_and_compl (out, gen, in, kill);
569 struct df_rd_problem_data *problem_data;
570 bool changed = false;
573 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
574 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
575 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
576 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
578 bitmap_copy (&tmp, in);
579 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
581 bitmap_clear_range (&tmp,
582 DF_DEFS_BEGIN (regno),
583 DF_DEFS_COUNT (regno));
585 bitmap_and_compl_into (&tmp, kill);
586 bitmap_ior_into (&tmp, gen);
587 changed = !bitmap_equal_p (&tmp, out);
600 /* Free all storage associated with the problem. */
605 struct df_rd_problem_data *problem_data
606 = (struct df_rd_problem_data *) df_rd->problem_data;
610 free_alloc_pool (df_rd->block_pool);
611 bitmap_obstack_release (&problem_data->rd_bitmaps);
613 df_rd->block_info_size = 0;
614 free (df_rd->block_info);
615 free (df_rd->problem_data);
621 /* Debugging info. */
624 df_rd_start_dump (FILE *file)
626 struct df_rd_problem_data *problem_data
627 = (struct df_rd_problem_data *) df_rd->problem_data;
628 unsigned int m = DF_REG_SIZE(df);
631 if (!df_rd->block_info)
634 fprintf (file, ";; Reaching defs:\n\n");
636 fprintf (file, " sparse invalidated \t");
637 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
638 fprintf (file, " dense invalidated \t");
639 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
641 for (regno = 0; regno < m; regno++)
642 if (DF_DEFS_COUNT (regno))
643 fprintf (file, "%d[%d,%d] ", regno,
644 DF_DEFS_BEGIN (regno),
645 DF_DEFS_COUNT (regno));
646 fprintf (file, "\n");
651 /* Debugging info at top of bb. */
654 df_rd_top_dump (basic_block bb, FILE *file)
656 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
660 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (&bb_info->in));
661 dump_bitmap (file, &bb_info->in);
662 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (&bb_info->gen));
663 dump_bitmap (file, &bb_info->gen);
664 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (&bb_info->kill));
665 dump_bitmap (file, &bb_info->kill);
669 /* Debugging info at top of bb. */
672 df_rd_bottom_dump (basic_block bb, FILE *file)
674 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
678 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (&bb_info->out));
679 dump_bitmap (file, &bb_info->out);
682 /* All of the information associated with every instance of the problem. */
684 static struct df_problem problem_RD =
686 DF_RD, /* Problem id. */
687 DF_FORWARD, /* Direction. */
688 df_rd_alloc, /* Allocate the problem specific data. */
689 NULL, /* Reset global information. */
690 df_rd_free_bb_info, /* Free basic block info. */
691 df_rd_local_compute, /* Local compute function. */
692 df_rd_init_solution, /* Init the solution specific data. */
693 df_worklist_dataflow, /* Worklist solver. */
694 NULL, /* Confluence operator 0. */
695 df_rd_confluence_n, /* Confluence operator n. */
696 df_rd_transfer_function, /* Transfer function. */
697 NULL, /* Finalize function. */
698 df_rd_free, /* Free all of the problem information. */
699 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
700 df_rd_start_dump, /* Debugging. */
701 df_rd_top_dump, /* Debugging start block. */
702 df_rd_bottom_dump, /* Debugging end block. */
703 NULL, /* Incremental solution verify start. */
704 NULL, /* Incremental solution verify end. */
705 NULL, /* Dependent problem. */
706 TV_DF_RD, /* Timing variable. */
707 true /* Reset blocks on dropping out of blocks_to_analyze. */
712 /* Create a new RD instance and add it to the existing instance
716 df_rd_add_problem (void)
718 df_add_problem (&problem_RD);
723 /*----------------------------------------------------------------------------
726 Find the locations in the function where any use of a pseudo can
727 reach in the backwards direction. In and out bitvectors are built
728 for each basic block. The regno is used to index into these sets.
729 See df.h for details.
730 ----------------------------------------------------------------------------*/
732 /* Private data used to verify the solution for this problem. */
733 struct df_lr_problem_data
740 /* Set basic block info. */
743 df_lr_set_bb_info (unsigned int index,
744 struct df_lr_bb_info *bb_info)
747 gcc_assert (index < df_lr->block_info_size);
748 df_lr->block_info[index] = bb_info;
752 /* Free basic block info. */
755 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
758 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
761 bitmap_clear (&bb_info->use);
762 bitmap_clear (&bb_info->def);
763 bitmap_clear (&bb_info->in);
764 bitmap_clear (&bb_info->out);
765 pool_free (df_lr->block_pool, bb_info);
770 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
771 not touched unless the block is new. */
774 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
776 unsigned int bb_index;
779 if (!df_lr->block_pool)
780 df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
781 sizeof (struct df_lr_bb_info), 50);
783 df_grow_bb_info (df_lr);
785 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
787 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
790 bitmap_clear (&bb_info->def);
791 bitmap_clear (&bb_info->use);
795 bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
796 df_lr_set_bb_info (bb_index, bb_info);
797 bitmap_initialize (&bb_info->use, &bitmap_default_obstack);
798 bitmap_initialize (&bb_info->def, &bitmap_default_obstack);
799 bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
800 bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
804 df_lr->optional_p = false;
808 /* Reset the global solution for recalculation. */
811 df_lr_reset (bitmap all_blocks)
813 unsigned int bb_index;
816 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
818 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
819 gcc_assert (bb_info);
820 bitmap_clear (&bb_info->in);
821 bitmap_clear (&bb_info->out);
826 /* Compute local live register info for basic block BB. */
829 df_lr_bb_local_compute (unsigned int bb_index)
831 basic_block bb = BASIC_BLOCK (bb_index);
832 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
837 /* Process the registers set in an exception handler. */
838 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
840 df_ref def = *def_rec;
841 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
843 unsigned int dregno = DF_REF_REGNO (def);
844 bitmap_set_bit (&bb_info->def, dregno);
845 bitmap_clear_bit (&bb_info->use, dregno);
849 /* Process the hardware registers that are always live. */
850 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
852 df_ref use = *use_rec;
853 /* Add use to set of uses in this BB. */
854 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
855 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
858 FOR_BB_INSNS_REVERSE (bb, insn)
860 unsigned int uid = INSN_UID (insn);
862 if (!NONDEBUG_INSN_P (insn))
865 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
867 df_ref def = *def_rec;
868 /* If the def is to only part of the reg, it does
869 not kill the other defs that reach here. */
870 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
872 unsigned int dregno = DF_REF_REGNO (def);
873 bitmap_set_bit (&bb_info->def, dregno);
874 bitmap_clear_bit (&bb_info->use, dregno);
878 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
880 df_ref use = *use_rec;
881 /* Add use to set of uses in this BB. */
882 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
886 /* Process the registers set in an exception handler or the hard
887 frame pointer if this block is the target of a non local
889 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
891 df_ref def = *def_rec;
892 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
894 unsigned int dregno = DF_REF_REGNO (def);
895 bitmap_set_bit (&bb_info->def, dregno);
896 bitmap_clear_bit (&bb_info->use, dregno);
901 /* Process the uses that are live into an exception handler. */
902 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
904 df_ref use = *use_rec;
905 /* Add use to set of uses in this BB. */
906 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
907 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
911 /* If the df_live problem is not defined, such as at -O0 and -O1, we
912 still need to keep the luids up to date. This is normally done
913 in the df_live problem since this problem has a forwards
916 df_recompute_luids (bb);
920 /* Compute local live register info for each basic block within BLOCKS. */
923 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
925 unsigned int bb_index;
928 bitmap_clear (&df->hardware_regs_used);
930 /* The all-important stack pointer must always be live. */
931 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
933 /* Before reload, there are a few registers that must be forced
934 live everywhere -- which might not already be the case for
935 blocks within infinite loops. */
936 if (!reload_completed)
938 /* Any reference to any pseudo before reload is a potential
939 reference of the frame pointer. */
940 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
942 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
943 /* Pseudos with argument area equivalences may require
944 reloading via the argument pointer. */
945 if (fixed_regs[ARG_POINTER_REGNUM])
946 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
949 /* Any constant, or pseudo with constant equivalences, may
950 require reloading from memory using the pic register. */
951 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
952 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
953 bitmap_set_bit (&df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
956 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
958 if (bb_index == EXIT_BLOCK)
960 /* The exit block is special for this problem and its bits are
961 computed from thin air. */
962 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
963 bitmap_copy (&bb_info->use, df->exit_block_uses);
966 df_lr_bb_local_compute (bb_index);
969 bitmap_clear (df_lr->out_of_date_transfer_functions);
973 /* Initialize the solution vectors. */
976 df_lr_init (bitmap all_blocks)
978 unsigned int bb_index;
981 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
983 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
984 bitmap_copy (&bb_info->in, &bb_info->use);
985 bitmap_clear (&bb_info->out);
990 /* Confluence function that processes infinite loops. This might be a
991 noreturn function that throws. And even if it isn't, getting the
992 unwind info right helps debugging. */
994 df_lr_confluence_0 (basic_block bb)
996 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
997 if (bb != EXIT_BLOCK_PTR)
998 bitmap_copy (op1, &df->hardware_regs_used);
1002 /* Confluence function that ignores fake edges. */
1005 df_lr_confluence_n (edge e)
1007 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
1008 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
1010 /* Call-clobbered registers die across exception and call edges. */
1011 /* ??? Abnormal call edges ignored for the moment, as this gets
1012 confused by sibling call edges, which crashes reg-stack. */
1013 if (e->flags & EDGE_EH)
1014 bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
1016 bitmap_ior_into (op1, op2);
1018 bitmap_ior_into (op1, &df->hardware_regs_used);
1022 /* Transfer function. */
1025 df_lr_transfer_function (int bb_index)
1027 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1028 bitmap in = &bb_info->in;
1029 bitmap out = &bb_info->out;
1030 bitmap use = &bb_info->use;
1031 bitmap def = &bb_info->def;
1033 return bitmap_ior_and_compl (in, use, out, def);
1037 /* Run the fast dce as a side effect of building LR. */
1040 df_lr_finalize (bitmap all_blocks)
1042 df_lr->solutions_dirty = false;
1043 if (df->changeable_flags & DF_LR_RUN_DCE)
1047 /* If dce deletes some instructions, we need to recompute the lr
1048 solution before proceeding further. The problem is that fast
1049 dce is a pessimestic dataflow algorithm. In the case where
1050 it deletes a statement S inside of a loop, the uses inside of
1051 S may not be deleted from the dataflow solution because they
1052 were carried around the loop. While it is conservatively
1053 correct to leave these extra bits, the standards of df
1054 require that we maintain the best possible (least fixed
1055 point) solution. The only way to do that is to redo the
1056 iteration from the beginning. See PR35805 for an
1058 if (df_lr->solutions_dirty)
1060 df_clear_flags (DF_LR_RUN_DCE);
1061 df_lr_alloc (all_blocks);
1062 df_lr_local_compute (all_blocks);
1063 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1064 df_lr_finalize (all_blocks);
1065 df_set_flags (DF_LR_RUN_DCE);
1071 /* Free all storage associated with the problem. */
1076 if (df_lr->block_info)
1079 for (i = 0; i < df_lr->block_info_size; i++)
1081 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1084 bitmap_clear (&bb_info->use);
1085 bitmap_clear (&bb_info->def);
1086 bitmap_clear (&bb_info->in);
1087 bitmap_clear (&bb_info->out);
1090 free_alloc_pool (df_lr->block_pool);
1092 df_lr->block_info_size = 0;
1093 free (df_lr->block_info);
1096 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1101 /* Debugging info at top of bb. */
1104 df_lr_top_dump (basic_block bb, FILE *file)
1106 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1107 struct df_lr_problem_data *problem_data;
1111 fprintf (file, ";; lr in \t");
1112 df_print_regset (file, &bb_info->in);
1113 if (df_lr->problem_data)
1115 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1116 fprintf (file, ";; old in \t");
1117 df_print_regset (file, &problem_data->in[bb->index]);
1119 fprintf (file, ";; lr use \t");
1120 df_print_regset (file, &bb_info->use);
1121 fprintf (file, ";; lr def \t");
1122 df_print_regset (file, &bb_info->def);
1126 /* Debugging info at bottom of bb. */
1129 df_lr_bottom_dump (basic_block bb, FILE *file)
1131 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1132 struct df_lr_problem_data *problem_data;
1136 fprintf (file, ";; lr out \t");
1137 df_print_regset (file, &bb_info->out);
1138 if (df_lr->problem_data)
1140 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1141 fprintf (file, ";; old out \t");
1142 df_print_regset (file, &problem_data->out[bb->index]);
1147 /* Build the datastructure to verify that the solution to the dataflow
1148 equations is not dirty. */
1151 df_lr_verify_solution_start (void)
1154 struct df_lr_problem_data *problem_data;
1155 if (df_lr->solutions_dirty)
1157 df_lr->problem_data = NULL;
1161 /* Set it true so that the solution is recomputed. */
1162 df_lr->solutions_dirty = true;
1164 problem_data = XNEW (struct df_lr_problem_data);
1165 df_lr->problem_data = problem_data;
1166 problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
1167 problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
1171 bitmap_initialize (&problem_data->in[bb->index], &bitmap_default_obstack);
1172 bitmap_initialize (&problem_data->out[bb->index], &bitmap_default_obstack);
1173 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1174 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1179 /* Compare the saved datastructure and the new solution to the dataflow
1183 df_lr_verify_solution_end (void)
1185 struct df_lr_problem_data *problem_data;
1188 if (df_lr->problem_data == NULL)
1191 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1193 if (df_lr->solutions_dirty)
1194 /* Do not check if the solution is still dirty. See the comment
1195 in df_lr_finalize for details. */
1196 df_lr->solutions_dirty = false;
1200 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1201 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1203 /*df_dump (stderr);*/
1208 /* Cannot delete them immediately because you may want to dump them
1209 if the comparison fails. */
1212 bitmap_clear (&problem_data->in[bb->index]);
1213 bitmap_clear (&problem_data->out[bb->index]);
1216 free (problem_data->in);
1217 free (problem_data->out);
1218 free (problem_data);
1219 df_lr->problem_data = NULL;
1223 /* All of the information associated with every instance of the problem. */
1225 static struct df_problem problem_LR =
1227 DF_LR, /* Problem id. */
1228 DF_BACKWARD, /* Direction. */
1229 df_lr_alloc, /* Allocate the problem specific data. */
1230 df_lr_reset, /* Reset global information. */
1231 df_lr_free_bb_info, /* Free basic block info. */
1232 df_lr_local_compute, /* Local compute function. */
1233 df_lr_init, /* Init the solution specific data. */
1234 df_worklist_dataflow, /* Worklist solver. */
1235 df_lr_confluence_0, /* Confluence operator 0. */
1236 df_lr_confluence_n, /* Confluence operator n. */
1237 df_lr_transfer_function, /* Transfer function. */
1238 df_lr_finalize, /* Finalize function. */
1239 df_lr_free, /* Free all of the problem information. */
1240 NULL, /* Remove this problem from the stack of dataflow problems. */
1241 NULL, /* Debugging. */
1242 df_lr_top_dump, /* Debugging start block. */
1243 df_lr_bottom_dump, /* Debugging end block. */
1244 df_lr_verify_solution_start,/* Incremental solution verify start. */
1245 df_lr_verify_solution_end, /* Incremental solution verify end. */
1246 NULL, /* Dependent problem. */
1247 TV_DF_LR, /* Timing variable. */
1248 false /* Reset blocks on dropping out of blocks_to_analyze. */
1252 /* Create a new DATAFLOW instance and add it to an existing instance
1253 of DF. The returned structure is what is used to get at the
1257 df_lr_add_problem (void)
1259 df_add_problem (&problem_LR);
1260 /* These will be initialized when df_scan_blocks processes each
1262 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1266 /* Verify that all of the lr related info is consistent and
1270 df_lr_verify_transfer_functions (void)
1273 bitmap_head saved_def;
1274 bitmap_head saved_use;
1275 bitmap_head all_blocks;
1280 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1281 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1282 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1286 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1287 bitmap_set_bit (&all_blocks, bb->index);
1291 /* Make a copy of the transfer functions and then compute
1292 new ones to see if the transfer functions have
1294 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1297 bitmap_copy (&saved_def, &bb_info->def);
1298 bitmap_copy (&saved_use, &bb_info->use);
1299 bitmap_clear (&bb_info->def);
1300 bitmap_clear (&bb_info->use);
1302 df_lr_bb_local_compute (bb->index);
1303 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1304 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1309 /* If we do not have basic block info, the block must be in
1310 the list of dirty blocks or else some one has added a
1311 block behind our backs. */
1312 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1315 /* Make sure no one created a block without following
1317 gcc_assert (df_scan_get_bb_info (bb->index));
1320 /* Make sure there are no dirty bits in blocks that have been deleted. */
1321 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1324 bitmap_clear (&saved_def);
1325 bitmap_clear (&saved_use);
1326 bitmap_clear (&all_blocks);
1331 /*----------------------------------------------------------------------------
1332 LIVE AND MUST-INITIALIZED REGISTERS.
1334 This problem first computes the IN and OUT bitvectors for the
1335 must-initialized registers problems, which is a forward problem.
1336 It gives the set of registers for which we MUST have an available
1337 definition on any path from the entry block to the entry/exit of
1338 a basic block. Sets generate a definition, while clobbers kill
1341 In and out bitvectors are built for each basic block and are indexed by
1342 regnum (see df.h for details). In and out bitvectors in struct
1343 df_live_bb_info actually refers to the must-initialized problem;
1345 Then, the in and out sets for the LIVE problem itself are computed.
1346 These are the logical AND of the IN and OUT sets from the LR problem
1347 and the must-initialized problem.
1348 ----------------------------------------------------------------------------*/
1350 /* Private data used to verify the solution for this problem. */
1351 struct df_live_problem_data
1357 /* Scratch var used by transfer functions. This is used to implement
1358 an optimization to reduce the amount of space used to compute the
1359 combined lr and live analysis. */
1360 static bitmap df_live_scratch;
1362 /* Set basic block info. */
1365 df_live_set_bb_info (unsigned int index,
1366 struct df_live_bb_info *bb_info)
1368 gcc_assert (df_live);
1369 gcc_assert (index < df_live->block_info_size);
1370 df_live->block_info[index] = bb_info;
1374 /* Free basic block info. */
1377 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1380 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1383 bitmap_clear (&bb_info->gen);
1384 bitmap_clear (&bb_info->kill);
1385 bitmap_clear (&bb_info->in);
1386 bitmap_clear (&bb_info->out);
1387 pool_free (df_live->block_pool, bb_info);
1392 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1393 not touched unless the block is new. */
1396 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1398 unsigned int bb_index;
1401 if (!df_live->block_pool)
1402 df_live->block_pool = create_alloc_pool ("df_live_block pool",
1403 sizeof (struct df_live_bb_info), 100);
1404 if (!df_live_scratch)
1405 df_live_scratch = BITMAP_ALLOC (NULL);
1407 df_grow_bb_info (df_live);
1409 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1411 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1414 bitmap_clear (&bb_info->kill);
1415 bitmap_clear (&bb_info->gen);
1419 bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1420 df_live_set_bb_info (bb_index, bb_info);
1421 bitmap_initialize (&bb_info->kill, &bitmap_default_obstack);
1422 bitmap_initialize (&bb_info->gen, &bitmap_default_obstack);
1423 bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
1424 bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
1427 df_live->optional_p = (optimize <= 1);
1431 /* Reset the global solution for recalculation. */
1434 df_live_reset (bitmap all_blocks)
1436 unsigned int bb_index;
1439 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1441 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1442 gcc_assert (bb_info);
1443 bitmap_clear (&bb_info->in);
1444 bitmap_clear (&bb_info->out);
1449 /* Compute local uninitialized register info for basic block BB. */
1452 df_live_bb_local_compute (unsigned int bb_index)
1454 basic_block bb = BASIC_BLOCK (bb_index);
1455 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1460 FOR_BB_INSNS (bb, insn)
1462 unsigned int uid = INSN_UID (insn);
1463 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1465 /* Inserting labels does not always trigger the incremental
1469 gcc_assert (!INSN_P (insn));
1470 insn_info = df_insn_create_insn_record (insn);
1473 DF_INSN_INFO_LUID (insn_info) = luid;
1478 for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
1480 df_ref def = *def_rec;
1481 unsigned int regno = DF_REF_REGNO (def);
1483 if (DF_REF_FLAGS_IS_SET (def,
1484 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1485 /* All partial or conditional def
1486 seen are included in the gen set. */
1487 bitmap_set_bit (&bb_info->gen, regno);
1488 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1489 /* Only must clobbers for the entire reg destroy the
1491 bitmap_set_bit (&bb_info->kill, regno);
1492 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1493 bitmap_set_bit (&bb_info->gen, regno);
1497 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1499 df_ref def = *def_rec;
1500 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1505 /* Compute local uninitialized register info. */
1508 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1510 unsigned int bb_index;
1513 df_grow_insn_info ();
1515 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1518 df_live_bb_local_compute (bb_index);
1521 bitmap_clear (df_live->out_of_date_transfer_functions);
1525 /* Initialize the solution vectors. */
1528 df_live_init (bitmap all_blocks)
1530 unsigned int bb_index;
1533 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1535 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1536 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1538 /* No register may reach a location where it is not used. Thus
1539 we trim the rr result to the places where it is used. */
1540 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1541 bitmap_clear (&bb_info->in);
1545 /* Forward confluence function that ignores fake edges. */
1548 df_live_confluence_n (edge e)
1550 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1551 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1553 if (e->flags & EDGE_FAKE)
1556 bitmap_ior_into (op1, op2);
1560 /* Transfer function for the forwards must-initialized problem. */
1563 df_live_transfer_function (int bb_index)
1565 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1566 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1567 bitmap in = &bb_info->in;
1568 bitmap out = &bb_info->out;
1569 bitmap gen = &bb_info->gen;
1570 bitmap kill = &bb_info->kill;
1572 /* We need to use a scratch set here so that the value returned from this
1573 function invocation properly reflects whether the sets changed in a
1574 significant way; i.e. not just because the lr set was anded in. */
1575 bitmap_and (df_live_scratch, gen, &bb_lr_info->out);
1576 /* No register may reach a location where it is not used. Thus
1577 we trim the rr result to the places where it is used. */
1578 bitmap_and_into (in, &bb_lr_info->in);
1580 return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1584 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1587 df_live_finalize (bitmap all_blocks)
1590 if (df_live->solutions_dirty)
1593 unsigned int bb_index;
1595 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1597 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1598 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1600 /* No register may reach a location where it is not used. Thus
1601 we trim the rr result to the places where it is used. */
1602 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1603 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1606 df_live->solutions_dirty = false;
1611 /* Free all storage associated with the problem. */
1616 if (df_live->block_info)
1620 for (i = 0; i < df_live->block_info_size; i++)
1622 struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1625 bitmap_clear (&bb_info->gen);
1626 bitmap_clear (&bb_info->kill);
1627 bitmap_clear (&bb_info->in);
1628 bitmap_clear (&bb_info->out);
1632 free_alloc_pool (df_live->block_pool);
1633 df_live->block_info_size = 0;
1634 free (df_live->block_info);
1636 if (df_live_scratch)
1637 BITMAP_FREE (df_live_scratch);
1639 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1644 /* Debugging info at top of bb. */
1647 df_live_top_dump (basic_block bb, FILE *file)
1649 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1650 struct df_live_problem_data *problem_data;
1655 fprintf (file, ";; live in \t");
1656 df_print_regset (file, &bb_info->in);
1657 if (df_live->problem_data)
1659 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1660 fprintf (file, ";; old in \t");
1661 df_print_regset (file, &problem_data->in[bb->index]);
1663 fprintf (file, ";; live gen \t");
1664 df_print_regset (file, &bb_info->gen);
1665 fprintf (file, ";; live kill\t");
1666 df_print_regset (file, &bb_info->kill);
1670 /* Debugging info at bottom of bb. */
1673 df_live_bottom_dump (basic_block bb, FILE *file)
1675 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1676 struct df_live_problem_data *problem_data;
1681 fprintf (file, ";; live out \t");
1682 df_print_regset (file, &bb_info->out);
1683 if (df_live->problem_data)
1685 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1686 fprintf (file, ";; old out \t");
1687 df_print_regset (file, &problem_data->out[bb->index]);
1692 /* Build the datastructure to verify that the solution to the dataflow
1693 equations is not dirty. */
1696 df_live_verify_solution_start (void)
1699 struct df_live_problem_data *problem_data;
1700 if (df_live->solutions_dirty)
1702 df_live->problem_data = NULL;
1706 /* Set it true so that the solution is recomputed. */
1707 df_live->solutions_dirty = true;
1709 problem_data = XNEW (struct df_live_problem_data);
1710 df_live->problem_data = problem_data;
1711 problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
1712 problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
1716 bitmap_initialize (&problem_data->in[bb->index], &bitmap_default_obstack);
1717 bitmap_initialize (&problem_data->out[bb->index], &bitmap_default_obstack);
1718 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1719 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1724 /* Compare the saved datastructure and the new solution to the dataflow
1728 df_live_verify_solution_end (void)
1730 struct df_live_problem_data *problem_data;
1733 if (df_live->problem_data == NULL)
1736 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1740 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1741 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1743 /*df_dump (stderr);*/
1748 /* Cannot delete them immediately because you may want to dump them
1749 if the comparison fails. */
1752 bitmap_clear (&problem_data->in[bb->index]);
1753 bitmap_clear (&problem_data->out[bb->index]);
1756 free (problem_data->in);
1757 free (problem_data->out);
1758 free (problem_data);
1759 df_live->problem_data = NULL;
1763 /* All of the information associated with every instance of the problem. */
1765 static struct df_problem problem_LIVE =
1767 DF_LIVE, /* Problem id. */
1768 DF_FORWARD, /* Direction. */
1769 df_live_alloc, /* Allocate the problem specific data. */
1770 df_live_reset, /* Reset global information. */
1771 df_live_free_bb_info, /* Free basic block info. */
1772 df_live_local_compute, /* Local compute function. */
1773 df_live_init, /* Init the solution specific data. */
1774 df_worklist_dataflow, /* Worklist solver. */
1775 NULL, /* Confluence operator 0. */
1776 df_live_confluence_n, /* Confluence operator n. */
1777 df_live_transfer_function, /* Transfer function. */
1778 df_live_finalize, /* Finalize function. */
1779 df_live_free, /* Free all of the problem information. */
1780 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1781 NULL, /* Debugging. */
1782 df_live_top_dump, /* Debugging start block. */
1783 df_live_bottom_dump, /* Debugging end block. */
1784 df_live_verify_solution_start,/* Incremental solution verify start. */
1785 df_live_verify_solution_end, /* Incremental solution verify end. */
1786 &problem_LR, /* Dependent problem. */
1787 TV_DF_LIVE, /* Timing variable. */
1788 false /* Reset blocks on dropping out of blocks_to_analyze. */
1792 /* Create a new DATAFLOW instance and add it to an existing instance
1793 of DF. The returned structure is what is used to get at the
1797 df_live_add_problem (void)
1799 df_add_problem (&problem_LIVE);
1800 /* These will be initialized when df_scan_blocks processes each
1802 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1806 /* Set all of the blocks as dirty. This needs to be done if this
1807 problem is added after all of the insns have been scanned. */
1810 df_live_set_all_dirty (void)
1814 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1819 /* Verify that all of the lr related info is consistent and
1823 df_live_verify_transfer_functions (void)
1826 bitmap_head saved_gen;
1827 bitmap_head saved_kill;
1828 bitmap_head all_blocks;
1833 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1834 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1835 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1837 df_grow_insn_info ();
1841 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1842 bitmap_set_bit (&all_blocks, bb->index);
1846 /* Make a copy of the transfer functions and then compute
1847 new ones to see if the transfer functions have
1849 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1852 bitmap_copy (&saved_gen, &bb_info->gen);
1853 bitmap_copy (&saved_kill, &bb_info->kill);
1854 bitmap_clear (&bb_info->gen);
1855 bitmap_clear (&bb_info->kill);
1857 df_live_bb_local_compute (bb->index);
1858 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1859 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1864 /* If we do not have basic block info, the block must be in
1865 the list of dirty blocks or else some one has added a
1866 block behind our backs. */
1867 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1870 /* Make sure no one created a block without following
1872 gcc_assert (df_scan_get_bb_info (bb->index));
1875 /* Make sure there are no dirty bits in blocks that have been deleted. */
1876 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1878 bitmap_clear (&saved_gen);
1879 bitmap_clear (&saved_kill);
1880 bitmap_clear (&all_blocks);
1883 /*----------------------------------------------------------------------------
1884 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1886 Link either the defs to the uses and / or the uses to the defs.
1888 These problems are set up like the other dataflow problems so that
1889 they nicely fit into the framework. They are much simpler and only
1890 involve a single traversal of instructions and an examination of
1891 the reaching defs information (the dependent problem).
1892 ----------------------------------------------------------------------------*/
1894 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1896 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1899 df_chain_create (df_ref src, df_ref dst)
1901 struct df_link *head = DF_REF_CHAIN (src);
1902 struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1904 DF_REF_CHAIN (src) = link;
1911 /* Delete any du or ud chains that start at REF and point to
1914 df_chain_unlink_1 (df_ref ref, df_ref target)
1916 struct df_link *chain = DF_REF_CHAIN (ref);
1917 struct df_link *prev = NULL;
1921 if (chain->ref == target)
1924 prev->next = chain->next;
1926 DF_REF_CHAIN (ref) = chain->next;
1927 pool_free (df_chain->block_pool, chain);
1931 chain = chain->next;
1936 /* Delete a du or ud chain that leave or point to REF. */
1939 df_chain_unlink (df_ref ref)
1941 struct df_link *chain = DF_REF_CHAIN (ref);
1944 struct df_link *next = chain->next;
1945 /* Delete the other side if it exists. */
1946 df_chain_unlink_1 (chain->ref, ref);
1947 pool_free (df_chain->block_pool, chain);
1950 DF_REF_CHAIN (ref) = NULL;
1954 /* Copy the du or ud chain starting at FROM_REF and attach it to
1958 df_chain_copy (df_ref to_ref,
1959 struct df_link *from_ref)
1963 df_chain_create (to_ref, from_ref->ref);
1964 from_ref = from_ref->next;
1969 /* Remove this problem from the stack of dataflow problems. */
1972 df_chain_remove_problem (void)
1975 unsigned int bb_index;
1977 /* Wholesale destruction of the old chains. */
1978 if (df_chain->block_pool)
1979 free_alloc_pool (df_chain->block_pool);
1981 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1986 basic_block bb = BASIC_BLOCK (bb_index);
1988 if (df_chain_problem_p (DF_DU_CHAIN))
1989 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1990 DF_REF_CHAIN (*def_rec) = NULL;
1991 if (df_chain_problem_p (DF_UD_CHAIN))
1992 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1993 DF_REF_CHAIN (*use_rec) = NULL;
1995 FOR_BB_INSNS (bb, insn)
1997 unsigned int uid = INSN_UID (insn);
2001 if (df_chain_problem_p (DF_DU_CHAIN))
2002 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2003 DF_REF_CHAIN (*def_rec) = NULL;
2004 if (df_chain_problem_p (DF_UD_CHAIN))
2006 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2007 DF_REF_CHAIN (*use_rec) = NULL;
2008 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
2009 DF_REF_CHAIN (*use_rec) = NULL;
2015 bitmap_clear (df_chain->out_of_date_transfer_functions);
2016 df_chain->block_pool = NULL;
2020 /* Remove the chain problem completely. */
2023 df_chain_fully_remove_problem (void)
2025 df_chain_remove_problem ();
2026 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2031 /* Create def-use or use-def chains. */
2034 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2036 df_chain_remove_problem ();
2037 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2038 sizeof (struct df_link), 50);
2039 df_chain->optional_p = true;
2043 /* Reset all of the chains when the set of basic blocks changes. */
2046 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2048 df_chain_remove_problem ();
2052 /* Create the chains for a list of USEs. */
2055 df_chain_create_bb_process_use (bitmap local_rd,
2060 unsigned int def_index;
2064 df_ref use = *use_rec;
2065 unsigned int uregno = DF_REF_REGNO (use);
2066 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2067 || (uregno >= FIRST_PSEUDO_REGISTER))
2069 /* Do not want to go through this for an uninitialized var. */
2070 int count = DF_DEFS_COUNT (uregno);
2073 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2075 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2076 unsigned int last_index = first_index + count - 1;
2078 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2081 if (def_index > last_index)
2084 def = DF_DEFS_GET (def_index);
2085 if (df_chain_problem_p (DF_DU_CHAIN))
2086 df_chain_create (def, use);
2087 if (df_chain_problem_p (DF_UD_CHAIN))
2088 df_chain_create (use, def);
2099 /* Create chains from reaching defs bitmaps for basic block BB. */
2102 df_chain_create_bb (unsigned int bb_index)
2104 basic_block bb = BASIC_BLOCK (bb_index);
2105 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2109 bitmap_initialize (&cpy, &bitmap_default_obstack);
2110 bitmap_copy (&cpy, &bb_info->in);
2111 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2113 /* Since we are going forwards, process the artificial uses first
2114 then the artificial defs second. */
2117 /* Create the chains for the artificial uses from the EH_USES at the
2118 beginning of the block. */
2120 /* Artificials are only hard regs. */
2121 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2122 df_chain_create_bb_process_use (&cpy,
2123 df_get_artificial_uses (bb->index),
2127 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2129 /* Process the regular instructions next. */
2130 FOR_BB_INSNS (bb, insn)
2133 unsigned int uid = INSN_UID (insn);
2135 /* First scan the uses and link them up with the defs that remain
2136 in the cpy vector. */
2137 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2138 if (df->changeable_flags & DF_EQ_NOTES)
2139 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2141 /* Since we are going forwards, process the defs second. */
2142 df_rd_simulate_one_insn (bb, insn, &cpy);
2145 /* Create the chains for the artificial uses of the hard registers
2146 at the end of the block. */
2147 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2148 df_chain_create_bb_process_use (&cpy,
2149 df_get_artificial_uses (bb->index),
2152 bitmap_clear (&cpy);
2155 /* Create def-use chains from reaching use bitmaps for basic blocks
2159 df_chain_finalize (bitmap all_blocks)
2161 unsigned int bb_index;
2164 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2166 df_chain_create_bb (bb_index);
2171 /* Free all storage associated with the problem. */
2174 df_chain_free (void)
2176 free_alloc_pool (df_chain->block_pool);
2177 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2182 /* Debugging info. */
2185 df_chain_top_dump (basic_block bb, FILE *file)
2187 if (df_chain_problem_p (DF_DU_CHAIN))
2190 df_ref *def_rec = df_get_artificial_defs (bb->index);
2194 fprintf (file, ";; DU chains for artificial defs\n");
2197 df_ref def = *def_rec;
2198 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2199 df_chain_dump (DF_REF_CHAIN (def), file);
2200 fprintf (file, "\n");
2205 FOR_BB_INSNS (bb, insn)
2209 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2210 def_rec = DF_INSN_INFO_DEFS (insn_info);
2213 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2214 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2218 df_ref def = *def_rec;
2219 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2220 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2221 fprintf (file, "read/write ");
2222 df_chain_dump (DF_REF_CHAIN (def), file);
2223 fprintf (file, "\n");
2234 df_chain_bottom_dump (basic_block bb, FILE *file)
2236 if (df_chain_problem_p (DF_UD_CHAIN))
2239 df_ref *use_rec = df_get_artificial_uses (bb->index);
2243 fprintf (file, ";; UD chains for artificial uses\n");
2246 df_ref use = *use_rec;
2247 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2248 df_chain_dump (DF_REF_CHAIN (use), file);
2249 fprintf (file, "\n");
2254 FOR_BB_INSNS (bb, insn)
2258 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2259 df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2260 use_rec = DF_INSN_INFO_USES (insn_info);
2261 if (*use_rec || *eq_use_rec)
2263 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2264 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2268 df_ref use = *use_rec;
2269 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2270 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2271 fprintf (file, "read/write ");
2272 df_chain_dump (DF_REF_CHAIN (use), file);
2273 fprintf (file, "\n");
2278 df_ref use = *eq_use_rec;
2279 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2280 df_chain_dump (DF_REF_CHAIN (use), file);
2281 fprintf (file, "\n");
2291 static struct df_problem problem_CHAIN =
2293 DF_CHAIN, /* Problem id. */
2294 DF_NONE, /* Direction. */
2295 df_chain_alloc, /* Allocate the problem specific data. */
2296 df_chain_reset, /* Reset global information. */
2297 NULL, /* Free basic block info. */
2298 NULL, /* Local compute function. */
2299 NULL, /* Init the solution specific data. */
2300 NULL, /* Iterative solver. */
2301 NULL, /* Confluence operator 0. */
2302 NULL, /* Confluence operator n. */
2303 NULL, /* Transfer function. */
2304 df_chain_finalize, /* Finalize function. */
2305 df_chain_free, /* Free all of the problem information. */
2306 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2307 NULL, /* Debugging. */
2308 df_chain_top_dump, /* Debugging start block. */
2309 df_chain_bottom_dump, /* Debugging end block. */
2310 NULL, /* Incremental solution verify start. */
2311 NULL, /* Incremental solution verify end. */
2312 &problem_RD, /* Dependent problem. */
2313 TV_DF_CHAIN, /* Timing variable. */
2314 false /* Reset blocks on dropping out of blocks_to_analyze. */
2318 /* Create a new DATAFLOW instance and add it to an existing instance
2319 of DF. The returned structure is what is used to get at the
2323 df_chain_add_problem (unsigned int chain_flags)
2325 df_add_problem (&problem_CHAIN);
2326 df_chain->local_flags = chain_flags;
2327 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2330 #undef df_chain_problem_p
2333 /*----------------------------------------------------------------------------
2334 BYTE LEVEL LIVE REGISTERS
2336 Find the locations in the function where any use of a pseudo can
2337 reach in the backwards direction. In and out bitvectors are built
2338 for each basic block. There are two mapping functions,
2339 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2340 used to map regnos into bit vector positions.
2342 This problem differs from the regular df_lr function in the way
2343 that subregs, *_extracts and strict_low_parts are handled. In lr
2344 these are consider partial kills, here, the exact set of bytes is
2345 modeled. Note that any reg that has none of these operations is
2346 only modeled with a single bit since all operations access the
2349 This problem is more brittle that the regular lr. It currently can
2350 be used in dce incrementally, but cannot be used in an environment
2351 where insns are created or modified. The problem is that the
2352 mapping of regnos to bitmap positions is relatively compact, in
2353 that if a pseudo does not do any of the byte wise operations, only
2354 one slot is allocated, rather than a slot for each byte. If insn
2355 are created, where a subreg is used for a reg that had no subregs,
2356 the mapping would be wrong. Likewise, there are no checks to see
2357 that new pseudos have been added. These issues could be addressed
2358 by adding a problem specific flag to not use the compact mapping,
2359 if there was a need to do so.
2361 ----------------------------------------------------------------------------*/
2363 /* Private data used to verify the solution for this problem. */
2364 struct df_byte_lr_problem_data
2366 /* Expanded versions of bitvectors used in lr. */
2367 bitmap_head invalidated_by_call;
2368 bitmap_head hardware_regs_used;
2370 /* Indexed by regno, this is true if there are subregs, extracts or
2371 strict_low_parts for this regno. */
2372 bitmap_head needs_expansion;
2374 /* The start position and len for each regno in the various bit
2376 unsigned int* regno_start;
2377 unsigned int* regno_len;
2378 /* An obstack for the bitmaps we need for this problem. */
2379 bitmap_obstack byte_lr_bitmaps;
2383 /* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2386 df_byte_lr_get_regno_start (unsigned int regno)
2388 struct df_byte_lr_problem_data *problem_data
2389 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2390 return problem_data->regno_start[regno];
2394 /* Get the len for REGNO in the df_byte_lr bitmaps. */
2397 df_byte_lr_get_regno_len (unsigned int regno)
2399 struct df_byte_lr_problem_data *problem_data
2400 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2401 return problem_data->regno_len[regno];
2405 /* Set basic block info. */
2408 df_byte_lr_set_bb_info (unsigned int index,
2409 struct df_byte_lr_bb_info *bb_info)
2411 gcc_assert (df_byte_lr);
2412 gcc_assert (index < df_byte_lr->block_info_size);
2413 df_byte_lr->block_info[index] = bb_info;
2417 /* Free basic block info. */
2420 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2423 struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2426 bitmap_clear (&bb_info->use);
2427 bitmap_clear (&bb_info->def);
2428 bitmap_clear (&bb_info->in);
2429 bitmap_clear (&bb_info->out);
2430 pool_free (df_byte_lr->block_pool, bb_info);
2435 /* Check all of the refs in REF_REC to see if any of them are
2436 extracts, subregs or strict_low_parts. */
2439 df_byte_lr_check_regs (df_ref *ref_rec)
2441 struct df_byte_lr_problem_data *problem_data
2442 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2444 for (; *ref_rec; ref_rec++)
2446 df_ref ref = *ref_rec;
2447 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2448 | DF_REF_ZERO_EXTRACT
2449 | DF_REF_STRICT_LOW_PART)
2450 || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2451 bitmap_set_bit (&problem_data->needs_expansion, DF_REF_REGNO (ref));
2456 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2457 regno_start and regno_len. */
2460 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2462 struct df_byte_lr_problem_data *problem_data
2463 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2467 bitmap_clear (dest);
2468 EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2470 bitmap_set_range (dest, problem_data->regno_start[i],
2471 problem_data->regno_len[i]);
2476 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2477 not touched unless the block is new. */
2480 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2482 unsigned int bb_index;
2486 unsigned int index = 0;
2487 unsigned int max_reg = max_reg_num();
2488 struct df_byte_lr_problem_data *problem_data
2489 = XNEW (struct df_byte_lr_problem_data);
2491 df_byte_lr->problem_data = problem_data;
2493 if (!df_byte_lr->block_pool)
2494 df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool",
2495 sizeof (struct df_byte_lr_bb_info), 50);
2497 df_grow_bb_info (df_byte_lr);
2499 /* Create the mapping from regnos to slots. This does not change
2500 unless the problem is destroyed and recreated. In particular, if
2501 we end up deleting the only insn that used a subreg, we do not
2502 want to redo the mapping because this would invalidate everything
2505 bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2506 problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2507 problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2508 bitmap_initialize (&problem_data->hardware_regs_used,
2509 &problem_data->byte_lr_bitmaps);
2510 bitmap_initialize (&problem_data->invalidated_by_call,
2511 &problem_data->byte_lr_bitmaps);
2512 bitmap_initialize (&problem_data->needs_expansion,
2513 &problem_data->byte_lr_bitmaps);
2515 /* Discover which regno's use subregs, extracts or
2516 strict_low_parts. */
2520 FOR_BB_INSNS (bb, insn)
2524 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2525 df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2526 df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
2529 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2532 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2533 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2535 /* Allocate the slots for each regno. */
2536 for (regno = 0; regno < max_reg; regno++)
2539 problem_data->regno_start[regno] = index;
2540 if (bitmap_bit_p (&problem_data->needs_expansion, regno))
2541 len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2545 problem_data->regno_len[regno] = len;
2549 df_byte_lr_expand_bitmap (&problem_data->hardware_regs_used,
2550 &df->hardware_regs_used);
2551 df_byte_lr_expand_bitmap (&problem_data->invalidated_by_call,
2552 regs_invalidated_by_call_regset);
2554 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2556 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2559 bitmap_clear (&bb_info->def);
2560 bitmap_clear (&bb_info->use);
2564 bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool);
2565 df_byte_lr_set_bb_info (bb_index, bb_info);
2566 bitmap_initialize (&bb_info->use, &problem_data->byte_lr_bitmaps);
2567 bitmap_initialize (&bb_info->def, &problem_data->byte_lr_bitmaps);
2568 bitmap_initialize (&bb_info->in, &problem_data->byte_lr_bitmaps);
2569 bitmap_initialize (&bb_info->out, &problem_data->byte_lr_bitmaps);
2573 df_byte_lr->optional_p = true;
2577 /* Reset the global solution for recalculation. */
2580 df_byte_lr_reset (bitmap all_blocks)
2582 unsigned int bb_index;
2585 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2587 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2588 gcc_assert (bb_info);
2589 bitmap_clear (&bb_info->in);
2590 bitmap_clear (&bb_info->out);
2595 /* Compute local live register info for basic block BB. */
2598 df_byte_lr_bb_local_compute (unsigned int bb_index)
2600 struct df_byte_lr_problem_data *problem_data
2601 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2602 basic_block bb = BASIC_BLOCK (bb_index);
2603 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2608 /* Process the registers set in an exception handler. */
2609 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2611 df_ref def = *def_rec;
2612 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2614 unsigned int dregno = DF_REF_REGNO (def);
2615 unsigned int start = problem_data->regno_start[dregno];
2616 unsigned int len = problem_data->regno_len[dregno];
2617 bitmap_set_range (&bb_info->def, start, len);
2618 bitmap_clear_range (&bb_info->use, start, len);
2622 /* Process the hardware registers that are always live. */
2623 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2625 df_ref use = *use_rec;
2626 /* Add use to set of uses in this BB. */
2627 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2629 unsigned int uregno = DF_REF_REGNO (use);
2630 unsigned int start = problem_data->regno_start[uregno];
2631 unsigned int len = problem_data->regno_len[uregno];
2632 bitmap_set_range (&bb_info->use, start, len);
2636 FOR_BB_INSNS_REVERSE (bb, insn)
2638 unsigned int uid = INSN_UID (insn);
2643 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2645 df_ref def = *def_rec;
2646 /* If the def is to only part of the reg, it does
2647 not kill the other defs that reach here. */
2648 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2650 unsigned int dregno = DF_REF_REGNO (def);
2651 unsigned int start = problem_data->regno_start[dregno];
2652 unsigned int len = problem_data->regno_len[dregno];
2655 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2662 bitmap_set_range (&bb_info->def, start, len);
2663 bitmap_clear_range (&bb_info->use, start, len);
2668 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2670 df_ref use = *use_rec;
2671 unsigned int uregno = DF_REF_REGNO (use);
2672 unsigned int start = problem_data->regno_start[uregno];
2673 unsigned int len = problem_data->regno_len[uregno];
2676 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2681 /* Add use to set of uses in this BB. */
2683 bitmap_set_range (&bb_info->use, start, len);
2687 /* Process the registers set in an exception handler or the hard
2688 frame pointer if this block is the target of a non local
2690 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2692 df_ref def = *def_rec;
2693 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2695 unsigned int dregno = DF_REF_REGNO (def);
2696 unsigned int start = problem_data->regno_start[dregno];
2697 unsigned int len = problem_data->regno_len[dregno];
2698 bitmap_set_range (&bb_info->def, start, len);
2699 bitmap_clear_range (&bb_info->use, start, len);
2704 /* Process the uses that are live into an exception handler. */
2705 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2707 df_ref use = *use_rec;
2708 /* Add use to set of uses in this BB. */
2709 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2711 unsigned int uregno = DF_REF_REGNO (use);
2712 unsigned int start = problem_data->regno_start[uregno];
2713 unsigned int len = problem_data->regno_len[uregno];
2714 bitmap_set_range (&bb_info->use, start, len);
2721 /* Compute local live register info for each basic block within BLOCKS. */
2724 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2726 unsigned int bb_index;
2729 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2731 if (bb_index == EXIT_BLOCK)
2733 /* The exit block is special for this problem and its bits are
2734 computed from thin air. */
2735 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2736 df_byte_lr_expand_bitmap (&bb_info->use, df->exit_block_uses);
2739 df_byte_lr_bb_local_compute (bb_index);
2742 bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2746 /* Initialize the solution vectors. */
2749 df_byte_lr_init (bitmap all_blocks)
2751 unsigned int bb_index;
2754 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2756 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2757 bitmap_copy (&bb_info->in, &bb_info->use);
2758 bitmap_clear (&bb_info->out);
2763 /* Confluence function that processes infinite loops. This might be a
2764 noreturn function that throws. And even if it isn't, getting the
2765 unwind info right helps debugging. */
2767 df_byte_lr_confluence_0 (basic_block bb)
2769 struct df_byte_lr_problem_data *problem_data
2770 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2771 bitmap op1 = &df_byte_lr_get_bb_info (bb->index)->out;
2772 if (bb != EXIT_BLOCK_PTR)
2773 bitmap_copy (op1, &problem_data->hardware_regs_used);
2777 /* Confluence function that ignores fake edges. */
2780 df_byte_lr_confluence_n (edge e)
2782 struct df_byte_lr_problem_data *problem_data
2783 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2784 bitmap op1 = &df_byte_lr_get_bb_info (e->src->index)->out;
2785 bitmap op2 = &df_byte_lr_get_bb_info (e->dest->index)->in;
2787 /* Call-clobbered registers die across exception and call edges. */
2788 /* ??? Abnormal call edges ignored for the moment, as this gets
2789 confused by sibling call edges, which crashes reg-stack. */
2790 if (e->flags & EDGE_EH)
2791 bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);
2793 bitmap_ior_into (op1, op2);
2795 bitmap_ior_into (op1, &problem_data->hardware_regs_used);
2799 /* Transfer function. */
2802 df_byte_lr_transfer_function (int bb_index)
2804 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2805 bitmap in = &bb_info->in;
2806 bitmap out = &bb_info->out;
2807 bitmap use = &bb_info->use;
2808 bitmap def = &bb_info->def;
2810 return bitmap_ior_and_compl (in, use, out, def);
2814 /* Free all storage associated with the problem. */
2817 df_byte_lr_free (void)
2819 struct df_byte_lr_problem_data *problem_data
2820 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2823 if (df_byte_lr->block_info)
2825 free_alloc_pool (df_byte_lr->block_pool);
2826 df_byte_lr->block_info_size = 0;
2827 free (df_byte_lr->block_info);
2830 BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2831 bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2832 free (problem_data->regno_start);
2833 free (problem_data->regno_len);
2834 free (problem_data);
2839 /* Debugging info at top of bb. */
2842 df_byte_lr_top_dump (basic_block bb, FILE *file)
2844 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2848 fprintf (file, ";; blr in \t");
2849 df_print_byte_regset (file, &bb_info->in);
2850 fprintf (file, ";; blr use \t");
2851 df_print_byte_regset (file, &bb_info->use);
2852 fprintf (file, ";; blr def \t");
2853 df_print_byte_regset (file, &bb_info->def);
2857 /* Debugging info at bottom of bb. */
2860 df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2862 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2866 fprintf (file, ";; blr out \t");
2867 df_print_byte_regset (file, &bb_info->out);
2871 /* All of the information associated with every instance of the problem. */
2873 static struct df_problem problem_BYTE_LR =
2875 DF_BYTE_LR, /* Problem id. */
2876 DF_BACKWARD, /* Direction. */
2877 df_byte_lr_alloc, /* Allocate the problem specific data. */
2878 df_byte_lr_reset, /* Reset global information. */
2879 df_byte_lr_free_bb_info, /* Free basic block info. */
2880 df_byte_lr_local_compute, /* Local compute function. */
2881 df_byte_lr_init, /* Init the solution specific data. */
2882 df_worklist_dataflow, /* Worklist solver. */
2883 df_byte_lr_confluence_0, /* Confluence operator 0. */
2884 df_byte_lr_confluence_n, /* Confluence operator n. */
2885 df_byte_lr_transfer_function, /* Transfer function. */
2886 NULL, /* Finalize function. */
2887 df_byte_lr_free, /* Free all of the problem information. */
2888 df_byte_lr_free, /* Remove this problem from the stack of dataflow problems. */
2889 NULL, /* Debugging. */
2890 df_byte_lr_top_dump, /* Debugging start block. */
2891 df_byte_lr_bottom_dump, /* Debugging end block. */
2892 NULL, /* Incremental solution verify start. */
2893 NULL, /* Incremental solution verify end. */
2894 NULL, /* Dependent problem. */
2895 TV_DF_BYTE_LR, /* Timing variable. */
2896 false /* Reset blocks on dropping out of blocks_to_analyze. */
2900 /* Create a new DATAFLOW instance and add it to an existing instance
2901 of DF. The returned structure is what is used to get at the
2905 df_byte_lr_add_problem (void)
2907 df_add_problem (&problem_BYTE_LR);
2908 /* These will be initialized when df_scan_blocks processes each
2910 df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2914 /* Simulate the effects of the defs of INSN on LIVE. */
2917 df_byte_lr_simulate_defs (rtx insn, bitmap live)
2919 struct df_byte_lr_problem_data *problem_data
2920 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2922 unsigned int uid = INSN_UID (insn);
2924 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2926 df_ref def = *def_rec;
2928 /* If the def is to only part of the reg, it does
2929 not kill the other defs that reach here. */
2930 if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2932 unsigned int dregno = DF_REF_REGNO (def);
2933 unsigned int start = problem_data->regno_start[dregno];
2934 unsigned int len = problem_data->regno_len[dregno];
2937 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2944 bitmap_clear_range (live, start, len);
2950 /* Simulate the effects of the uses of INSN on LIVE. */
2953 df_byte_lr_simulate_uses (rtx insn, bitmap live)
2955 struct df_byte_lr_problem_data *problem_data
2956 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2958 unsigned int uid = INSN_UID (insn);
2960 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2962 df_ref use = *use_rec;
2963 unsigned int uregno = DF_REF_REGNO (use);
2964 unsigned int start = problem_data->regno_start[uregno];
2965 unsigned int len = problem_data->regno_len[uregno];
2969 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2975 /* Add use to set of uses in this BB. */
2977 bitmap_set_range (live, start, len);
2982 /* Apply the artificial uses and defs at the top of BB in a forwards
2986 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2988 struct df_byte_lr_problem_data *problem_data
2989 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2994 int bb_index = bb->index;
2997 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2999 df_ref use = *use_rec;
3000 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3002 unsigned int uregno = DF_REF_REGNO (use);
3003 unsigned int start = problem_data->regno_start[uregno];
3004 unsigned int len = problem_data->regno_len[uregno];
3005 bitmap_set_range (live, start, len);
3010 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3012 df_ref def = *def_rec;
3013 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3015 unsigned int dregno = DF_REF_REGNO (def);
3016 unsigned int start = problem_data->regno_start[dregno];
3017 unsigned int len = problem_data->regno_len[dregno];
3018 bitmap_clear_range (live, start, len);
3024 /* Apply the artificial uses and defs at the end of BB in a backwards
3028 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3030 struct df_byte_lr_problem_data *problem_data
3031 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
3034 int bb_index = bb->index;
3036 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3038 df_ref def = *def_rec;
3039 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3041 unsigned int dregno = DF_REF_REGNO (def);
3042 unsigned int start = problem_data->regno_start[dregno];
3043 unsigned int len = problem_data->regno_len[dregno];
3044 bitmap_clear_range (live, start, len);
3048 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3050 df_ref use = *use_rec;
3051 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3053 unsigned int uregno = DF_REF_REGNO (use);
3054 unsigned int start = problem_data->regno_start[uregno];
3055 unsigned int len = problem_data->regno_len[uregno];
3056 bitmap_set_range (live, start, len);
3063 /*----------------------------------------------------------------------------
3064 This problem computes REG_DEAD and REG_UNUSED notes.
3065 ----------------------------------------------------------------------------*/
3068 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3070 df_note->optional_p = true;
3073 #ifdef REG_DEAD_DEBUGGING
3075 df_print_note (const char *prefix, rtx insn, rtx note)
3079 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3080 print_rtl (dump_file, note);
3081 fprintf (dump_file, "\n");
3087 /* After reg-stack, the x86 floating point stack regs are difficult to
3088 analyze because of all of the pushes, pops and rotations. Thus, we
3089 just leave the notes alone. */
3093 df_ignore_stack_reg (int regno)
3095 return regstack_completed
3096 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3100 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3107 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3108 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3111 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3113 rtx *pprev = ®_NOTES (insn);
3120 switch (REG_NOTE_KIND (link))
3123 /* After reg-stack, we need to ignore any unused notes
3124 for the stack registers. */
3125 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3127 pprev = &XEXP (link, 1);
3132 rtx next = XEXP (link, 1);
3133 #ifdef REG_DEAD_DEBUGGING
3134 df_print_note ("deleting: ", insn, link);
3136 XEXP (link, 1) = dead;
3138 *pprev = link = next;
3143 /* After reg-stack, we need to ignore any unused notes
3144 for the stack registers. */
3145 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3147 pprev = &XEXP (link, 1);
3152 rtx next = XEXP (link, 1);
3153 #ifdef REG_DEAD_DEBUGGING
3154 df_print_note ("deleting: ", insn, link);
3156 XEXP (link, 1) = unused;
3158 *pprev = link = next;
3163 pprev = &XEXP (link, 1);
3169 *old_dead_notes = dead;
3170 *old_unused_notes = unused;
3174 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3175 list, otherwise create a new one. */
3178 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3183 gcc_assert (!DEBUG_INSN_P (insn));
3186 if (XEXP (curr, 0) == reg)
3189 XEXP (prev, 1) = XEXP (curr, 1);
3191 old = XEXP (curr, 1);
3192 XEXP (curr, 1) = REG_NOTES (insn);
3193 REG_NOTES (insn) = curr;
3199 curr = XEXP (curr, 1);
3202 /* Did not find the note. */
3203 add_reg_note (insn, note_type, reg);
3207 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3208 arguments. Return true if the register value described by MWS's
3209 mw_reg is known to be completely unused, and if mw_reg can therefore
3210 be used in a REG_UNUSED note. */
3213 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3214 bitmap live, bitmap artificial_uses)
3218 /* If MWS describes a partial reference, create REG_UNUSED notes for
3219 individual hard registers. */
3220 if (mws->flags & DF_REF_PARTIAL)
3223 /* Likewise if some part of the register is used. */
3224 for (r = mws->start_regno; r <= mws->end_regno; r++)
3225 if (bitmap_bit_p (live, r)
3226 || bitmap_bit_p (artificial_uses, r))
3229 gcc_assert (REG_P (mws->mw_reg));
3233 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3234 based on the bits in LIVE. Do not generate notes for registers in
3235 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3236 not generated if the reg is both read and written by the
3241 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3242 bitmap live, bitmap do_not_gen,
3243 bitmap artificial_uses)
3247 #ifdef REG_DEAD_DEBUGGING
3249 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3250 mws->start_regno, mws->end_regno);
3253 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3255 unsigned int regno = mws->start_regno;
3256 old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3258 #ifdef REG_DEAD_DEBUGGING
3259 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3261 bitmap_set_bit (do_not_gen, regno);
3262 /* Only do this if the value is totally dead. */
3265 for (r = mws->start_regno; r <= mws->end_regno; r++)
3267 if (!bitmap_bit_p (live, r)
3268 && !bitmap_bit_p (artificial_uses, r))
3270 old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3271 #ifdef REG_DEAD_DEBUGGING
3272 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3275 bitmap_set_bit (do_not_gen, r);
3281 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3282 arguments. Return true if the register value described by MWS's
3283 mw_reg is known to be completely dead, and if mw_reg can therefore
3284 be used in a REG_DEAD note. */
3287 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3288 bitmap live, bitmap artificial_uses,
3293 /* If MWS describes a partial reference, create REG_DEAD notes for
3294 individual hard registers. */
3295 if (mws->flags & DF_REF_PARTIAL)
3298 /* Likewise if some part of the register is not dead. */
3299 for (r = mws->start_regno; r <= mws->end_regno; r++)
3300 if (bitmap_bit_p (live, r)
3301 || bitmap_bit_p (artificial_uses, r)
3302 || bitmap_bit_p (do_not_gen, r))
3305 gcc_assert (REG_P (mws->mw_reg));
3309 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3310 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3311 from being set if the instruction both reads and writes the
3315 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3316 bitmap live, bitmap do_not_gen,
3317 bitmap artificial_uses, bool *added_notes_p)
3320 bool is_debug = *added_notes_p;
3322 *added_notes_p = false;
3324 #ifdef REG_DEAD_DEBUGGING
3327 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3328 mws->start_regno, mws->end_regno);
3329 df_print_regset (dump_file, do_not_gen);
3330 fprintf (dump_file, " live =");
3331 df_print_regset (dump_file, live);
3332 fprintf (dump_file, " artificial uses =");
3333 df_print_regset (dump_file, artificial_uses);
3337 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3339 /* Add a dead note for the entire multi word register. */
3342 *added_notes_p = true;
3345 old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3346 #ifdef REG_DEAD_DEBUGGING
3347 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3352 for (r = mws->start_regno; r <= mws->end_regno; r++)
3353 if (!bitmap_bit_p (live, r)
3354 && !bitmap_bit_p (artificial_uses, r)
3355 && !bitmap_bit_p (do_not_gen, r))
3359 *added_notes_p = true;
3362 old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3363 #ifdef REG_DEAD_DEBUGGING
3364 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3372 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3373 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3376 df_create_unused_note (rtx insn, rtx old, df_ref def,
3377 bitmap live, bitmap artificial_uses)
3379 unsigned int dregno = DF_REF_REGNO (def);
3381 #ifdef REG_DEAD_DEBUGGING
3384 fprintf (dump_file, " regular looking at def ");
3385 df_ref_debug (def, dump_file);
3389 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3390 || bitmap_bit_p (live, dregno)
3391 || bitmap_bit_p (artificial_uses, dregno)
3392 || df_ignore_stack_reg (dregno)))
3394 rtx reg = (DF_REF_LOC (def))
3395 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3396 old = df_set_note (REG_UNUSED, insn, old, reg);
3397 #ifdef REG_DEAD_DEBUGGING
3398 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3405 /* Node of a linked list of uses of dead REGs in debug insns. */
3406 struct dead_debug_use
3409 struct dead_debug_use *next;
3412 /* Linked list of the above, with a bitmap of the REGs in the
3416 struct dead_debug_use *head;
3421 /* Initialize DEBUG to an empty list, and clear USED, if given. */
3423 dead_debug_init (struct dead_debug *debug, bitmap used)
3427 debug->to_rescan = NULL;
3429 bitmap_clear (used);
3432 /* Reset all debug insns with pending uses. Release the bitmap in it,
3433 unless it is USED. USED must be the same bitmap passed to
3436 dead_debug_finish (struct dead_debug *debug, bitmap used)
3438 struct dead_debug_use *head;
3441 if (debug->used != used)
3442 BITMAP_FREE (debug->used);
3444 while ((head = debug->head))
3446 insn = DF_REF_INSN (head->use);
3447 if (!head->next || DF_REF_INSN (head->next->use) != insn)
3449 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3450 df_insn_rescan_debug_internal (insn);
3451 if (debug->to_rescan)
3452 bitmap_clear_bit (debug->to_rescan, INSN_UID (insn));
3454 debug->head = head->next;
3458 if (debug->to_rescan)
3463 EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi)
3465 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
3467 df_insn_rescan (insn_info->insn);
3469 BITMAP_FREE (debug->to_rescan);
3473 /* Add USE to DEBUG. It must be a dead reference to UREGNO in a debug
3474 insn. Create a bitmap for DEBUG as needed. */
3476 dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno)
3478 struct dead_debug_use *newddu = XNEW (struct dead_debug_use);
3481 newddu->next = debug->head;
3482 debug->head = newddu;
3485 debug->used = BITMAP_ALLOC (NULL);
3487 bitmap_set_bit (debug->used, uregno);
3490 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3491 before INSN that binds the REG to a debug temp, and replace all
3492 uses of UREGNO in DEBUG with uses of the debug temp. INSN must be
3493 the insn where UREGNO dies. */
3495 dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno,
3498 struct dead_debug_use **tailp = &debug->head;
3499 struct dead_debug_use *cur;
3500 struct dead_debug_use *uses = NULL;
3501 struct dead_debug_use **usesp = &uses;
3506 if (!debug->used || !bitmap_clear_bit (debug->used, uregno))
3509 /* Move all uses of uregno from debug->head to uses, setting mode to
3510 the widest referenced mode. */
3511 while ((cur = *tailp))
3513 if (DF_REF_REGNO (cur->use) == uregno)
3520 || (GET_MODE_BITSIZE (GET_MODE (reg))
3521 < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use)))))
3522 reg = *DF_REF_REAL_LOC (cur->use);
3525 tailp = &(*tailp)->next;
3530 /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL). */
3531 dval = make_debug_expr_from_rtl (reg);
3533 /* Emit a debug bind insn before the insn in which reg dies. */
3534 bind = gen_rtx_VAR_LOCATION (GET_MODE (reg),
3535 DEBUG_EXPR_TREE_DECL (dval), reg,
3536 VAR_INIT_STATUS_INITIALIZED);
3538 bind = emit_debug_insn_before (bind, insn);
3539 df_insn_rescan (bind);
3541 /* Adjust all uses. */
3542 while ((cur = uses))
3544 if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg))
3545 *DF_REF_REAL_LOC (cur->use) = dval;
3547 *DF_REF_REAL_LOC (cur->use)
3548 = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval);
3549 /* ??? Should we simplify subreg of subreg? */
3550 if (debug->to_rescan == NULL)
3551 debug->to_rescan = BITMAP_ALLOC (NULL);
3552 bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use)));
3558 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3559 info: lifetime, bb, and number of defs and uses for basic block
3560 BB. The three bitvectors are scratch regs used here. */
3563 df_note_bb_compute (unsigned int bb_index,
3564 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3566 basic_block bb = BASIC_BLOCK (bb_index);
3570 struct dead_debug debug;
3572 dead_debug_init (&debug, NULL);
3574 bitmap_copy (live, df_get_live_out (bb));
3575 bitmap_clear (artificial_uses);
3577 #ifdef REG_DEAD_DEBUGGING
3580 fprintf (dump_file, "live at bottom ");
3581 df_print_regset (dump_file, live);
3585 /* Process the artificial defs and uses at the bottom of the block
3586 to begin processing. */
3587 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3589 df_ref def = *def_rec;
3590 #ifdef REG_DEAD_DEBUGGING
3592 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3595 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3596 bitmap_clear_bit (live, DF_REF_REGNO (def));
3599 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3601 df_ref use = *use_rec;
3602 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3604 unsigned int regno = DF_REF_REGNO (use);
3605 bitmap_set_bit (live, regno);
3607 /* Notes are not generated for any of the artificial registers
3608 at the bottom of the block. */
3609 bitmap_set_bit (artificial_uses, regno);
3613 #ifdef REG_DEAD_DEBUGGING
3616 fprintf (dump_file, "live before artificials out ");
3617 df_print_regset (dump_file, live);
3621 FOR_BB_INSNS_REVERSE (bb, insn)
3623 unsigned int uid = INSN_UID (insn);
3624 struct df_mw_hardreg **mws_rec;
3626 rtx old_unused_notes;
3632 debug_insn = DEBUG_INSN_P (insn);
3634 bitmap_clear (do_not_gen);
3635 df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3637 /* Process the defs. */
3640 #ifdef REG_DEAD_DEBUGGING
3643 fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
3644 df_print_regset (dump_file, live);
3647 /* We only care about real sets for calls. Clobbers cannot
3648 be depended on to really die. */
3649 mws_rec = DF_INSN_UID_MWS (uid);
3652 struct df_mw_hardreg *mws = *mws_rec;
3653 if ((DF_MWS_REG_DEF_P (mws))
3654 && !df_ignore_stack_reg (mws->start_regno))
3656 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3657 mws, live, do_not_gen,
3662 /* All of the defs except the return value are some sort of
3663 clobber. This code is for the return. */
3664 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3666 df_ref def = *def_rec;
3667 unsigned int dregno = DF_REF_REGNO (def);
3668 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3671 = df_create_unused_note (insn, old_unused_notes,
3672 def, live, artificial_uses);
3673 bitmap_set_bit (do_not_gen, dregno);
3676 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3677 bitmap_clear_bit (live, dregno);
3683 mws_rec = DF_INSN_UID_MWS (uid);
3686 struct df_mw_hardreg *mws = *mws_rec;
3687 if (DF_MWS_REG_DEF_P (mws))
3689 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3690 mws, live, do_not_gen,
3695 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3697 df_ref def = *def_rec;
3698 unsigned int dregno = DF_REF_REGNO (def);
3700 = df_create_unused_note (insn, old_unused_notes,
3701 def, live, artificial_uses);
3703 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3704 bitmap_set_bit (do_not_gen, dregno);
3706 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3707 bitmap_clear_bit (live, dregno);
3711 /* Process the uses. */
3712 mws_rec = DF_INSN_UID_MWS (uid);
3715 struct df_mw_hardreg *mws = *mws_rec;
3716 if ((DF_MWS_REG_DEF_P (mws))
3717 && !df_ignore_stack_reg (mws->start_regno))
3719 bool really_add_notes = debug_insn != 0;
3722 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3723 mws, live, do_not_gen,
3727 if (really_add_notes)
3733 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3735 df_ref use = *use_rec;
3736 unsigned int uregno = DF_REF_REGNO (use);
3738 #ifdef REG_DEAD_DEBUGGING
3739 if (dump_file && !debug_insn)
3741 fprintf (dump_file, " regular looking at use ");
3742 df_ref_debug (use, dump_file);
3745 if (!bitmap_bit_p (live, uregno))
3751 dead_debug_add (&debug, use, uregno);
3757 dead_debug_insert_before (&debug, uregno, insn);
3759 if ( (!(DF_REF_FLAGS (use)
3760 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3761 && (!bitmap_bit_p (do_not_gen, uregno))
3762 && (!bitmap_bit_p (artificial_uses, uregno))
3763 && (!df_ignore_stack_reg (uregno)))
3765 rtx reg = (DF_REF_LOC (use))
3766 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3767 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3769 #ifdef REG_DEAD_DEBUGGING
3770 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3773 /* This register is now live. */
3774 bitmap_set_bit (live, uregno);
3778 while (old_unused_notes)
3780 rtx next = XEXP (old_unused_notes, 1);
3781 free_EXPR_LIST_node (old_unused_notes);
3782 old_unused_notes = next;
3784 while (old_dead_notes)
3786 rtx next = XEXP (old_dead_notes, 1);
3787 free_EXPR_LIST_node (old_dead_notes);
3788 old_dead_notes = next;
3791 if (debug_insn == -1)
3793 /* ??? We could probably do better here, replacing dead
3794 registers with their definitions. */
3795 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3796 df_insn_rescan_debug_internal (insn);
3800 dead_debug_finish (&debug, NULL);
3804 /* Compute register info: lifetime, bb, and number of defs and uses. */
3806 df_note_compute (bitmap all_blocks)
3808 unsigned int bb_index;
3810 bitmap_head live, do_not_gen, artificial_uses;
3812 bitmap_initialize (&live, &df_bitmap_obstack);
3813 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3814 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3816 #ifdef REG_DEAD_DEBUGGING
3818 print_rtl_with_bb (dump_file, get_insns());
3821 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3823 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3826 bitmap_clear (&live);
3827 bitmap_clear (&do_not_gen);
3828 bitmap_clear (&artificial_uses);
3832 /* Free all storage associated with the problem. */
3841 /* All of the information associated every instance of the problem. */
3843 static struct df_problem problem_NOTE =
3845 DF_NOTE, /* Problem id. */
3846 DF_NONE, /* Direction. */
3847 df_note_alloc, /* Allocate the problem specific data. */
3848 NULL, /* Reset global information. */
3849 NULL, /* Free basic block info. */
3850 df_note_compute, /* Local compute function. */
3851 NULL, /* Init the solution specific data. */
3852 NULL, /* Iterative solver. */
3853 NULL, /* Confluence operator 0. */
3854 NULL, /* Confluence operator n. */
3855 NULL, /* Transfer function. */
3856 NULL, /* Finalize function. */
3857 df_note_free, /* Free all of the problem information. */
3858 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3859 NULL, /* Debugging. */
3860 NULL, /* Debugging start block. */
3861 NULL, /* Debugging end block. */
3862 NULL, /* Incremental solution verify start. */
3863 NULL, /* Incremental solution verify end. */
3864 &problem_LR, /* Dependent problem. */
3865 TV_DF_NOTE, /* Timing variable. */
3866 false /* Reset blocks on dropping out of blocks_to_analyze. */
3870 /* Create a new DATAFLOW instance and add it to an existing instance
3871 of DF. The returned structure is what is used to get at the
3875 df_note_add_problem (void)
3877 df_add_problem (&problem_NOTE);
3883 /*----------------------------------------------------------------------------
3884 Functions for simulating the effects of single insns.
3886 You can either simulate in the forwards direction, starting from
3887 the top of a block or the backwards direction from the end of the
3888 block. If you go backwards, defs are examined first to clear bits,
3889 then uses are examined to set bits. If you go forwards, defs are
3890 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3891 are examined to clear bits. In either case, the result of examining
3892 a def can be undone (respectively by a use or a REG_UNUSED note).
3894 If you start at the top of the block, use one of DF_LIVE_IN or
3895 DF_LR_IN. If you start at the bottom of the block use one of
3896 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3897 THEY WILL BE DESTROYED.
3898 ----------------------------------------------------------------------------*/
3901 /* Find the set of DEFs for INSN. */
3904 df_simulate_find_defs (rtx insn, bitmap defs)
3907 unsigned int uid = INSN_UID (insn);
3909 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3911 df_ref def = *def_rec;
3912 bitmap_set_bit (defs, DF_REF_REGNO (def));
3916 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3919 df_simulate_find_noclobber_defs (rtx insn, bitmap defs)
3922 unsigned int uid = INSN_UID (insn);
3924 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3926 df_ref def = *def_rec;
3927 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3928 bitmap_set_bit (defs, DF_REF_REGNO (def));
3933 /* Simulate the effects of the defs of INSN on LIVE. */
3936 df_simulate_defs (rtx insn, bitmap live)
3939 unsigned int uid = INSN_UID (insn);
3941 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3943 df_ref def = *def_rec;
3944 unsigned int dregno = DF_REF_REGNO (def);
3946 /* If the def is to only part of the reg, it does
3947 not kill the other defs that reach here. */
3948 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3949 bitmap_clear_bit (live, dregno);
3954 /* Simulate the effects of the uses of INSN on LIVE. */
3957 df_simulate_uses (rtx insn, bitmap live)
3960 unsigned int uid = INSN_UID (insn);
3962 if (DEBUG_INSN_P (insn))
3965 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3967 df_ref use = *use_rec;
3968 /* Add use to set of uses in this BB. */
3969 bitmap_set_bit (live, DF_REF_REGNO (use));
3974 /* Add back the always live regs in BB to LIVE. */
3977 df_simulate_fixup_sets (basic_block bb, bitmap live)
3979 /* These regs are considered always live so if they end up dying
3980 because of some def, we need to bring the back again. */
3981 if (bb_has_eh_pred (bb))
3982 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3984 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3988 /*----------------------------------------------------------------------------
3989 The following three functions are used only for BACKWARDS scanning:
3990 i.e. they process the defs before the uses.
3992 df_simulate_initialize_backwards should be called first with a
3993 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3994 df_simulate_one_insn_backwards should be called for each insn in
3995 the block, starting with the last one. Finally,
3996 df_simulate_finalize_backwards can be called to get a new value
3997 of the sets at the top of the block (this is rarely used).
3998 ----------------------------------------------------------------------------*/
4000 /* Apply the artificial uses and defs at the end of BB in a backwards
4004 df_simulate_initialize_backwards (basic_block bb, bitmap live)
4008 int bb_index = bb->index;
4010 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4012 df_ref def = *def_rec;
4013 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
4014 bitmap_clear_bit (live, DF_REF_REGNO (def));
4017 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4019 df_ref use = *use_rec;
4020 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
4021 bitmap_set_bit (live, DF_REF_REGNO (use));
4026 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
4029 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
4031 if (!NONDEBUG_INSN_P (insn))
4034 df_simulate_defs (insn, live);
4035 df_simulate_uses (insn, live);
4036 df_simulate_fixup_sets (bb, live);
4040 /* Apply the artificial uses and defs at the top of BB in a backwards
4044 df_simulate_finalize_backwards (basic_block bb, bitmap live)
4050 int bb_index = bb->index;
4052 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4054 df_ref def = *def_rec;
4055 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4056 bitmap_clear_bit (live, DF_REF_REGNO (def));
4060 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4062 df_ref use = *use_rec;
4063 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4064 bitmap_set_bit (live, DF_REF_REGNO (use));
4068 /*----------------------------------------------------------------------------
4069 The following three functions are used only for FORWARDS scanning:
4070 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
4071 Thus it is important to add the DF_NOTES problem to the stack of
4072 problems computed before using these functions.
4074 df_simulate_initialize_forwards should be called first with a
4075 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
4076 df_simulate_one_insn_forwards should be called for each insn in
4077 the block, starting with the first one.
4078 ----------------------------------------------------------------------------*/
4080 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
4081 DF_LR_IN for basic block BB, for forward scanning by marking artificial
4085 df_simulate_initialize_forwards (basic_block bb, bitmap live)
4088 int bb_index = bb->index;
4090 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4092 df_ref def = *def_rec;
4093 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4094 bitmap_set_bit (live, DF_REF_REGNO (def));
4098 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4101 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
4104 if (! INSN_P (insn))
4107 /* Make sure that DF_NOTE really is an active df problem. */
4108 gcc_assert (df_note);
4110 /* Note that this is the opposite as how the problem is defined, because
4111 in the LR problem defs _kill_ liveness. However, they do so backwards,
4112 while here the scan is performed forwards! So, first assume that the
4113 def is live, and if this is not true REG_UNUSED notes will rectify the
4115 df_simulate_find_noclobber_defs (insn, live);
4117 /* Clear all of the registers that go dead. */
4118 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4120 switch (REG_NOTE_KIND (link))
4125 rtx reg = XEXP (link, 0);
4126 int regno = REGNO (reg);
4127 if (regno < FIRST_PSEUDO_REGISTER)
4129 int n = hard_regno_nregs[regno][GET_MODE (reg)];
4131 bitmap_clear_bit (live, regno + n);
4134 bitmap_clear_bit (live, regno);
4141 df_simulate_fixup_sets (bb, live);
4146 /*----------------------------------------------------------------------------
4147 MULTIPLE DEFINITIONS
4149 Find the locations in the function reached by multiple definition sites
4150 for a live pseudo. In and out bitvectors are built for each basic
4151 block. They are restricted for efficiency to live registers.
4153 The gen and kill sets for the problem are obvious. Together they
4154 include all defined registers in a basic block; the gen set includes
4155 registers where a partial or conditional or may-clobber definition is
4156 last in the BB, while the kill set includes registers with a complete
4157 definition coming last. However, the computation of the dataflow
4158 itself is interesting.
4160 The idea behind it comes from SSA form's iterated dominance frontier
4161 criterion for inserting PHI functions. Just like in that case, we can use
4162 the dominance frontier to find places where multiple definitions meet;
4163 a register X defined in a basic block BB1 has multiple definitions in
4164 basic blocks in BB1's dominance frontier.
4166 So, the in-set of a basic block BB2 is not just the union of the
4167 out-sets of BB2's predecessors, but includes some more bits that come
4168 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4169 the previous paragraph). I called this set the init-set of BB2.
4171 (Note: I actually use the kill-set only to build the init-set.
4172 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4174 For example, if you have
4178 if <...> goto BB2 else goto BB3;
4186 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4187 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4188 not need to iterate the dominance frontier, because we do not insert
4189 anything like PHI functions there! Instead, dataflow will take care of
4190 propagating the information to BB3's successors.
4191 ---------------------------------------------------------------------------*/
4193 /* Scratch var used by transfer functions. This is used to do md analysis
4194 only for live registers. */
4195 static bitmap_head df_md_scratch;
4197 /* Set basic block info. */
4200 df_md_set_bb_info (unsigned int index,
4201 struct df_md_bb_info *bb_info)
4204 gcc_assert (index < df_md->block_info_size);
4205 df_md->block_info[index] = bb_info;
4210 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4213 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4216 bitmap_clear (&bb_info->kill);
4217 bitmap_clear (&bb_info->gen);
4218 bitmap_clear (&bb_info->init);
4219 bitmap_clear (&bb_info->in);
4220 bitmap_clear (&bb_info->out);
4221 pool_free (df_md->block_pool, bb_info);
4226 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4227 not touched unless the block is new. */
4230 df_md_alloc (bitmap all_blocks)
4232 unsigned int bb_index;
4235 if (!df_md->block_pool)
4236 df_md->block_pool = create_alloc_pool ("df_md_block pool",
4237 sizeof (struct df_md_bb_info), 50);
4239 df_grow_bb_info (df_md);
4240 bitmap_initialize (&df_md_scratch, &bitmap_default_obstack);
4242 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4244 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4247 bitmap_clear (&bb_info->init);
4248 bitmap_clear (&bb_info->gen);
4249 bitmap_clear (&bb_info->kill);
4250 bitmap_clear (&bb_info->in);
4251 bitmap_clear (&bb_info->out);
4255 bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
4256 df_md_set_bb_info (bb_index, bb_info);
4257 bitmap_initialize (&bb_info->init, &bitmap_default_obstack);
4258 bitmap_initialize (&bb_info->gen, &bitmap_default_obstack);
4259 bitmap_initialize (&bb_info->kill, &bitmap_default_obstack);
4260 bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
4261 bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
4265 df_md->optional_p = true;
4268 /* Add the effect of the top artificial defs of BB to the multiple definitions
4272 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4274 int bb_index = bb->index;
4276 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4278 df_ref def = *def_rec;
4279 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4281 unsigned int dregno = DF_REF_REGNO (def);
4282 if (DF_REF_FLAGS (def)
4283 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4284 bitmap_set_bit (local_md, dregno);
4286 bitmap_clear_bit (local_md, dregno);
4292 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4296 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
4299 unsigned uid = INSN_UID (insn);
4302 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4304 df_ref def = *def_rec;
4305 unsigned int dregno = DF_REF_REGNO (def);
4306 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4307 || (dregno >= FIRST_PSEUDO_REGISTER))
4309 if (DF_REF_FLAGS (def)
4310 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4311 bitmap_set_bit (local_md, DF_REF_ID (def));
4313 bitmap_clear_bit (local_md, DF_REF_ID (def));
4319 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4324 bitmap_clear (&seen_in_insn);
4326 while ((def = *def_rec++) != NULL)
4328 unsigned int dregno = DF_REF_REGNO (def);
4329 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4330 || (dregno >= FIRST_PSEUDO_REGISTER))
4331 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4333 if (!bitmap_bit_p (&seen_in_insn, dregno))
4335 if (DF_REF_FLAGS (def)
4336 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4338 bitmap_set_bit (&bb_info->gen, dregno);
4339 bitmap_clear_bit (&bb_info->kill, dregno);
4343 /* When we find a clobber and a regular def,
4344 make sure the regular def wins. */
4345 bitmap_set_bit (&seen_in_insn, dregno);
4346 bitmap_set_bit (&bb_info->kill, dregno);
4347 bitmap_clear_bit (&bb_info->gen, dregno);
4355 /* Compute local multiple def info for basic block BB. */
4358 df_md_bb_local_compute (unsigned int bb_index)
4360 basic_block bb = BASIC_BLOCK (bb_index);
4361 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4364 /* Artificials are only hard regs. */
4365 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4366 df_md_bb_local_compute_process_def (bb_info,
4367 df_get_artificial_defs (bb_index),
4370 FOR_BB_INSNS (bb, insn)
4372 unsigned int uid = INSN_UID (insn);
4376 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4379 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4380 df_md_bb_local_compute_process_def (bb_info,
4381 df_get_artificial_defs (bb_index),
4385 /* Compute local reaching def info for each basic block within BLOCKS. */
4388 df_md_local_compute (bitmap all_blocks)
4390 unsigned int bb_index, df_bb_index;
4391 bitmap_iterator bi1, bi2;
4393 bitmap_head *frontiers;
4395 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4397 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4399 df_md_bb_local_compute (bb_index);
4402 bitmap_clear (&seen_in_insn);
4404 frontiers = XNEWVEC (bitmap_head, last_basic_block);
4406 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4408 compute_dominance_frontiers (frontiers);
4410 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4411 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4413 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4414 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4416 basic_block bb = BASIC_BLOCK (df_bb_index);
4417 if (bitmap_bit_p (all_blocks, df_bb_index))
4418 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4419 df_get_live_in (bb));
4424 bitmap_clear (&frontiers[bb->index]);
4429 /* Reset the global solution for recalculation. */
4432 df_md_reset (bitmap all_blocks)
4434 unsigned int bb_index;
4437 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4439 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4440 gcc_assert (bb_info);
4441 bitmap_clear (&bb_info->in);
4442 bitmap_clear (&bb_info->out);
4447 df_md_transfer_function (int bb_index)
4449 basic_block bb = BASIC_BLOCK (bb_index);
4450 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4451 bitmap in = &bb_info->in;
4452 bitmap out = &bb_info->out;
4453 bitmap gen = &bb_info->gen;
4454 bitmap kill = &bb_info->kill;
4456 /* We need to use a scratch set here so that the value returned from this
4457 function invocation properly reflects whether the sets changed in a
4458 significant way; i.e. not just because the live set was anded in. */
4459 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4461 /* Multiple definitions of a register are not relevant if it is not
4462 live. Thus we trim the result to the places where it is live. */
4463 bitmap_and_into (in, df_get_live_in (bb));
4465 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4468 /* Initialize the solution bit vectors for problem. */
4471 df_md_init (bitmap all_blocks)
4473 unsigned int bb_index;
4476 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4478 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4480 bitmap_copy (&bb_info->in, &bb_info->init);
4481 df_md_transfer_function (bb_index);
4486 df_md_confluence_0 (basic_block bb)
4488 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4489 bitmap_copy (&bb_info->in, &bb_info->init);
4492 /* In of target gets or of out of source. */
4495 df_md_confluence_n (edge e)
4497 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4498 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4500 if (e->flags & EDGE_FAKE)
4503 if (e->flags & EDGE_EH)
4504 bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
4506 bitmap_ior_into (op1, op2);
4509 /* Free all storage associated with the problem. */
4515 for (i = 0; i < df_md->block_info_size; i++)
4517 struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
4520 bitmap_clear (&bb_info->kill);
4521 bitmap_clear (&bb_info->gen);
4522 bitmap_clear (&bb_info->init);
4523 bitmap_clear (&bb_info->in);
4524 bitmap_clear (&bb_info->out);
4528 bitmap_clear (&df_md_scratch);
4529 free_alloc_pool (df_md->block_pool);
4531 df_md->block_info_size = 0;
4532 free (df_md->block_info);
4537 /* Debugging info at top of bb. */
4540 df_md_top_dump (basic_block bb, FILE *file)
4542 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4546 fprintf (file, ";; md in \t");
4547 df_print_regset (file, &bb_info->in);
4548 fprintf (file, ";; md init \t");
4549 df_print_regset (file, &bb_info->init);
4550 fprintf (file, ";; md gen \t");
4551 df_print_regset (file, &bb_info->gen);
4552 fprintf (file, ";; md kill \t");
4553 df_print_regset (file, &bb_info->kill);
4556 /* Debugging info at bottom of bb. */
4559 df_md_bottom_dump (basic_block bb, FILE *file)
4561 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4565 fprintf (file, ";; md out \t");
4566 df_print_regset (file, &bb_info->out);
4569 static struct df_problem problem_MD =
4571 DF_MD, /* Problem id. */
4572 DF_FORWARD, /* Direction. */
4573 df_md_alloc, /* Allocate the problem specific data. */
4574 df_md_reset, /* Reset global information. */
4575 df_md_free_bb_info, /* Free basic block info. */
4576 df_md_local_compute, /* Local compute function. */
4577 df_md_init, /* Init the solution specific data. */
4578 df_worklist_dataflow, /* Worklist solver. */
4579 df_md_confluence_0, /* Confluence operator 0. */
4580 df_md_confluence_n, /* Confluence operator n. */
4581 df_md_transfer_function, /* Transfer function. */
4582 NULL, /* Finalize function. */
4583 df_md_free, /* Free all of the problem information. */
4584 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4585 NULL, /* Debugging. */
4586 df_md_top_dump, /* Debugging start block. */
4587 df_md_bottom_dump, /* Debugging end block. */
4588 NULL, /* Incremental solution verify start. */
4589 NULL, /* Incremental solution verify end. */
4590 NULL, /* Dependent problem. */
4591 TV_DF_MD, /* Timing variable. */
4592 false /* Reset blocks on dropping out of blocks_to_analyze. */
4595 /* Create a new MD instance and add it to the existing instance
4599 df_md_add_problem (void)
4601 df_add_problem (&problem_MD);