1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008 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 seen_in_block = NULL;
58 static bitmap seen_in_insn = NULL;
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 = xrealloc (dflow->block_info,
113 new_size *sizeof (void*));
114 memset (dflow->block_info + dflow->block_info_size, 0,
115 (new_size - dflow->block_info_size) *sizeof (void *));
116 dflow->block_info_size = new_size;
120 /* Dump a def-use or use-def chain for REF to FILE. */
123 df_chain_dump (struct df_link *link, FILE *file)
125 fprintf (file, "{ ");
126 for (; link; link = link->next)
128 fprintf (file, "%c%d(bb %d insn %d) ",
129 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
130 DF_REF_ID (link->ref),
131 DF_REF_BBNO (link->ref),
132 DF_REF_INSN_INFO (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
138 /* Print some basic block info as part of df_dump. */
141 df_print_bb_index (basic_block bb, FILE *file)
146 fprintf (file, "\n( ");
147 FOR_EACH_EDGE (e, ei, bb->preds)
149 basic_block pred = e->src;
150 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
152 fprintf (file, ")->[%d]->( ", bb->index);
153 FOR_EACH_EDGE (e, ei, bb->succs)
155 basic_block succ = e->dest;
156 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
158 fprintf (file, ")\n");
163 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
169 seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
170 seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
177 BITMAP_FREE (seen_in_block);
178 BITMAP_FREE (seen_in_insn);
183 /*----------------------------------------------------------------------------
186 Find the locations in the function where each definition site for a
187 pseudo reaches. In and out bitvectors are built for each basic
188 block. The id field in the ref is used to index into these sets.
189 See df.h for details.
190 ----------------------------------------------------------------------------*/
192 /* This problem plays a large number of games for the sake of
195 1) The order of the bits in the bitvectors. After the scanning
196 phase, all of the defs are sorted. All of the defs for the reg 0
197 are first, followed by all defs for reg 1 and so on.
199 2) There are two kill sets, one if the number of defs is less or
200 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
203 <= : Data is built directly in the kill set.
205 > : One level of indirection is used to keep from generating long
206 strings of 1 bits in the kill sets. Bitvectors that are indexed
207 by the regnum are used to represent that there is a killing def
208 for the register. The confluence and transfer functions use
209 these along with the bitmap_clear_range call to remove ranges of
210 bits without actually generating a knockout vector.
212 The kill and sparse_kill and the dense_invalidated_by_call and
213 sparse_invalidated_by_call both play this game. */
215 /* Private data used to compute the solution for this problem. These
216 data structures are not accessible outside of this module. */
217 struct df_rd_problem_data
219 /* The set of defs to regs invalidated by call. */
220 bitmap sparse_invalidated_by_call;
221 /* The set of defs to regs invalidate by call for rd. */
222 bitmap dense_invalidated_by_call;
223 /* An obstack for the bitmaps we need for this problem. */
224 bitmap_obstack rd_bitmaps;
227 /* Set basic block info. */
230 df_rd_set_bb_info (unsigned int index,
231 struct df_rd_bb_info *bb_info)
234 gcc_assert (index < df_rd->block_info_size);
235 df_rd->block_info[index] = bb_info;
239 /* Free basic block info. */
242 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
245 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
248 BITMAP_FREE (bb_info->kill);
249 BITMAP_FREE (bb_info->sparse_kill);
250 BITMAP_FREE (bb_info->gen);
251 BITMAP_FREE (bb_info->in);
252 BITMAP_FREE (bb_info->out);
253 pool_free (df_rd->block_pool, bb_info);
258 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
259 not touched unless the block is new. */
262 df_rd_alloc (bitmap all_blocks)
264 unsigned int bb_index;
266 struct df_rd_problem_data *problem_data;
268 if (!df_rd->block_pool)
269 df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
270 sizeof (struct df_rd_bb_info), 50);
272 if (df_rd->problem_data)
274 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
275 bitmap_clear (problem_data->sparse_invalidated_by_call);
276 bitmap_clear (problem_data->dense_invalidated_by_call);
280 problem_data = XNEW (struct df_rd_problem_data);
281 df_rd->problem_data = problem_data;
283 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
284 problem_data->sparse_invalidated_by_call
285 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
286 problem_data->dense_invalidated_by_call
287 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
290 df_grow_bb_info (df_rd);
292 /* Because of the clustering of all use sites for the same pseudo,
293 we have to process all of the blocks before doing the
296 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
298 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
301 bitmap_clear (bb_info->kill);
302 bitmap_clear (bb_info->sparse_kill);
303 bitmap_clear (bb_info->gen);
307 bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
308 df_rd_set_bb_info (bb_index, bb_info);
309 bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
310 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
311 bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
312 bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
313 bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
316 df_rd->optional_p = true;
320 /* Process a list of DEFs for df_rd_bb_local_compute. */
323 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
324 struct df_ref **def_rec,
325 enum df_ref_flags top_flag)
329 struct df_ref *def = *def_rec;
330 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
332 unsigned int regno = DF_REF_REGNO (def);
333 unsigned int begin = DF_DEFS_BEGIN (regno);
334 unsigned int n_defs = DF_DEFS_COUNT (regno);
336 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
337 || (regno >= FIRST_PSEUDO_REGISTER))
339 /* Only the last def(s) for a regno in the block has any
341 if (!bitmap_bit_p (seen_in_block, regno))
343 /* The first def for regno in insn gets to knock out the
344 defs from other instructions. */
345 if ((!bitmap_bit_p (seen_in_insn, regno))
346 /* If the def is to only part of the reg, it does
347 not kill the other defs that reach here. */
348 && (!(DF_REF_FLAGS (def) &
349 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
351 if (n_defs > DF_SPARSE_THRESHOLD)
353 bitmap_set_bit (bb_info->sparse_kill, regno);
354 bitmap_clear_range(bb_info->gen, begin, n_defs);
358 bitmap_set_range (bb_info->kill, begin, n_defs);
359 bitmap_clear_range (bb_info->gen, begin, n_defs);
363 bitmap_set_bit (seen_in_insn, regno);
364 /* All defs for regno in the instruction may be put into
366 if (!(DF_REF_FLAGS (def)
367 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
368 bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
376 /* Compute local reaching def info for basic block BB. */
379 df_rd_bb_local_compute (unsigned int bb_index)
381 basic_block bb = BASIC_BLOCK (bb_index);
382 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
385 bitmap_clear (seen_in_block);
386 bitmap_clear (seen_in_insn);
388 /* Artificials are only hard regs. */
389 if (!(df->changeable_flags & DF_NO_HARD_REGS))
390 df_rd_bb_local_compute_process_def (bb_info,
391 df_get_artificial_defs (bb_index),
394 FOR_BB_INSNS_REVERSE (bb, insn)
396 unsigned int uid = INSN_UID (insn);
401 df_rd_bb_local_compute_process_def (bb_info,
402 DF_INSN_UID_DEFS (uid), 0);
404 /* This complex dance with the two bitmaps is required because
405 instructions can assign twice to the same pseudo. This
406 generally happens with calls that will have one def for the
407 result and another def for the clobber. If only one vector
408 is used and the clobber goes first, the result will be
410 bitmap_ior_into (seen_in_block, seen_in_insn);
411 bitmap_clear (seen_in_insn);
414 /* Process the artificial defs at the top of the block last since we
415 are going backwards through the block and these are logically at
417 if (!(df->changeable_flags & DF_NO_HARD_REGS))
418 df_rd_bb_local_compute_process_def (bb_info,
419 df_get_artificial_defs (bb_index),
424 /* Compute local reaching def info for each basic block within BLOCKS. */
427 df_rd_local_compute (bitmap all_blocks)
429 unsigned int bb_index;
432 struct df_rd_problem_data *problem_data
433 = (struct df_rd_problem_data *) df_rd->problem_data;
434 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
435 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
439 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
441 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
443 df_rd_bb_local_compute (bb_index);
446 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
447 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
449 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
450 bitmap_set_bit (sparse_invalidated, regno);
452 bitmap_set_range (dense_invalidated,
453 DF_DEFS_BEGIN (regno),
454 DF_DEFS_COUNT (regno));
460 /* Initialize the solution bit vectors for problem. */
463 df_rd_init_solution (bitmap all_blocks)
465 unsigned int bb_index;
468 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
470 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
472 bitmap_copy (bb_info->out, bb_info->gen);
473 bitmap_clear (bb_info->in);
477 /* In of target gets or of out of source. */
480 df_rd_confluence_n (edge e)
482 bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
483 bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
485 if (e->flags & EDGE_FAKE)
488 if (e->flags & EDGE_EH)
490 struct df_rd_problem_data *problem_data
491 = (struct df_rd_problem_data *) df_rd->problem_data;
492 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
493 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
496 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
498 bitmap_copy (tmp, op2);
499 bitmap_and_compl_into (tmp, dense_invalidated);
501 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
503 bitmap_clear_range (tmp,
504 DF_DEFS_BEGIN (regno),
505 DF_DEFS_COUNT (regno));
507 bitmap_ior_into (op1, tmp);
511 bitmap_ior_into (op1, op2);
515 /* Transfer function. */
518 df_rd_transfer_function (int bb_index)
520 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
523 bitmap in = bb_info->in;
524 bitmap out = bb_info->out;
525 bitmap gen = bb_info->gen;
526 bitmap kill = bb_info->kill;
527 bitmap sparse_kill = bb_info->sparse_kill;
529 if (bitmap_empty_p (sparse_kill))
530 return bitmap_ior_and_compl (out, gen, in, kill);
533 struct df_rd_problem_data *problem_data;
534 bool changed = false;
537 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
538 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
539 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
540 tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
542 bitmap_copy (tmp, in);
543 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
545 bitmap_clear_range (tmp,
546 DF_DEFS_BEGIN (regno),
547 DF_DEFS_COUNT (regno));
549 bitmap_and_compl_into (tmp, kill);
550 bitmap_ior_into (tmp, gen);
551 changed = !bitmap_equal_p (tmp, out);
564 /* Free all storage associated with the problem. */
569 struct df_rd_problem_data *problem_data
570 = (struct df_rd_problem_data *) df_rd->problem_data;
574 free_alloc_pool (df_rd->block_pool);
575 bitmap_obstack_release (&problem_data->rd_bitmaps);
577 df_rd->block_info_size = 0;
578 free (df_rd->block_info);
579 free (df_rd->problem_data);
585 /* Debugging info. */
588 df_rd_start_dump (FILE *file)
590 struct df_rd_problem_data *problem_data
591 = (struct df_rd_problem_data *) df_rd->problem_data;
592 unsigned int m = DF_REG_SIZE(df);
595 if (!df_rd->block_info)
598 fprintf (file, ";; Reaching defs:\n\n");
600 fprintf (file, " sparse invalidated \t");
601 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
602 fprintf (file, " dense invalidated \t");
603 dump_bitmap (file, problem_data->dense_invalidated_by_call);
605 for (regno = 0; regno < m; regno++)
606 if (DF_DEFS_COUNT (regno))
607 fprintf (file, "%d[%d,%d] ", regno,
608 DF_DEFS_BEGIN (regno),
609 DF_DEFS_COUNT (regno));
610 fprintf (file, "\n");
615 /* Debugging info at top of bb. */
618 df_rd_top_dump (basic_block bb, FILE *file)
620 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
621 if (!bb_info || !bb_info->in)
624 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
625 dump_bitmap (file, bb_info->in);
626 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
627 dump_bitmap (file, bb_info->gen);
628 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
629 dump_bitmap (file, bb_info->kill);
633 /* Debugging info at top of bb. */
636 df_rd_bottom_dump (basic_block bb, FILE *file)
638 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
639 if (!bb_info || !bb_info->out)
642 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
643 dump_bitmap (file, bb_info->out);
646 /* All of the information associated with every instance of the problem. */
648 static struct df_problem problem_RD =
650 DF_RD, /* Problem id. */
651 DF_FORWARD, /* Direction. */
652 df_rd_alloc, /* Allocate the problem specific data. */
653 NULL, /* Reset global information. */
654 df_rd_free_bb_info, /* Free basic block info. */
655 df_rd_local_compute, /* Local compute function. */
656 df_rd_init_solution, /* Init the solution specific data. */
657 df_worklist_dataflow, /* Worklist solver. */
658 NULL, /* Confluence operator 0. */
659 df_rd_confluence_n, /* Confluence operator n. */
660 df_rd_transfer_function, /* Transfer function. */
661 NULL, /* Finalize function. */
662 df_rd_free, /* Free all of the problem information. */
663 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
664 df_rd_start_dump, /* Debugging. */
665 df_rd_top_dump, /* Debugging start block. */
666 df_rd_bottom_dump, /* Debugging end block. */
667 NULL, /* Incremental solution verify start. */
668 NULL, /* Incremental solution verify end. */
669 NULL, /* Dependent problem. */
670 TV_DF_RD, /* Timing variable. */
671 true /* Reset blocks on dropping out of blocks_to_analyze. */
676 /* Create a new DATAFLOW instance and add it to an existing instance
677 of DF. The returned structure is what is used to get at the
681 df_rd_add_problem (void)
683 df_add_problem (&problem_RD);
688 /*----------------------------------------------------------------------------
691 Find the locations in the function where any use of a pseudo can
692 reach in the backwards direction. In and out bitvectors are built
693 for each basic block. The regno is used to index into these sets.
694 See df.h for details.
695 ----------------------------------------------------------------------------*/
697 /* Private data used to verify the solution for this problem. */
698 struct df_lr_problem_data
705 /* Set basic block info. */
708 df_lr_set_bb_info (unsigned int index,
709 struct df_lr_bb_info *bb_info)
712 gcc_assert (index < df_lr->block_info_size);
713 df_lr->block_info[index] = bb_info;
717 /* Free basic block info. */
720 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
723 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
726 BITMAP_FREE (bb_info->use);
727 BITMAP_FREE (bb_info->def);
728 BITMAP_FREE (bb_info->in);
729 BITMAP_FREE (bb_info->out);
730 pool_free (df_lr->block_pool, bb_info);
735 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
736 not touched unless the block is new. */
739 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
741 unsigned int bb_index;
744 if (!df_lr->block_pool)
745 df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
746 sizeof (struct df_lr_bb_info), 50);
748 df_grow_bb_info (df_lr);
750 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
752 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
755 bitmap_clear (bb_info->def);
756 bitmap_clear (bb_info->use);
760 bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
761 df_lr_set_bb_info (bb_index, bb_info);
762 bb_info->use = BITMAP_ALLOC (NULL);
763 bb_info->def = BITMAP_ALLOC (NULL);
764 bb_info->in = BITMAP_ALLOC (NULL);
765 bb_info->out = BITMAP_ALLOC (NULL);
769 df_lr->optional_p = false;
773 /* Reset the global solution for recalculation. */
776 df_lr_reset (bitmap all_blocks)
778 unsigned int bb_index;
781 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
783 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
784 gcc_assert (bb_info);
785 bitmap_clear (bb_info->in);
786 bitmap_clear (bb_info->out);
791 /* Compute local live register info for basic block BB. */
794 df_lr_bb_local_compute (unsigned int bb_index)
796 basic_block bb = BASIC_BLOCK (bb_index);
797 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
799 struct df_ref **def_rec;
800 struct df_ref **use_rec;
802 /* Process the registers set in an exception handler. */
803 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
805 struct df_ref *def = *def_rec;
806 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
808 unsigned int dregno = DF_REF_REGNO (def);
809 bitmap_set_bit (bb_info->def, dregno);
810 bitmap_clear_bit (bb_info->use, dregno);
814 /* Process the hardware registers that are always live. */
815 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
817 struct df_ref *use = *use_rec;
818 /* Add use to set of uses in this BB. */
819 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
820 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
823 FOR_BB_INSNS_REVERSE (bb, insn)
825 unsigned int uid = INSN_UID (insn);
830 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
832 struct df_ref *def = *def_rec;
833 /* If the def is to only part of the reg, it does
834 not kill the other defs that reach here. */
835 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
837 unsigned int dregno = DF_REF_REGNO (def);
838 bitmap_set_bit (bb_info->def, dregno);
839 bitmap_clear_bit (bb_info->use, dregno);
843 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
845 struct df_ref *use = *use_rec;
846 /* Add use to set of uses in this BB. */
847 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
851 /* Process the registers set in an exception handler or the hard
852 frame pointer if this block is the target of a non local
854 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
856 struct df_ref *def = *def_rec;
857 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
859 unsigned int dregno = DF_REF_REGNO (def);
860 bitmap_set_bit (bb_info->def, dregno);
861 bitmap_clear_bit (bb_info->use, dregno);
866 /* Process the uses that are live into an exception handler. */
867 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
869 struct df_ref *use = *use_rec;
870 /* Add use to set of uses in this BB. */
871 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
872 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
876 /* If the df_live problem is not defined, such as at -O0 and -O1, we
877 still need to keep the luids up to date. This is normally done
878 in the df_live problem since this problem has a forwards
881 df_recompute_luids (bb);
885 /* Compute local live register info for each basic block within BLOCKS. */
888 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
890 unsigned int bb_index;
893 bitmap_clear (df->hardware_regs_used);
895 /* The all-important stack pointer must always be live. */
896 bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
898 /* Before reload, there are a few registers that must be forced
899 live everywhere -- which might not already be the case for
900 blocks within infinite loops. */
901 if (!reload_completed)
903 /* Any reference to any pseudo before reload is a potential
904 reference of the frame pointer. */
905 bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
907 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
908 /* Pseudos with argument area equivalences may require
909 reloading via the argument pointer. */
910 if (fixed_regs[ARG_POINTER_REGNUM])
911 bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
914 /* Any constant, or pseudo with constant equivalences, may
915 require reloading from memory using the pic register. */
916 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
917 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
918 bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
921 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
923 if (bb_index == EXIT_BLOCK)
925 /* The exit block is special for this problem and its bits are
926 computed from thin air. */
927 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
928 bitmap_copy (bb_info->use, df->exit_block_uses);
931 df_lr_bb_local_compute (bb_index);
934 bitmap_clear (df_lr->out_of_date_transfer_functions);
938 /* Initialize the solution vectors. */
941 df_lr_init (bitmap all_blocks)
943 unsigned int bb_index;
946 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
948 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
949 bitmap_copy (bb_info->in, bb_info->use);
950 bitmap_clear (bb_info->out);
955 /* Confluence function that processes infinite loops. This might be a
956 noreturn function that throws. And even if it isn't, getting the
957 unwind info right helps debugging. */
959 df_lr_confluence_0 (basic_block bb)
961 bitmap op1 = df_lr_get_bb_info (bb->index)->out;
962 if (bb != EXIT_BLOCK_PTR)
963 bitmap_copy (op1, df->hardware_regs_used);
967 /* Confluence function that ignores fake edges. */
970 df_lr_confluence_n (edge e)
972 bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
973 bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
975 /* Call-clobbered registers die across exception and call edges. */
976 /* ??? Abnormal call edges ignored for the moment, as this gets
977 confused by sibling call edges, which crashes reg-stack. */
978 if (e->flags & EDGE_EH)
979 bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
981 bitmap_ior_into (op1, op2);
983 bitmap_ior_into (op1, df->hardware_regs_used);
987 /* Transfer function. */
990 df_lr_transfer_function (int bb_index)
992 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
993 bitmap in = bb_info->in;
994 bitmap out = bb_info->out;
995 bitmap use = bb_info->use;
996 bitmap def = bb_info->def;
998 return bitmap_ior_and_compl (in, use, out, def);
1002 /* Run the fast dce as a side effect of building LR. */
1005 df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1007 if (df->changeable_flags & DF_LR_RUN_DCE)
1010 if (df_lr->problem_data && df_lr->solutions_dirty)
1012 /* If we are here, then it is because we are both verifying
1013 the solution and the dce changed the function. In that case
1014 the verification info built will be wrong. So we leave the
1015 dirty flag true so that the verifier will skip the checking
1016 part and just clean up.*/
1017 df_lr->solutions_dirty = true;
1020 df_lr->solutions_dirty = false;
1023 df_lr->solutions_dirty = false;
1027 /* Free all storage associated with the problem. */
1032 if (df_lr->block_info)
1035 for (i = 0; i < df_lr->block_info_size; i++)
1037 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1040 BITMAP_FREE (bb_info->use);
1041 BITMAP_FREE (bb_info->def);
1042 BITMAP_FREE (bb_info->in);
1043 BITMAP_FREE (bb_info->out);
1046 free_alloc_pool (df_lr->block_pool);
1048 df_lr->block_info_size = 0;
1049 free (df_lr->block_info);
1052 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1057 /* Debugging info at top of bb. */
1060 df_lr_top_dump (basic_block bb, FILE *file)
1062 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1063 struct df_lr_problem_data *problem_data;
1064 if (!bb_info || !bb_info->in)
1067 fprintf (file, ";; lr in \t");
1068 df_print_regset (file, bb_info->in);
1069 if (df_lr->problem_data)
1071 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1072 fprintf (file, ";; old in \t");
1073 df_print_regset (file, problem_data->in[bb->index]);
1075 fprintf (file, ";; lr use \t");
1076 df_print_regset (file, bb_info->use);
1077 fprintf (file, ";; lr def \t");
1078 df_print_regset (file, bb_info->def);
1082 /* Debugging info at bottom of bb. */
1085 df_lr_bottom_dump (basic_block bb, FILE *file)
1087 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1088 struct df_lr_problem_data *problem_data;
1089 if (!bb_info || !bb_info->out)
1092 fprintf (file, ";; lr out \t");
1093 df_print_regset (file, bb_info->out);
1094 if (df_lr->problem_data)
1096 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1097 fprintf (file, ";; old out \t");
1098 df_print_regset (file, problem_data->out[bb->index]);
1103 /* Build the datastructure to verify that the solution to the dataflow
1104 equations is not dirty. */
1107 df_lr_verify_solution_start (void)
1110 struct df_lr_problem_data *problem_data;
1111 if (df_lr->solutions_dirty)
1113 df_lr->problem_data = NULL;
1117 /* Set it true so that the solution is recomputed. */
1118 df_lr->solutions_dirty = true;
1120 problem_data = XNEW (struct df_lr_problem_data);
1121 df_lr->problem_data = problem_data;
1122 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1123 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1127 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1128 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1129 bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1130 bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1135 /* Compare the saved datastructure and the new solution to the dataflow
1139 df_lr_verify_solution_end (void)
1141 struct df_lr_problem_data *problem_data;
1144 if (df_lr->problem_data == NULL)
1147 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1149 if (df_lr->solutions_dirty)
1150 /* Do not check if the solution is still dirty. See the comment
1151 in df_lr_finalize for details. */
1152 df_lr->solutions_dirty = false;
1156 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1157 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1159 /*df_dump (stderr);*/
1164 /* Cannot delete them immediately because you may want to dump them
1165 if the comparison fails. */
1168 BITMAP_FREE (problem_data->in[bb->index]);
1169 BITMAP_FREE (problem_data->out[bb->index]);
1172 free (problem_data->in);
1173 free (problem_data->out);
1174 free (problem_data);
1175 df_lr->problem_data = NULL;
1179 /* All of the information associated with every instance of the problem. */
1181 static struct df_problem problem_LR =
1183 DF_LR, /* Problem id. */
1184 DF_BACKWARD, /* Direction. */
1185 df_lr_alloc, /* Allocate the problem specific data. */
1186 df_lr_reset, /* Reset global information. */
1187 df_lr_free_bb_info, /* Free basic block info. */
1188 df_lr_local_compute, /* Local compute function. */
1189 df_lr_init, /* Init the solution specific data. */
1190 df_worklist_dataflow, /* Worklist solver. */
1191 df_lr_confluence_0, /* Confluence operator 0. */
1192 df_lr_confluence_n, /* Confluence operator n. */
1193 df_lr_transfer_function, /* Transfer function. */
1194 df_lr_finalize, /* Finalize function. */
1195 df_lr_free, /* Free all of the problem information. */
1196 NULL, /* Remove this problem from the stack of dataflow problems. */
1197 NULL, /* Debugging. */
1198 df_lr_top_dump, /* Debugging start block. */
1199 df_lr_bottom_dump, /* Debugging end block. */
1200 df_lr_verify_solution_start,/* Incremental solution verify start. */
1201 df_lr_verify_solution_end, /* Incremental solution verify end. */
1202 NULL, /* Dependent problem. */
1203 TV_DF_LR, /* Timing variable. */
1204 false /* Reset blocks on dropping out of blocks_to_analyze. */
1208 /* Create a new DATAFLOW instance and add it to an existing instance
1209 of DF. The returned structure is what is used to get at the
1213 df_lr_add_problem (void)
1215 df_add_problem (&problem_LR);
1216 /* These will be initialized when df_scan_blocks processes each
1218 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1222 /* Verify that all of the lr related info is consistent and
1226 df_lr_verify_transfer_functions (void)
1238 saved_def = BITMAP_ALLOC (NULL);
1239 saved_use = BITMAP_ALLOC (NULL);
1240 saved_adef = BITMAP_ALLOC (NULL);
1241 saved_ause = BITMAP_ALLOC (NULL);
1242 all_blocks = BITMAP_ALLOC (NULL);
1246 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1247 bitmap_set_bit (all_blocks, bb->index);
1251 /* Make a copy of the transfer functions and then compute
1252 new ones to see if the transfer functions have
1254 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1257 bitmap_copy (saved_def, bb_info->def);
1258 bitmap_copy (saved_use, bb_info->use);
1259 bitmap_clear (bb_info->def);
1260 bitmap_clear (bb_info->use);
1262 df_lr_bb_local_compute (bb->index);
1263 gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1264 gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1269 /* If we do not have basic block info, the block must be in
1270 the list of dirty blocks or else some one has added a
1271 block behind our backs. */
1272 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1275 /* Make sure no one created a block without following
1277 gcc_assert (df_scan_get_bb_info (bb->index));
1280 /* Make sure there are no dirty bits in blocks that have been deleted. */
1281 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1284 BITMAP_FREE (saved_def);
1285 BITMAP_FREE (saved_use);
1286 BITMAP_FREE (saved_adef);
1287 BITMAP_FREE (saved_ause);
1288 BITMAP_FREE (all_blocks);
1293 /*----------------------------------------------------------------------------
1294 LIVE AND MUST-INITIALIZED REGISTERS.
1296 This problem first computes the IN and OUT bitvectors for the
1297 must-initialized registers problems, which is a forward problem.
1298 It gives the set of registers for which we MUST have an available
1299 definition on any path from the entry block to the entry/exit of
1300 a basic block. Sets generate a definition, while clobbers kill
1303 In and out bitvectors are built for each basic block and are indexed by
1304 regnum (see df.h for details). In and out bitvectors in struct
1305 df_live_bb_info actually refers to the must-initialized problem;
1307 Then, the in and out sets for the LIVE problem itself are computed.
1308 These are the logical AND of the IN and OUT sets from the LR problem
1309 and the must-initialized problem.
1310 ----------------------------------------------------------------------------*/
1312 /* Private data used to verify the solution for this problem. */
1313 struct df_live_problem_data
1319 /* Scratch var used by transfer functions. This is used to implement
1320 an optimization to reduce the amount of space used to compute the
1321 combined lr and live analysis. */
1322 static bitmap df_live_scratch;
1324 /* Set basic block info. */
1327 df_live_set_bb_info (unsigned int index,
1328 struct df_live_bb_info *bb_info)
1330 gcc_assert (df_live);
1331 gcc_assert (index < df_live->block_info_size);
1332 df_live->block_info[index] = bb_info;
1336 /* Free basic block info. */
1339 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1342 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1345 BITMAP_FREE (bb_info->gen);
1346 BITMAP_FREE (bb_info->kill);
1347 BITMAP_FREE (bb_info->in);
1348 BITMAP_FREE (bb_info->out);
1349 pool_free (df_live->block_pool, bb_info);
1354 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1355 not touched unless the block is new. */
1358 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1360 unsigned int bb_index;
1363 if (!df_live->block_pool)
1364 df_live->block_pool = create_alloc_pool ("df_live_block pool",
1365 sizeof (struct df_live_bb_info), 100);
1366 if (!df_live_scratch)
1367 df_live_scratch = BITMAP_ALLOC (NULL);
1369 df_grow_bb_info (df_live);
1371 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1373 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1376 bitmap_clear (bb_info->kill);
1377 bitmap_clear (bb_info->gen);
1381 bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1382 df_live_set_bb_info (bb_index, bb_info);
1383 bb_info->kill = BITMAP_ALLOC (NULL);
1384 bb_info->gen = BITMAP_ALLOC (NULL);
1385 bb_info->in = BITMAP_ALLOC (NULL);
1386 bb_info->out = BITMAP_ALLOC (NULL);
1389 df_live->optional_p = (optimize <= 1);
1393 /* Reset the global solution for recalculation. */
1396 df_live_reset (bitmap all_blocks)
1398 unsigned int bb_index;
1401 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1403 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1404 gcc_assert (bb_info);
1405 bitmap_clear (bb_info->in);
1406 bitmap_clear (bb_info->out);
1411 /* Compute local uninitialized register info for basic block BB. */
1414 df_live_bb_local_compute (unsigned int bb_index)
1416 basic_block bb = BASIC_BLOCK (bb_index);
1417 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1419 struct df_ref **def_rec;
1422 FOR_BB_INSNS (bb, insn)
1424 unsigned int uid = INSN_UID (insn);
1425 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1427 /* Inserting labels does not always trigger the incremental
1431 gcc_assert (!INSN_P (insn));
1432 insn_info = df_insn_create_insn_record (insn);
1435 DF_INSN_INFO_LUID (insn_info) = luid;
1440 for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
1442 struct df_ref *def = *def_rec;
1443 unsigned int regno = DF_REF_REGNO (def);
1445 if (DF_REF_FLAGS_IS_SET (def,
1446 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1447 /* All partial or conditional def
1448 seen are included in the gen set. */
1449 bitmap_set_bit (bb_info->gen, regno);
1450 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1451 /* Only must clobbers for the entire reg destroy the
1453 bitmap_set_bit (bb_info->kill, regno);
1454 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1455 bitmap_set_bit (bb_info->gen, regno);
1459 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1461 struct df_ref *def = *def_rec;
1462 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1467 /* Compute local uninitialized register info. */
1470 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1472 unsigned int bb_index;
1475 df_grow_insn_info ();
1477 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1480 df_live_bb_local_compute (bb_index);
1483 bitmap_clear (df_live->out_of_date_transfer_functions);
1487 /* Initialize the solution vectors. */
1490 df_live_init (bitmap all_blocks)
1492 unsigned int bb_index;
1495 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1497 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1498 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1500 /* No register may reach a location where it is not used. Thus
1501 we trim the rr result to the places where it is used. */
1502 bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
1503 bitmap_clear (bb_info->in);
1507 /* Forward confluence function that ignores fake edges. */
1510 df_live_confluence_n (edge e)
1512 bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1513 bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1515 if (e->flags & EDGE_FAKE)
1518 bitmap_ior_into (op1, op2);
1522 /* Transfer function for the forwards must-initialized problem. */
1525 df_live_transfer_function (int bb_index)
1527 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1528 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1529 bitmap in = bb_info->in;
1530 bitmap out = bb_info->out;
1531 bitmap gen = bb_info->gen;
1532 bitmap kill = bb_info->kill;
1534 /* We need to use a scratch set here so that the value returned from
1535 this function invocation properly reflects if the sets changed in
1536 a significant way; i.e. not just because the lr set was anded
1538 bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1539 /* No register may reach a location where it is not used. Thus
1540 we trim the rr result to the places where it is used. */
1541 bitmap_and_into (in, bb_lr_info->in);
1543 return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1547 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1550 df_live_finalize (bitmap all_blocks)
1553 if (df_live->solutions_dirty)
1556 unsigned int bb_index;
1558 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1560 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1561 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1563 /* No register may reach a location where it is not used. Thus
1564 we trim the rr result to the places where it is used. */
1565 bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1566 bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1569 df_live->solutions_dirty = false;
1574 /* Free all storage associated with the problem. */
1579 if (df_live->block_info)
1583 for (i = 0; i < df_live->block_info_size; i++)
1585 struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1588 BITMAP_FREE (bb_info->gen);
1589 BITMAP_FREE (bb_info->kill);
1590 BITMAP_FREE (bb_info->in);
1591 BITMAP_FREE (bb_info->out);
1595 free_alloc_pool (df_live->block_pool);
1596 df_live->block_info_size = 0;
1597 free (df_live->block_info);
1599 if (df_live_scratch)
1600 BITMAP_FREE (df_live_scratch);
1602 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1607 /* Debugging info at top of bb. */
1610 df_live_top_dump (basic_block bb, FILE *file)
1612 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1613 struct df_live_problem_data *problem_data;
1615 if (!bb_info || !bb_info->in)
1618 fprintf (file, ";; live in \t");
1619 df_print_regset (file, bb_info->in);
1620 if (df_live->problem_data)
1622 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1623 fprintf (file, ";; old in \t");
1624 df_print_regset (file, problem_data->in[bb->index]);
1626 fprintf (file, ";; live gen \t");
1627 df_print_regset (file, bb_info->gen);
1628 fprintf (file, ";; live kill\t");
1629 df_print_regset (file, bb_info->kill);
1633 /* Debugging info at bottom of bb. */
1636 df_live_bottom_dump (basic_block bb, FILE *file)
1638 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1639 struct df_live_problem_data *problem_data;
1641 if (!bb_info || !bb_info->out)
1644 fprintf (file, ";; live out \t");
1645 df_print_regset (file, bb_info->out);
1646 if (df_live->problem_data)
1648 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1649 fprintf (file, ";; old out \t");
1650 df_print_regset (file, problem_data->out[bb->index]);
1655 /* Build the datastructure to verify that the solution to the dataflow
1656 equations is not dirty. */
1659 df_live_verify_solution_start (void)
1662 struct df_live_problem_data *problem_data;
1663 if (df_live->solutions_dirty)
1665 df_live->problem_data = NULL;
1669 /* Set it true so that the solution is recomputed. */
1670 df_live->solutions_dirty = true;
1672 problem_data = XNEW (struct df_live_problem_data);
1673 df_live->problem_data = problem_data;
1674 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1675 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1679 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1680 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1681 bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1682 bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1687 /* Compare the saved datastructure and the new solution to the dataflow
1691 df_live_verify_solution_end (void)
1693 struct df_live_problem_data *problem_data;
1696 if (df_live->problem_data == NULL)
1699 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1703 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1704 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1706 /*df_dump (stderr);*/
1711 /* Cannot delete them immediately because you may want to dump them
1712 if the comparison fails. */
1715 BITMAP_FREE (problem_data->in[bb->index]);
1716 BITMAP_FREE (problem_data->out[bb->index]);
1719 free (problem_data->in);
1720 free (problem_data->out);
1721 free (problem_data);
1722 df_live->problem_data = NULL;
1726 /* All of the information associated with every instance of the problem. */
1728 static struct df_problem problem_LIVE =
1730 DF_LIVE, /* Problem id. */
1731 DF_FORWARD, /* Direction. */
1732 df_live_alloc, /* Allocate the problem specific data. */
1733 df_live_reset, /* Reset global information. */
1734 df_live_free_bb_info, /* Free basic block info. */
1735 df_live_local_compute, /* Local compute function. */
1736 df_live_init, /* Init the solution specific data. */
1737 df_worklist_dataflow, /* Worklist solver. */
1738 NULL, /* Confluence operator 0. */
1739 df_live_confluence_n, /* Confluence operator n. */
1740 df_live_transfer_function, /* Transfer function. */
1741 df_live_finalize, /* Finalize function. */
1742 df_live_free, /* Free all of the problem information. */
1743 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1744 NULL, /* Debugging. */
1745 df_live_top_dump, /* Debugging start block. */
1746 df_live_bottom_dump, /* Debugging end block. */
1747 df_live_verify_solution_start,/* Incremental solution verify start. */
1748 df_live_verify_solution_end, /* Incremental solution verify end. */
1749 &problem_LR, /* Dependent problem. */
1750 TV_DF_LIVE, /* Timing variable. */
1751 false /* Reset blocks on dropping out of blocks_to_analyze. */
1755 /* Create a new DATAFLOW instance and add it to an existing instance
1756 of DF. The returned structure is what is used to get at the
1760 df_live_add_problem (void)
1762 df_add_problem (&problem_LIVE);
1763 /* These will be initialized when df_scan_blocks processes each
1765 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1769 /* Set all of the blocks as dirty. This needs to be done if this
1770 problem is added after all of the insns have been scanned. */
1773 df_live_set_all_dirty (void)
1777 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1782 /* Verify that all of the lr related info is consistent and
1786 df_live_verify_transfer_functions (void)
1796 saved_gen = BITMAP_ALLOC (NULL);
1797 saved_kill = BITMAP_ALLOC (NULL);
1798 all_blocks = BITMAP_ALLOC (NULL);
1800 df_grow_insn_info ();
1804 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1805 bitmap_set_bit (all_blocks, bb->index);
1809 /* Make a copy of the transfer functions and then compute
1810 new ones to see if the transfer functions have
1812 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1815 bitmap_copy (saved_gen, bb_info->gen);
1816 bitmap_copy (saved_kill, bb_info->kill);
1817 bitmap_clear (bb_info->gen);
1818 bitmap_clear (bb_info->kill);
1820 df_live_bb_local_compute (bb->index);
1821 gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1822 gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1827 /* If we do not have basic block info, the block must be in
1828 the list of dirty blocks or else some one has added a
1829 block behind our backs. */
1830 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1833 /* Make sure no one created a block without following
1835 gcc_assert (df_scan_get_bb_info (bb->index));
1838 /* Make sure there are no dirty bits in blocks that have been deleted. */
1839 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1841 BITMAP_FREE (saved_gen);
1842 BITMAP_FREE (saved_kill);
1843 BITMAP_FREE (all_blocks);
1846 /*----------------------------------------------------------------------------
1847 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1849 Link either the defs to the uses and / or the uses to the defs.
1851 These problems are set up like the other dataflow problems so that
1852 they nicely fit into the framework. They are much simpler and only
1853 involve a single traversal of instructions and an examination of
1854 the reaching defs information (the dependent problem).
1855 ----------------------------------------------------------------------------*/
1857 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1859 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1862 df_chain_create (struct df_ref *src, struct df_ref *dst)
1864 struct df_link *head = DF_REF_CHAIN (src);
1865 struct df_link *link = pool_alloc (df_chain->block_pool);
1867 DF_REF_CHAIN (src) = link;
1874 /* Delete any du or ud chains that start at REF and point to
1877 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
1879 struct df_link *chain = DF_REF_CHAIN (ref);
1880 struct df_link *prev = NULL;
1884 if (chain->ref == target)
1887 prev->next = chain->next;
1889 DF_REF_CHAIN (ref) = chain->next;
1890 pool_free (df_chain->block_pool, chain);
1894 chain = chain->next;
1899 /* Delete a du or ud chain that leave or point to REF. */
1902 df_chain_unlink (struct df_ref *ref)
1904 struct df_link *chain = DF_REF_CHAIN (ref);
1907 struct df_link *next = chain->next;
1908 /* Delete the other side if it exists. */
1909 df_chain_unlink_1 (chain->ref, ref);
1910 pool_free (df_chain->block_pool, chain);
1913 DF_REF_CHAIN (ref) = NULL;
1917 /* Copy the du or ud chain starting at FROM_REF and attach it to
1921 df_chain_copy (struct df_ref *to_ref,
1922 struct df_link *from_ref)
1926 df_chain_create (to_ref, from_ref->ref);
1927 from_ref = from_ref->next;
1932 /* Remove this problem from the stack of dataflow problems. */
1935 df_chain_remove_problem (void)
1938 unsigned int bb_index;
1940 /* Wholesale destruction of the old chains. */
1941 if (df_chain->block_pool)
1942 free_alloc_pool (df_chain->block_pool);
1944 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1947 struct df_ref **def_rec;
1948 struct df_ref **use_rec;
1949 basic_block bb = BASIC_BLOCK (bb_index);
1951 if (df_chain_problem_p (DF_DU_CHAIN))
1952 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1953 DF_REF_CHAIN (*def_rec) = NULL;
1954 if (df_chain_problem_p (DF_UD_CHAIN))
1955 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1956 DF_REF_CHAIN (*use_rec) = NULL;
1958 FOR_BB_INSNS (bb, insn)
1960 unsigned int uid = INSN_UID (insn);
1964 if (df_chain_problem_p (DF_DU_CHAIN))
1965 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1966 DF_REF_CHAIN (*def_rec) = NULL;
1967 if (df_chain_problem_p (DF_UD_CHAIN))
1969 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1970 DF_REF_CHAIN (*use_rec) = NULL;
1971 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1972 DF_REF_CHAIN (*use_rec) = NULL;
1978 bitmap_clear (df_chain->out_of_date_transfer_functions);
1979 df_chain->block_pool = NULL;
1983 /* Remove the chain problem completely. */
1986 df_chain_fully_remove_problem (void)
1988 df_chain_remove_problem ();
1989 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1994 /* Create def-use or use-def chains. */
1997 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1999 df_chain_remove_problem ();
2000 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2001 sizeof (struct df_link), 50);
2002 df_chain->optional_p = true;
2006 /* Reset all of the chains when the set of basic blocks changes. */
2009 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2011 df_chain_remove_problem ();
2015 /* Create the chains for a list of USEs. */
2018 df_chain_create_bb_process_use (bitmap local_rd,
2019 struct df_ref **use_rec,
2020 enum df_ref_flags top_flag)
2023 unsigned int def_index;
2027 struct df_ref *use = *use_rec;
2028 unsigned int uregno = DF_REF_REGNO (use);
2029 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2030 || (uregno >= FIRST_PSEUDO_REGISTER))
2032 /* Do not want to go through this for an uninitialized var. */
2033 int count = DF_DEFS_COUNT (uregno);
2036 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2038 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2039 unsigned int last_index = first_index + count - 1;
2041 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2044 if (def_index > last_index)
2047 def = DF_DEFS_GET (def_index);
2048 if (df_chain_problem_p (DF_DU_CHAIN))
2049 df_chain_create (def, use);
2050 if (df_chain_problem_p (DF_UD_CHAIN))
2051 df_chain_create (use, def);
2062 /* Create chains from reaching defs bitmaps for basic block BB. */
2065 df_chain_create_bb (unsigned int bb_index)
2067 basic_block bb = BASIC_BLOCK (bb_index);
2068 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2070 bitmap cpy = BITMAP_ALLOC (NULL);
2071 struct df_ref **def_rec;
2073 bitmap_copy (cpy, bb_info->in);
2074 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2076 /* Since we are going forwards, process the artificial uses first
2077 then the artificial defs second. */
2080 /* Create the chains for the artificial uses from the EH_USES at the
2081 beginning of the block. */
2083 /* Artificials are only hard regs. */
2084 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2085 df_chain_create_bb_process_use (cpy,
2086 df_get_artificial_uses (bb->index),
2090 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2092 struct df_ref *def = *def_rec;
2093 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2095 unsigned int dregno = DF_REF_REGNO (def);
2096 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2097 bitmap_clear_range (cpy,
2098 DF_DEFS_BEGIN (dregno),
2099 DF_DEFS_COUNT (dregno));
2100 bitmap_set_bit (cpy, DF_REF_ID (def));
2104 /* Process the regular instructions next. */
2105 FOR_BB_INSNS (bb, insn)
2107 struct df_ref **def_rec;
2108 unsigned int uid = INSN_UID (insn);
2113 /* Now scan the uses and link them up with the defs that remain
2114 in the cpy vector. */
2116 df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2118 if (df->changeable_flags & DF_EQ_NOTES)
2119 df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2122 /* Since we are going forwards, process the defs second. This
2123 pass only changes the bits in cpy. */
2124 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2126 struct df_ref *def = *def_rec;
2127 unsigned int dregno = DF_REF_REGNO (def);
2128 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2129 || (dregno >= FIRST_PSEUDO_REGISTER))
2131 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2132 bitmap_clear_range (cpy,
2133 DF_DEFS_BEGIN (dregno),
2134 DF_DEFS_COUNT (dregno));
2135 if (!(DF_REF_FLAGS (def)
2136 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2137 bitmap_set_bit (cpy, DF_REF_ID (def));
2142 /* Create the chains for the artificial uses of the hard registers
2143 at the end of the block. */
2144 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2145 df_chain_create_bb_process_use (cpy,
2146 df_get_artificial_uses (bb->index),
2152 /* Create def-use chains from reaching use bitmaps for basic blocks
2156 df_chain_finalize (bitmap all_blocks)
2158 unsigned int bb_index;
2161 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2163 df_chain_create_bb (bb_index);
2168 /* Free all storage associated with the problem. */
2171 df_chain_free (void)
2173 free_alloc_pool (df_chain->block_pool);
2174 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2179 /* Debugging info. */
2182 df_chain_top_dump (basic_block bb, FILE *file)
2184 if (df_chain_problem_p (DF_DU_CHAIN))
2187 struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2191 fprintf (file, ";; DU chains for artificial defs\n");
2194 struct df_ref *def = *def_rec;
2195 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2196 df_chain_dump (DF_REF_CHAIN (def), file);
2197 fprintf (file, "\n");
2202 FOR_BB_INSNS (bb, insn)
2206 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2207 def_rec = DF_INSN_INFO_DEFS (insn_info);
2210 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2211 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2215 struct df_ref *def = *def_rec;
2216 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2217 if (def->flags & DF_REF_READ_WRITE)
2218 fprintf (file, "read/write ");
2219 df_chain_dump (DF_REF_CHAIN (def), file);
2220 fprintf (file, "\n");
2231 df_chain_bottom_dump (basic_block bb, FILE *file)
2233 if (df_chain_problem_p (DF_UD_CHAIN))
2236 struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2240 fprintf (file, ";; UD chains for artificial uses\n");
2243 struct df_ref *use = *use_rec;
2244 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2245 df_chain_dump (DF_REF_CHAIN (use), file);
2246 fprintf (file, "\n");
2251 FOR_BB_INSNS (bb, insn)
2255 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2256 struct df_ref **eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2257 use_rec = DF_INSN_INFO_USES (insn_info);
2258 if (*use_rec || *eq_use_rec)
2260 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2261 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2265 struct df_ref *use = *use_rec;
2266 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2267 if (use->flags & DF_REF_READ_WRITE)
2268 fprintf (file, "read/write ");
2269 df_chain_dump (DF_REF_CHAIN (use), file);
2270 fprintf (file, "\n");
2275 struct df_ref *use = *eq_use_rec;
2276 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2277 df_chain_dump (DF_REF_CHAIN (use), file);
2278 fprintf (file, "\n");
2288 static struct df_problem problem_CHAIN =
2290 DF_CHAIN, /* Problem id. */
2291 DF_NONE, /* Direction. */
2292 df_chain_alloc, /* Allocate the problem specific data. */
2293 df_chain_reset, /* Reset global information. */
2294 NULL, /* Free basic block info. */
2295 NULL, /* Local compute function. */
2296 NULL, /* Init the solution specific data. */
2297 NULL, /* Iterative solver. */
2298 NULL, /* Confluence operator 0. */
2299 NULL, /* Confluence operator n. */
2300 NULL, /* Transfer function. */
2301 df_chain_finalize, /* Finalize function. */
2302 df_chain_free, /* Free all of the problem information. */
2303 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2304 NULL, /* Debugging. */
2305 df_chain_top_dump, /* Debugging start block. */
2306 df_chain_bottom_dump, /* Debugging end block. */
2307 NULL, /* Incremental solution verify start. */
2308 NULL, /* Incremental solution verify end. */
2309 &problem_RD, /* Dependent problem. */
2310 TV_DF_CHAIN, /* Timing variable. */
2311 false /* Reset blocks on dropping out of blocks_to_analyze. */
2315 /* Create a new DATAFLOW instance and add it to an existing instance
2316 of DF. The returned structure is what is used to get at the
2320 df_chain_add_problem (enum df_chain_flags chain_flags)
2322 df_add_problem (&problem_CHAIN);
2323 df_chain->local_flags = (unsigned int)chain_flags;
2324 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2327 #undef df_chain_problem_p
2330 /*----------------------------------------------------------------------------
2331 BYTE LEVEL LIVE REGISTERS
2333 Find the locations in the function where any use of a pseudo can
2334 reach in the backwards direction. In and out bitvectors are built
2335 for each basic block. There are two mapping functions,
2336 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2337 used to map regnos into bit vector positions.
2339 This problem differs from the regular df_lr function in the way
2340 that subregs, *_extracts and strict_low_parts are handled. In lr
2341 these are consider partial kills, here, the exact set of bytes is
2342 modeled. Note that any reg that has none of these operations is
2343 only modeled with a single bit since all operations access the
2346 This problem is more brittle that the regular lr. It currently can
2347 be used in dce incrementally, but cannot be used in an environment
2348 where insns are created or modified. The problem is that the
2349 mapping of regnos to bitmap positions is relatively compact, in
2350 that if a pseudo does not do any of the byte wise operations, only
2351 one slot is allocated, rather than a slot for each byte. If insn
2352 are created, where a subreg is used for a reg that had no subregs,
2353 the mapping would be wrong. Likewise, there are no checks to see
2354 that new pseudos have been added. These issues could be addressed
2355 by adding a problem specific flag to not use the compact mapping,
2356 if there was a need to do so.
2358 ----------------------------------------------------------------------------*/
2360 /* Private data used to verify the solution for this problem. */
2361 struct df_byte_lr_problem_data
2363 /* Expanded versions of bitvectors used in lr. */
2364 bitmap invalidated_by_call;
2365 bitmap hardware_regs_used;
2367 /* Indexed by regno, this is true if there are subregs, extracts or
2368 strict_low_parts for this regno. */
2369 bitmap needs_expansion;
2371 /* The start position and len for each regno in the various bit
2373 unsigned int* regno_start;
2374 unsigned int* regno_len;
2375 /* An obstack for the bitmaps we need for this problem. */
2376 bitmap_obstack byte_lr_bitmaps;
2380 /* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2383 df_byte_lr_get_regno_start (unsigned int regno)
2385 struct df_byte_lr_problem_data *problem_data
2386 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2387 return problem_data->regno_start[regno];
2391 /* Get the len for REGNO in the df_byte_lr bitmaps. */
2394 df_byte_lr_get_regno_len (unsigned int regno)
2396 struct df_byte_lr_problem_data *problem_data
2397 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2398 return problem_data->regno_len[regno];
2402 /* Set basic block info. */
2405 df_byte_lr_set_bb_info (unsigned int index,
2406 struct df_byte_lr_bb_info *bb_info)
2408 gcc_assert (df_byte_lr);
2409 gcc_assert (index < df_byte_lr->block_info_size);
2410 df_byte_lr->block_info[index] = bb_info;
2414 /* Free basic block info. */
2417 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2420 struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2423 BITMAP_FREE (bb_info->use);
2424 BITMAP_FREE (bb_info->def);
2425 BITMAP_FREE (bb_info->in);
2426 BITMAP_FREE (bb_info->out);
2427 pool_free (df_byte_lr->block_pool, bb_info);
2432 /* Check all of the refs in REF_REC to see if any of them are
2433 extracts, subregs or strict_low_parts. */
2436 df_byte_lr_check_regs (struct df_ref **ref_rec)
2438 struct df_byte_lr_problem_data *problem_data
2439 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2441 for (; *ref_rec; ref_rec++)
2443 struct df_ref *ref = *ref_rec;
2444 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2445 | DF_REF_ZERO_EXTRACT
2446 | DF_REF_STRICT_LOW_PART)
2447 || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2448 bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref));
2453 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2454 regno_start and regno_len. */
2457 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2459 struct df_byte_lr_problem_data *problem_data
2460 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2464 bitmap_clear (dest);
2465 EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2467 bitmap_set_range (dest, problem_data->regno_start[i],
2468 problem_data->regno_len[i]);
2473 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2474 not touched unless the block is new. */
2477 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2479 unsigned int bb_index;
2483 unsigned int index = 0;
2484 unsigned int max_reg = max_reg_num();
2485 struct df_byte_lr_problem_data *problem_data
2486 = problem_data = XNEW (struct df_byte_lr_problem_data);
2488 df_byte_lr->problem_data = problem_data;
2490 if (!df_byte_lr->block_pool)
2491 df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool",
2492 sizeof (struct df_byte_lr_bb_info), 50);
2494 df_grow_bb_info (df_byte_lr);
2496 /* Create the mapping from regnos to slots. This does not change
2497 unless the problem is destroyed and recreated. In particular, if
2498 we end up deleting the only insn that used a subreg, we do not
2499 want to redo the mapping because this would invalidate everything
2502 bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2503 problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2504 problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2505 problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2506 problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2507 problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2509 /* Discover which regno's use subregs, extracts or
2510 strict_low_parts. */
2514 FOR_BB_INSNS (bb, insn)
2518 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2519 df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2520 df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
2523 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2526 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2527 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2529 /* Allocate the slots for each regno. */
2530 for (regno = 0; regno < max_reg; regno++)
2533 problem_data->regno_start[regno] = index;
2534 if (bitmap_bit_p (problem_data->needs_expansion, regno))
2535 len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2539 problem_data->regno_len[regno] = len;
2543 df_byte_lr_expand_bitmap (problem_data->hardware_regs_used,
2544 df->hardware_regs_used);
2545 df_byte_lr_expand_bitmap (problem_data->invalidated_by_call,
2546 df_invalidated_by_call);
2548 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2550 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2553 bitmap_clear (bb_info->def);
2554 bitmap_clear (bb_info->use);
2558 bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool);
2559 df_byte_lr_set_bb_info (bb_index, bb_info);
2560 bb_info->use = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2561 bb_info->def = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2562 bb_info->in = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2563 bb_info->out = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2567 df_byte_lr->optional_p = true;
2571 /* Reset the global solution for recalculation. */
2574 df_byte_lr_reset (bitmap all_blocks)
2576 unsigned int bb_index;
2579 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2581 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2582 gcc_assert (bb_info);
2583 bitmap_clear (bb_info->in);
2584 bitmap_clear (bb_info->out);
2589 /* Compute local live register info for basic block BB. */
2592 df_byte_lr_bb_local_compute (unsigned int bb_index)
2594 struct df_byte_lr_problem_data *problem_data
2595 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2596 basic_block bb = BASIC_BLOCK (bb_index);
2597 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2599 struct df_ref **def_rec;
2600 struct df_ref **use_rec;
2602 /* Process the registers set in an exception handler. */
2603 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2605 struct df_ref *def = *def_rec;
2606 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2608 unsigned int dregno = DF_REF_REGNO (def);
2609 unsigned int start = problem_data->regno_start[dregno];
2610 unsigned int len = problem_data->regno_len[dregno];
2611 bitmap_set_range (bb_info->def, start, len);
2612 bitmap_clear_range (bb_info->use, start, len);
2616 /* Process the hardware registers that are always live. */
2617 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2619 struct df_ref *use = *use_rec;
2620 /* Add use to set of uses in this BB. */
2621 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2623 unsigned int uregno = DF_REF_REGNO (use);
2624 unsigned int start = problem_data->regno_start[uregno];
2625 unsigned int len = problem_data->regno_len[uregno];
2626 bitmap_set_range (bb_info->use, start, len);
2630 FOR_BB_INSNS_REVERSE (bb, insn)
2632 unsigned int uid = INSN_UID (insn);
2637 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2639 struct df_ref *def = *def_rec;
2640 /* If the def is to only part of the reg, it does
2641 not kill the other defs that reach here. */
2642 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2644 unsigned int dregno = DF_REF_REGNO (def);
2645 unsigned int start = problem_data->regno_start[dregno];
2646 unsigned int len = problem_data->regno_len[dregno];
2649 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2656 bitmap_set_range (bb_info->def, start, len);
2657 bitmap_clear_range (bb_info->use, start, len);
2662 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2664 struct df_ref *use = *use_rec;
2665 unsigned int uregno = DF_REF_REGNO (use);
2666 unsigned int start = problem_data->regno_start[uregno];
2667 unsigned int len = problem_data->regno_len[uregno];
2670 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2675 /* Add use to set of uses in this BB. */
2677 bitmap_set_range (bb_info->use, start, len);
2681 /* Process the registers set in an exception handler or the hard
2682 frame pointer if this block is the target of a non local
2684 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2686 struct df_ref *def = *def_rec;
2687 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2689 unsigned int dregno = DF_REF_REGNO (def);
2690 unsigned int start = problem_data->regno_start[dregno];
2691 unsigned int len = problem_data->regno_len[dregno];
2692 bitmap_set_range (bb_info->def, start, len);
2693 bitmap_clear_range (bb_info->use, start, len);
2698 /* Process the uses that are live into an exception handler. */
2699 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2701 struct df_ref *use = *use_rec;
2702 /* Add use to set of uses in this BB. */
2703 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2705 unsigned int uregno = DF_REF_REGNO (use);
2706 unsigned int start = problem_data->regno_start[uregno];
2707 unsigned int len = problem_data->regno_len[uregno];
2708 bitmap_set_range (bb_info->use, start, len);
2715 /* Compute local live register info for each basic block within BLOCKS. */
2718 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2720 unsigned int bb_index;
2723 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2725 if (bb_index == EXIT_BLOCK)
2727 /* The exit block is special for this problem and its bits are
2728 computed from thin air. */
2729 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2730 df_byte_lr_expand_bitmap (bb_info->use, df->exit_block_uses);
2733 df_byte_lr_bb_local_compute (bb_index);
2736 bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2740 /* Initialize the solution vectors. */
2743 df_byte_lr_init (bitmap all_blocks)
2745 unsigned int bb_index;
2748 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2750 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2751 bitmap_copy (bb_info->in, bb_info->use);
2752 bitmap_clear (bb_info->out);
2757 /* Confluence function that processes infinite loops. This might be a
2758 noreturn function that throws. And even if it isn't, getting the
2759 unwind info right helps debugging. */
2761 df_byte_lr_confluence_0 (basic_block bb)
2763 struct df_byte_lr_problem_data *problem_data
2764 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2765 bitmap op1 = df_byte_lr_get_bb_info (bb->index)->out;
2766 if (bb != EXIT_BLOCK_PTR)
2767 bitmap_copy (op1, problem_data->hardware_regs_used);
2771 /* Confluence function that ignores fake edges. */
2774 df_byte_lr_confluence_n (edge e)
2776 struct df_byte_lr_problem_data *problem_data
2777 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2778 bitmap op1 = df_byte_lr_get_bb_info (e->src->index)->out;
2779 bitmap op2 = df_byte_lr_get_bb_info (e->dest->index)->in;
2781 /* Call-clobbered registers die across exception and call edges. */
2782 /* ??? Abnormal call edges ignored for the moment, as this gets
2783 confused by sibling call edges, which crashes reg-stack. */
2784 if (e->flags & EDGE_EH)
2785 bitmap_ior_and_compl_into (op1, op2, problem_data->invalidated_by_call);
2787 bitmap_ior_into (op1, op2);
2789 bitmap_ior_into (op1, problem_data->hardware_regs_used);
2793 /* Transfer function. */
2796 df_byte_lr_transfer_function (int bb_index)
2798 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2799 bitmap in = bb_info->in;
2800 bitmap out = bb_info->out;
2801 bitmap use = bb_info->use;
2802 bitmap def = bb_info->def;
2804 return bitmap_ior_and_compl (in, use, out, def);
2808 /* Free all storage associated with the problem. */
2811 df_byte_lr_free (void)
2813 struct df_byte_lr_problem_data *problem_data
2814 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2817 if (df_byte_lr->block_info)
2819 free_alloc_pool (df_byte_lr->block_pool);
2820 df_byte_lr->block_info_size = 0;
2821 free (df_byte_lr->block_info);
2824 BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2825 bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2826 free (problem_data->regno_start);
2827 free (problem_data->regno_len);
2828 free (problem_data);
2833 /* Debugging info at top of bb. */
2836 df_byte_lr_top_dump (basic_block bb, FILE *file)
2838 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2839 if (!bb_info || !bb_info->in)
2842 fprintf (file, ";; blr in \t");
2843 df_print_byte_regset (file, bb_info->in);
2844 fprintf (file, ";; blr use \t");
2845 df_print_byte_regset (file, bb_info->use);
2846 fprintf (file, ";; blr def \t");
2847 df_print_byte_regset (file, bb_info->def);
2851 /* Debugging info at bottom of bb. */
2854 df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2856 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2857 if (!bb_info || !bb_info->out)
2860 fprintf (file, ";; blr out \t");
2861 df_print_byte_regset (file, bb_info->out);
2865 /* All of the information associated with every instance of the problem. */
2867 static struct df_problem problem_BYTE_LR =
2869 DF_BYTE_LR, /* Problem id. */
2870 DF_BACKWARD, /* Direction. */
2871 df_byte_lr_alloc, /* Allocate the problem specific data. */
2872 df_byte_lr_reset, /* Reset global information. */
2873 df_byte_lr_free_bb_info, /* Free basic block info. */
2874 df_byte_lr_local_compute, /* Local compute function. */
2875 df_byte_lr_init, /* Init the solution specific data. */
2876 df_worklist_dataflow, /* Worklist solver. */
2877 df_byte_lr_confluence_0, /* Confluence operator 0. */
2878 df_byte_lr_confluence_n, /* Confluence operator n. */
2879 df_byte_lr_transfer_function, /* Transfer function. */
2880 NULL, /* Finalize function. */
2881 df_byte_lr_free, /* Free all of the problem information. */
2882 df_byte_lr_free, /* Remove this problem from the stack of dataflow problems. */
2883 NULL, /* Debugging. */
2884 df_byte_lr_top_dump, /* Debugging start block. */
2885 df_byte_lr_bottom_dump, /* Debugging end block. */
2886 NULL, /* Incremental solution verify start. */
2887 NULL, /* Incremental solution verify end. */
2888 NULL, /* Dependent problem. */
2889 TV_DF_BYTE_LR, /* Timing variable. */
2890 false /* Reset blocks on dropping out of blocks_to_analyze. */
2894 /* Create a new DATAFLOW instance and add it to an existing instance
2895 of DF. The returned structure is what is used to get at the
2899 df_byte_lr_add_problem (void)
2901 df_add_problem (&problem_BYTE_LR);
2902 /* These will be initialized when df_scan_blocks processes each
2904 df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2908 /* Simulate the effects of the defs of INSN on LIVE. */
2911 df_byte_lr_simulate_defs (rtx insn, bitmap live)
2913 struct df_byte_lr_problem_data *problem_data
2914 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2915 struct df_ref **def_rec;
2916 unsigned int uid = INSN_UID (insn);
2918 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2920 struct df_ref *def = *def_rec;
2922 /* If the def is to only part of the reg, it does
2923 not kill the other defs that reach here. */
2924 if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2926 unsigned int dregno = DF_REF_REGNO (def);
2927 unsigned int start = problem_data->regno_start[dregno];
2928 unsigned int len = problem_data->regno_len[dregno];
2931 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2938 bitmap_clear_range (live, start, len);
2944 /* Simulate the effects of the uses of INSN on LIVE. */
2947 df_byte_lr_simulate_uses (rtx insn, bitmap live)
2949 struct df_byte_lr_problem_data *problem_data
2950 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2951 struct df_ref **use_rec;
2952 unsigned int uid = INSN_UID (insn);
2954 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2956 struct df_ref *use = *use_rec;
2957 unsigned int uregno = DF_REF_REGNO (use);
2958 unsigned int start = problem_data->regno_start[uregno];
2959 unsigned int len = problem_data->regno_len[uregno];
2963 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2969 /* Add use to set of uses in this BB. */
2971 bitmap_set_range (live, start, len);
2976 /* Apply the artificial uses and defs at the top of BB in a forwards
2980 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2982 struct df_byte_lr_problem_data *problem_data
2983 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2984 struct df_ref **def_rec;
2986 struct df_ref **use_rec;
2988 int bb_index = bb->index;
2991 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2993 struct df_ref *use = *use_rec;
2994 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2996 unsigned int uregno = DF_REF_REGNO (use);
2997 unsigned int start = problem_data->regno_start[uregno];
2998 unsigned int len = problem_data->regno_len[uregno];
2999 bitmap_set_range (live, start, len);
3004 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3006 struct df_ref *def = *def_rec;
3007 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3009 unsigned int dregno = DF_REF_REGNO (def);
3010 unsigned int start = problem_data->regno_start[dregno];
3011 unsigned int len = problem_data->regno_len[dregno];
3012 bitmap_clear_range (live, start, len);
3018 /* Apply the artificial uses and defs at the end of BB in a backwards
3022 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3024 struct df_byte_lr_problem_data *problem_data
3025 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
3026 struct df_ref **def_rec;
3027 struct df_ref **use_rec;
3028 int bb_index = bb->index;
3030 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3032 struct df_ref *def = *def_rec;
3033 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3035 unsigned int dregno = DF_REF_REGNO (def);
3036 unsigned int start = problem_data->regno_start[dregno];
3037 unsigned int len = problem_data->regno_len[dregno];
3038 bitmap_clear_range (live, start, len);
3042 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3044 struct df_ref *use = *use_rec;
3045 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3047 unsigned int uregno = DF_REF_REGNO (use);
3048 unsigned int start = problem_data->regno_start[uregno];
3049 unsigned int len = problem_data->regno_len[uregno];
3050 bitmap_set_range (live, start, len);
3057 /*----------------------------------------------------------------------------
3058 This problem computes REG_DEAD and REG_UNUSED notes.
3059 ----------------------------------------------------------------------------*/
3062 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3064 df_note->optional_p = true;
3067 #ifdef REG_DEAD_DEBUGGING
3069 df_print_note (const char *prefix, rtx insn, rtx note)
3073 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3074 print_rtl (dump_file, note);
3075 fprintf (dump_file, "\n");
3081 /* After reg-stack, the x86 floating point stack regs are difficult to
3082 analyze because of all of the pushes, pops and rotations. Thus, we
3083 just leave the notes alone. */
3087 df_ignore_stack_reg (int regno)
3089 return regstack_completed
3090 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3094 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3101 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3102 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3105 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3107 rtx *pprev = ®_NOTES (insn);
3114 switch (REG_NOTE_KIND (link))
3117 /* After reg-stack, we need to ignore any unused notes
3118 for the stack registers. */
3119 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3121 pprev = &XEXP (link, 1);
3126 rtx next = XEXP (link, 1);
3127 #ifdef REG_DEAD_DEBUGGING
3128 df_print_note ("deleting: ", insn, link);
3130 XEXP (link, 1) = dead;
3132 *pprev = link = next;
3137 /* After reg-stack, we need to ignore any unused notes
3138 for the stack registers. */
3139 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3141 pprev = &XEXP (link, 1);
3146 rtx next = XEXP (link, 1);
3147 #ifdef REG_DEAD_DEBUGGING
3148 df_print_note ("deleting: ", insn, link);
3150 XEXP (link, 1) = unused;
3152 *pprev = link = next;
3157 pprev = &XEXP (link, 1);
3163 *old_dead_notes = dead;
3164 *old_unused_notes = unused;
3168 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3169 list, otherwise create a new one. */
3172 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3178 if (XEXP (this, 0) == reg)
3181 XEXP (prev, 1) = XEXP (this, 1);
3183 old = XEXP (this, 1);
3184 XEXP (this, 1) = REG_NOTES (insn);
3185 REG_NOTES (insn) = this;
3191 this = XEXP (this, 1);
3194 /* Did not find the note. */
3195 REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
3199 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3200 arguments. Return true if the register value described by MWS's
3201 mw_reg is known to be completely unused, and if mw_reg can therefore
3202 be used in a REG_UNUSED note. */
3205 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3206 bitmap live, bitmap artificial_uses)
3210 /* If MWS describes a partial reference, create REG_UNUSED notes for
3211 individual hard registers. */
3212 if (mws->flags & DF_REF_PARTIAL)
3215 /* Likewise if some part of the register is used. */
3216 for (r = mws->start_regno; r <= mws->end_regno; r++)
3217 if (bitmap_bit_p (live, r)
3218 || bitmap_bit_p (artificial_uses, r))
3221 gcc_assert (REG_P (mws->mw_reg));
3225 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3226 based on the bits in LIVE. Do not generate notes for registers in
3227 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3228 not generated if the reg is both read and written by the
3233 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3234 bitmap live, bitmap do_not_gen,
3235 bitmap artificial_uses)
3239 #ifdef REG_DEAD_DEBUGGING
3241 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3242 mws->start_regno, mws->end_regno);
3245 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3247 unsigned int regno = mws->start_regno;
3248 old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3250 #ifdef REG_DEAD_DEBUGGING
3251 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3253 bitmap_set_bit (do_not_gen, regno);
3254 /* Only do this if the value is totally dead. */
3257 for (r = mws->start_regno; r <= mws->end_regno; r++)
3259 if (!bitmap_bit_p (live, r)
3260 && !bitmap_bit_p (artificial_uses, r))
3262 old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3263 #ifdef REG_DEAD_DEBUGGING
3264 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3267 bitmap_set_bit (do_not_gen, r);
3273 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3274 arguments. Return true if the register value described by MWS's
3275 mw_reg is known to be completely dead, and if mw_reg can therefore
3276 be used in a REG_DEAD note. */
3279 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3280 bitmap live, bitmap artificial_uses,
3285 /* If MWS describes a partial reference, create REG_DEAD notes for
3286 individual hard registers. */
3287 if (mws->flags & DF_REF_PARTIAL)
3290 /* Likewise if some part of the register is not dead. */
3291 for (r = mws->start_regno; r <= mws->end_regno; r++)
3292 if (bitmap_bit_p (live, r)
3293 || bitmap_bit_p (artificial_uses, r)
3294 || bitmap_bit_p (do_not_gen, r))
3297 gcc_assert (REG_P (mws->mw_reg));
3301 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3302 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3303 from being set if the instruction both reads and writes the
3307 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3308 bitmap live, bitmap do_not_gen,
3309 bitmap artificial_uses)
3313 #ifdef REG_DEAD_DEBUGGING
3316 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3317 mws->start_regno, mws->end_regno);
3318 df_print_regset (dump_file, do_not_gen);
3319 fprintf (dump_file, " live =");
3320 df_print_regset (dump_file, live);
3321 fprintf (dump_file, " artificial uses =");
3322 df_print_regset (dump_file, artificial_uses);
3326 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3328 /* Add a dead note for the entire multi word register. */
3329 old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3330 #ifdef REG_DEAD_DEBUGGING
3331 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3336 for (r = mws->start_regno; r <= mws->end_regno; r++)
3337 if (!bitmap_bit_p (live, r)
3338 && !bitmap_bit_p (artificial_uses, r)
3339 && !bitmap_bit_p (do_not_gen, r))
3341 old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3342 #ifdef REG_DEAD_DEBUGGING
3343 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3351 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3352 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3355 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
3356 bitmap live, bitmap artificial_uses)
3358 unsigned int dregno = DF_REF_REGNO (def);
3360 #ifdef REG_DEAD_DEBUGGING
3363 fprintf (dump_file, " regular looking at def ");
3364 df_ref_debug (def, dump_file);
3368 if (!(bitmap_bit_p (live, dregno)
3369 || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3370 || bitmap_bit_p (artificial_uses, dregno)
3371 || df_ignore_stack_reg (dregno)))
3373 rtx reg = (DF_REF_LOC (def))
3374 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3375 old = df_set_note (REG_UNUSED, insn, old, reg);
3376 #ifdef REG_DEAD_DEBUGGING
3377 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3385 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3386 info: lifetime, bb, and number of defs and uses for basic block
3387 BB. The three bitvectors are scratch regs used here. */
3390 df_note_bb_compute (unsigned int bb_index,
3391 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3393 basic_block bb = BASIC_BLOCK (bb_index);
3395 struct df_ref **def_rec;
3396 struct df_ref **use_rec;
3398 bitmap_copy (live, df_get_live_out (bb));
3399 bitmap_clear (artificial_uses);
3401 #ifdef REG_DEAD_DEBUGGING
3404 fprintf (dump_file, "live at bottom ");
3405 df_print_regset (dump_file, live);
3409 /* Process the artificial defs and uses at the bottom of the block
3410 to begin processing. */
3411 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3413 struct df_ref *def = *def_rec;
3414 #ifdef REG_DEAD_DEBUGGING
3416 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3419 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3420 bitmap_clear_bit (live, DF_REF_REGNO (def));
3423 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3425 struct df_ref *use = *use_rec;
3426 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3428 unsigned int regno = DF_REF_REGNO (use);
3429 bitmap_set_bit (live, regno);
3431 /* Notes are not generated for any of the artificial registers
3432 at the bottom of the block. */
3433 bitmap_set_bit (artificial_uses, regno);
3437 #ifdef REG_DEAD_DEBUGGING
3440 fprintf (dump_file, "live before artificials out ");
3441 df_print_regset (dump_file, live);
3445 FOR_BB_INSNS_REVERSE (bb, insn)
3447 unsigned int uid = INSN_UID (insn);
3448 struct df_mw_hardreg **mws_rec;
3450 rtx old_unused_notes;
3455 bitmap_clear (do_not_gen);
3456 df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3458 /* Process the defs. */
3461 #ifdef REG_DEAD_DEBUGGING
3464 fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
3465 df_print_regset (dump_file, live);
3468 /* We only care about real sets for calls. Clobbers cannot
3469 be depended on to really die. */
3470 mws_rec = DF_INSN_UID_MWS (uid);
3473 struct df_mw_hardreg *mws = *mws_rec;
3474 if ((mws->type == DF_REF_REG_DEF)
3475 && !df_ignore_stack_reg (mws->start_regno))
3477 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3478 mws, live, do_not_gen,
3483 /* All of the defs except the return value are some sort of
3484 clobber. This code is for the return. */
3485 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3487 struct df_ref *def = *def_rec;
3488 unsigned int dregno = DF_REF_REGNO (def);
3489 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3492 = df_create_unused_note (insn, old_unused_notes,
3493 def, live, artificial_uses);
3494 bitmap_set_bit (do_not_gen, dregno);
3497 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3498 bitmap_clear_bit (live, dregno);
3504 mws_rec = DF_INSN_UID_MWS (uid);
3507 struct df_mw_hardreg *mws = *mws_rec;
3508 if (mws->type == DF_REF_REG_DEF)
3510 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3511 mws, live, do_not_gen,
3516 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3518 struct df_ref *def = *def_rec;
3519 unsigned int dregno = DF_REF_REGNO (def);
3521 = df_create_unused_note (insn, old_unused_notes,
3522 def, live, artificial_uses);
3524 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3525 bitmap_set_bit (do_not_gen, dregno);
3527 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3528 bitmap_clear_bit (live, dregno);
3532 /* Process the uses. */
3533 mws_rec = DF_INSN_UID_MWS (uid);
3536 struct df_mw_hardreg *mws = *mws_rec;
3537 if ((mws->type != DF_REF_REG_DEF)
3538 && !df_ignore_stack_reg (mws->start_regno))
3540 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3541 mws, live, do_not_gen,
3546 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3548 struct df_ref *use = *use_rec;
3549 unsigned int uregno = DF_REF_REGNO (use);
3551 #ifdef REG_DEAD_DEBUGGING
3554 fprintf (dump_file, " regular looking at use ");
3555 df_ref_debug (use, dump_file);
3558 if (!bitmap_bit_p (live, uregno))
3560 if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
3561 && (!bitmap_bit_p (do_not_gen, uregno))
3562 && (!bitmap_bit_p (artificial_uses, uregno))
3563 && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
3564 && (!df_ignore_stack_reg (uregno)))
3566 rtx reg = (DF_REF_LOC (use))
3567 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3568 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3570 #ifdef REG_DEAD_DEBUGGING
3571 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3574 /* This register is now live. */
3575 bitmap_set_bit (live, uregno);
3579 while (old_unused_notes)
3581 rtx next = XEXP (old_unused_notes, 1);
3582 free_EXPR_LIST_node (old_unused_notes);
3583 old_unused_notes = next;
3585 while (old_dead_notes)
3587 rtx next = XEXP (old_dead_notes, 1);
3588 free_EXPR_LIST_node (old_dead_notes);
3589 old_dead_notes = next;
3595 /* Compute register info: lifetime, bb, and number of defs and uses. */
3597 df_note_compute (bitmap all_blocks)
3599 unsigned int bb_index;
3601 bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
3602 bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
3603 bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3605 #ifdef REG_DEAD_DEBUGGING
3607 print_rtl_with_bb (dump_file, get_insns());
3610 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3612 df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
3616 BITMAP_FREE (do_not_gen);
3617 BITMAP_FREE (artificial_uses);
3621 /* Free all storage associated with the problem. */
3630 /* All of the information associated every instance of the problem. */
3632 static struct df_problem problem_NOTE =
3634 DF_NOTE, /* Problem id. */
3635 DF_NONE, /* Direction. */
3636 df_note_alloc, /* Allocate the problem specific data. */
3637 NULL, /* Reset global information. */
3638 NULL, /* Free basic block info. */
3639 df_note_compute, /* Local compute function. */
3640 NULL, /* Init the solution specific data. */
3641 NULL, /* Iterative solver. */
3642 NULL, /* Confluence operator 0. */
3643 NULL, /* Confluence operator n. */
3644 NULL, /* Transfer function. */
3645 NULL, /* Finalize function. */
3646 df_note_free, /* Free all of the problem information. */
3647 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3648 NULL, /* Debugging. */
3649 NULL, /* Debugging start block. */
3650 NULL, /* Debugging end block. */
3651 NULL, /* Incremental solution verify start. */
3652 NULL, /* Incremental solution verify end. */
3653 &problem_LR, /* Dependent problem. */
3654 TV_DF_NOTE, /* Timing variable. */
3655 false /* Reset blocks on dropping out of blocks_to_analyze. */
3659 /* Create a new DATAFLOW instance and add it to an existing instance
3660 of DF. The returned structure is what is used to get at the
3664 df_note_add_problem (void)
3666 df_add_problem (&problem_NOTE);
3672 /*----------------------------------------------------------------------------
3673 Functions for simulating the effects of single insns.
3675 You can either simulate in the forwards direction, starting from
3676 the top of a block or the backwards direction from the end of the
3677 block. The main difference is that if you go forwards, the uses
3678 are examined first then the defs, and if you go backwards, the defs
3679 are examined first then the uses.
3681 If you start at the top of the block, use one of DF_LIVE_IN or
3682 DF_LR_IN. If you start at the bottom of the block use one of
3683 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3684 THEY WILL BE DESTROYED.
3685 ----------------------------------------------------------------------------*/
3688 /* Find the set of DEFs for INSN. */
3691 df_simulate_find_defs (rtx insn, bitmap defs)
3693 struct df_ref **def_rec;
3694 unsigned int uid = INSN_UID (insn);
3696 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3698 struct df_ref *def = *def_rec;
3699 /* If the def is to only part of the reg, it does
3700 not kill the other defs that reach here. */
3701 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3702 bitmap_set_bit (defs, DF_REF_REGNO (def));
3707 /* Simulate the effects of the defs of INSN on LIVE. */
3710 df_simulate_defs (rtx insn, bitmap live)
3712 struct df_ref **def_rec;
3713 unsigned int uid = INSN_UID (insn);
3715 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3717 struct df_ref *def = *def_rec;
3718 unsigned int dregno = DF_REF_REGNO (def);
3720 /* If the def is to only part of the reg, it does
3721 not kill the other defs that reach here. */
3722 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3723 bitmap_clear_bit (live, dregno);
3728 /* Simulate the effects of the uses of INSN on LIVE. */
3731 df_simulate_uses (rtx insn, bitmap live)
3733 struct df_ref **use_rec;
3734 unsigned int uid = INSN_UID (insn);
3736 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3738 struct df_ref *use = *use_rec;
3739 /* Add use to set of uses in this BB. */
3740 bitmap_set_bit (live, DF_REF_REGNO (use));
3745 /* Add back the always live regs in BB to LIVE. */
3748 df_simulate_fixup_sets (basic_block bb, bitmap live)
3750 /* These regs are considered always live so if they end up dying
3751 because of some def, we need to bring the back again. */
3752 if (bb_has_eh_pred (bb))
3753 bitmap_ior_into (live, df->eh_block_artificial_uses);
3755 bitmap_ior_into (live, df->regular_block_artificial_uses);
3759 /*----------------------------------------------------------------------------
3760 The following three functions are used only for BACKWARDS scanning:
3761 i.e. they process the defs before the uses.
3763 df_simulate_artificial_refs_at_end should be called first with a
3764 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3765 df_simulate_one_insn should be called for each insn in the block,
3766 starting with the last on. Finally,
3767 df_simulate_artificial_refs_at_top can be called to get a new value
3768 of the sets at the top of the block (this is rarely used).
3770 It would be not be difficult to define a similar set of functions
3771 that work in the forwards direction. In that case the functions
3772 would ignore the use sets and look for the REG_DEAD and REG_UNUSED
3774 ----------------------------------------------------------------------------*/
3776 /* Apply the artificial uses and defs at the end of BB in a backwards
3780 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3782 struct df_ref **def_rec;
3783 struct df_ref **use_rec;
3784 int bb_index = bb->index;
3786 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3788 struct df_ref *def = *def_rec;
3789 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3790 bitmap_clear_bit (live, DF_REF_REGNO (def));
3793 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3795 struct df_ref *use = *use_rec;
3796 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3797 bitmap_set_bit (live, DF_REF_REGNO (use));
3802 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3805 df_simulate_one_insn (basic_block bb, rtx insn, bitmap live)
3807 if (! INSN_P (insn))
3810 df_simulate_defs (insn, live);
3811 df_simulate_uses (insn, live);
3812 df_simulate_fixup_sets (bb, live);
3816 /* Apply the artificial uses and defs at the top of BB in a backwards
3820 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3822 struct df_ref **def_rec;
3824 struct df_ref **use_rec;
3826 int bb_index = bb->index;
3828 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3830 struct df_ref *def = *def_rec;
3831 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3832 bitmap_clear_bit (live, DF_REF_REGNO (def));
3836 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3838 struct df_ref *use = *use_rec;
3839 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3840 bitmap_set_bit (live, DF_REF_REGNO (use));