1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 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 2, 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 COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
28 #include "coretypes.h"
32 #include "insn-config.h"
37 #include "alloc-pool.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
50 #define REG_DEAD_DEBUGGING
53 #define DF_SPARSE_THRESHOLD 32
55 static bitmap seen_in_block = NULL;
56 static bitmap seen_in_insn = NULL;
59 /*----------------------------------------------------------------------------
60 Public functions access functions for the dataflow problems.
61 ----------------------------------------------------------------------------*/
62 /* Get the live at out set for BB no matter what problem happens to be
63 defined. This function is used by the register allocators who
64 choose different dataflow problems depending on the optimization
68 df_get_live_out (basic_block bb)
73 return DF_RA_LIVE_OUT (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_RA_LIVE_IN (bb);
93 return DF_LIVE_IN (bb);
98 /* Get the live at top set for BB no matter what problem happens to be
99 defined. This function is used by the register allocators who
100 choose different dataflow problems depending on the optimization
104 df_get_live_top (basic_block bb)
109 return DF_RA_LIVE_TOP (bb);
111 return DF_LR_TOP (bb);
115 /*----------------------------------------------------------------------------
117 ----------------------------------------------------------------------------*/
119 /* Generic versions to get the void* version of the block info. Only
120 used inside the problem instance vectors. */
122 /* Grow the bb_info array. */
125 df_grow_bb_info (struct dataflow *dflow)
127 unsigned int new_size = last_basic_block + 1;
128 if (dflow->block_info_size < new_size)
130 new_size += new_size / 4;
131 dflow->block_info = xrealloc (dflow->block_info,
132 new_size *sizeof (void*));
133 memset (dflow->block_info + dflow->block_info_size, 0,
134 (new_size - dflow->block_info_size) *sizeof (void *));
135 dflow->block_info_size = new_size;
139 /* Dump a def-use or use-def chain for REF to FILE. */
142 df_chain_dump (struct df_link *link, FILE *file)
144 fprintf (file, "{ ");
145 for (; link; link = link->next)
147 fprintf (file, "%c%d(bb %d insn %d) ",
148 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
149 DF_REF_ID (link->ref),
150 DF_REF_BBNO (link->ref),
151 DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
157 /* Print some basic block info as part of df_dump. */
160 df_print_bb_index (basic_block bb, FILE *file)
165 fprintf (file, "\n( ");
166 FOR_EACH_EDGE (e, ei, bb->preds)
168 basic_block pred = e->src;
169 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
171 fprintf (file, ")->[%d]->( ", bb->index);
172 FOR_EACH_EDGE (e, ei, bb->succs)
174 basic_block succ = e->dest;
175 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
177 fprintf (file, ")\n");
182 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
188 seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
189 seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
196 BITMAP_FREE (seen_in_block);
197 BITMAP_FREE (seen_in_insn);
202 /*----------------------------------------------------------------------------
205 Find the locations in the function where each use site for a pseudo
206 can reach backwards. In and out bitvectors are built for each basic
207 block. The id field in the ref is used to index into these sets.
208 See df.h for details.
210 ----------------------------------------------------------------------------*/
212 /* This problem plays a large number of games for the sake of
215 1) The order of the bits in the bitvectors. After the scanning
216 phase, all of the uses are sorted. All of the uses for the reg 0
217 are first, followed by all uses for reg 1 and so on.
219 2) There are two kill sets, one if the number of uses is less or
220 equal to DF_SPARSE_THRESHOLD and another if it is greater.
222 <= : Data is built directly in the kill set.
224 > : One level of indirection is used to keep from generating long
225 strings of 1 bits in the kill sets. Bitvectors that are indexed
226 by the regnum are used to represent that there is a killing def
227 for the register. The confluence and transfer functions use
228 these along with the bitmap_clear_range call to remove ranges of
229 bits without actually generating a knockout vector.
231 The kill and sparse_kill and the dense_invalidated_by_call and
232 sparse_invalidated_by_call both play this game. */
234 /* Private data used to compute the solution for this problem. These
235 data structures are not accessible outside of this module. */
236 struct df_ru_problem_data
238 /* The set of defs to regs invalidated by call. */
239 bitmap sparse_invalidated_by_call;
240 /* The set of defs to regs invalidated by call for ru. */
241 bitmap dense_invalidated_by_call;
242 /* An obstack for the bitmaps we need for this problem. */
243 bitmap_obstack ru_bitmaps;
246 /* Set basic block info. */
249 df_ru_set_bb_info (unsigned int index, struct df_ru_bb_info *bb_info)
252 gcc_assert (index < df_ru->block_info_size);
253 df_ru->block_info[index] = bb_info;
257 /* Free basic block info. */
260 df_ru_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
263 struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
266 BITMAP_FREE (bb_info->kill);
267 BITMAP_FREE (bb_info->sparse_kill);
268 BITMAP_FREE (bb_info->gen);
269 BITMAP_FREE (bb_info->in);
270 BITMAP_FREE (bb_info->out);
271 pool_free (df_ru->block_pool, bb_info);
276 /* Allocate or reset bitmaps for DF_RU blocks. The solution bits are
277 not touched unless the block is new. */
280 df_ru_alloc (bitmap all_blocks)
282 unsigned int bb_index;
284 struct df_ru_problem_data *problem_data;
286 if (!df_ru->block_pool)
287 df_ru->block_pool = create_alloc_pool ("df_ru_block pool",
288 sizeof (struct df_ru_bb_info), 50);
290 if (df_ru->problem_data)
292 problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
293 bitmap_clear (problem_data->sparse_invalidated_by_call);
294 bitmap_clear (problem_data->dense_invalidated_by_call);
298 problem_data = XNEW (struct df_ru_problem_data);
299 df_ru->problem_data = problem_data;
301 bitmap_obstack_initialize (&problem_data->ru_bitmaps);
302 problem_data->sparse_invalidated_by_call
303 = BITMAP_ALLOC (&problem_data->ru_bitmaps);
304 problem_data->dense_invalidated_by_call
305 = BITMAP_ALLOC (&problem_data->ru_bitmaps);
308 df_grow_bb_info (df_ru);
310 /* Because of the clustering of all def sites for the same pseudo,
311 we have to process all of the blocks before doing the
314 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
316 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
319 bitmap_clear (bb_info->kill);
320 bitmap_clear (bb_info->sparse_kill);
321 bitmap_clear (bb_info->gen);
325 bb_info = (struct df_ru_bb_info *) pool_alloc (df_ru->block_pool);
326 df_ru_set_bb_info (bb_index, bb_info);
327 bb_info->kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
328 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
329 bb_info->gen = BITMAP_ALLOC (&problem_data->ru_bitmaps);
330 bb_info->in = BITMAP_ALLOC (&problem_data->ru_bitmaps);
331 bb_info->out = BITMAP_ALLOC (&problem_data->ru_bitmaps);
337 /* Process a list of DEFs for df_ru_bb_local_compute. */
340 df_ru_bb_local_compute_process_def (struct df_ru_bb_info *bb_info,
341 struct df_ref **def_rec,
342 enum df_ref_flags top_flag)
346 struct df_ref *def = *def_rec;
347 if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
348 /* If the def is to only part of the reg, it is as if it did
349 not happen, since some of the bits may get thru. */
350 && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
352 unsigned int regno = DF_REF_REGNO (def);
353 unsigned int begin = DF_USES_BEGIN (regno);
354 unsigned int n_uses = DF_USES_COUNT (regno);
356 if (!bitmap_bit_p (seen_in_block, regno))
358 /* The first def for regno in the insn, causes the kill
359 info to be generated. Do not modify the gen set
360 because the only values in it are the uses from here
361 to the top of the block and this def does not effect
363 if (!bitmap_bit_p (seen_in_insn, regno))
365 if (n_uses > DF_SPARSE_THRESHOLD)
366 bitmap_set_bit (bb_info->sparse_kill, regno);
368 bitmap_set_range (bb_info->kill, begin, n_uses);
370 bitmap_set_bit (seen_in_insn, regno);
378 /* Process a list of USEs for df_ru_bb_local_compute. */
381 df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info,
382 struct df_ref **use_rec,
383 enum df_ref_flags top_flag)
387 struct df_ref *use = *use_rec;
388 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
390 /* Add use to set of gens in this BB unless we have seen a
391 def in a previous instruction. */
392 unsigned int regno = DF_REF_REGNO (use);
393 if (!bitmap_bit_p (seen_in_block, regno))
394 bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
400 /* Compute local reaching use (upward exposed use) info for basic
401 block BB. USE_INFO->REGS[R] caches the set of uses for register R. */
403 df_ru_bb_local_compute (unsigned int bb_index)
405 basic_block bb = BASIC_BLOCK (bb_index);
406 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
409 /* Set when a def for regno is seen. */
410 bitmap_clear (seen_in_block);
411 bitmap_clear (seen_in_insn);
414 /* Variables defined in the prolog that are used by the exception
416 df_ru_bb_local_compute_process_use (bb_info,
417 df_get_artificial_uses (bb_index),
420 df_ru_bb_local_compute_process_def (bb_info,
421 df_get_artificial_defs (bb_index),
424 FOR_BB_INSNS (bb, insn)
426 unsigned int uid = INSN_UID (insn);
430 df_ru_bb_local_compute_process_use (bb_info,
431 DF_INSN_UID_USES (uid), 0);
433 if (df->changeable_flags & DF_EQ_NOTES)
434 df_ru_bb_local_compute_process_use (bb_info,
435 DF_INSN_UID_EQ_USES (uid), 0);
437 df_ru_bb_local_compute_process_def (bb_info,
438 DF_INSN_UID_DEFS (uid), 0);
440 bitmap_ior_into (seen_in_block, seen_in_insn);
441 bitmap_clear (seen_in_insn);
444 /* Process the hardware registers that are always live. */
445 df_ru_bb_local_compute_process_use (bb_info,
446 df_get_artificial_uses (bb_index), 0);
448 df_ru_bb_local_compute_process_def (bb_info,
449 df_get_artificial_defs (bb_index), 0);
453 /* Compute local reaching use (upward exposed use) info for each basic
454 block within BLOCKS. */
456 df_ru_local_compute (bitmap all_blocks)
458 unsigned int bb_index;
461 struct df_ru_problem_data *problem_data
462 = (struct df_ru_problem_data *) df_ru->problem_data;
463 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
464 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
468 df_maybe_reorganize_use_refs (df->changeable_flags & DF_EQ_NOTES ?
469 DF_REF_ORDER_BY_REG_WITH_NOTES : DF_REF_ORDER_BY_REG);
471 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
473 df_ru_bb_local_compute (bb_index);
476 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
477 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
479 if (DF_USES_COUNT (regno) > DF_SPARSE_THRESHOLD)
480 bitmap_set_bit (sparse_invalidated, regno);
482 bitmap_set_range (dense_invalidated,
483 DF_USES_BEGIN (regno),
484 DF_USES_COUNT (regno));
491 /* Initialize the solution bit vectors for problem. */
494 df_ru_init_solution (bitmap all_blocks)
496 unsigned int bb_index;
499 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
501 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
502 bitmap_copy (bb_info->in, bb_info->gen);
503 bitmap_clear (bb_info->out);
508 /* Out of target gets or of in of source. */
511 df_ru_confluence_n (edge e)
513 bitmap op1 = df_ru_get_bb_info (e->src->index)->out;
514 bitmap op2 = df_ru_get_bb_info (e->dest->index)->in;
516 if (e->flags & EDGE_EH)
518 struct df_ru_problem_data *problem_data
519 = (struct df_ru_problem_data *) df_ru->problem_data;
520 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
521 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
524 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
526 bitmap_copy (tmp, op2);
527 bitmap_and_compl_into (tmp, dense_invalidated);
529 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
531 bitmap_clear_range (tmp,
532 DF_USES_BEGIN (regno),
533 DF_USES_COUNT (regno));
535 bitmap_ior_into (op1, tmp);
539 bitmap_ior_into (op1, op2);
543 /* Transfer function. */
546 df_ru_transfer_function (int bb_index)
548 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
551 bitmap in = bb_info->in;
552 bitmap out = bb_info->out;
553 bitmap gen = bb_info->gen;
554 bitmap kill = bb_info->kill;
555 bitmap sparse_kill = bb_info->sparse_kill;
557 if (bitmap_empty_p (sparse_kill))
558 return bitmap_ior_and_compl (in, gen, out, kill);
561 struct df_ru_problem_data *problem_data;
563 bool changed = false;
565 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
566 IN with TMP. Therefore, allocate TMP in the RU bitmaps obstack. */
567 problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
568 tmp = BITMAP_ALLOC (&problem_data->ru_bitmaps);
570 bitmap_copy (tmp, out);
571 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
573 bitmap_clear_range (tmp,
574 DF_USES_BEGIN (regno),
575 DF_USES_COUNT (regno));
577 bitmap_and_compl_into (tmp, kill);
578 bitmap_ior_into (tmp, gen);
579 changed = !bitmap_equal_p (tmp, in);
592 /* Free all storage associated with the problem. */
598 struct df_ru_problem_data *problem_data
599 = (struct df_ru_problem_data *) df_ru->problem_data;
603 for (i = 0; i < df_ru->block_info_size; i++)
605 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (i);
608 BITMAP_FREE (bb_info->kill);
609 BITMAP_FREE (bb_info->sparse_kill);
610 BITMAP_FREE (bb_info->gen);
611 BITMAP_FREE (bb_info->in);
612 BITMAP_FREE (bb_info->out);
616 free_alloc_pool (df_ru->block_pool);
617 BITMAP_FREE (problem_data->sparse_invalidated_by_call);
618 BITMAP_FREE (problem_data->dense_invalidated_by_call);
619 bitmap_obstack_release (&problem_data->ru_bitmaps);
621 df_ru->block_info_size = 0;
622 free (df_ru->block_info);
623 free (df_ru->problem_data);
629 /* Debugging info. */
632 df_ru_start_dump (FILE *file)
634 struct df_ru_problem_data *problem_data
635 = (struct df_ru_problem_data *) df_ru->problem_data;
636 unsigned int m = DF_REG_SIZE(df);
639 if (!df_ru->block_info)
642 fprintf (file, ";; Reaching uses:\n");
644 fprintf (file, ";; sparse invalidated \t");
645 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
646 fprintf (file, " dense invalidated \t");
647 dump_bitmap (file, problem_data->dense_invalidated_by_call);
649 for (regno = 0; regno < m; regno++)
650 if (DF_USES_COUNT (regno))
651 fprintf (file, "%d[%d,%d] ", regno,
652 DF_USES_BEGIN (regno),
653 DF_USES_COUNT (regno));
654 fprintf (file, "\n");
658 /* Debugging info at top of bb. */
661 df_ru_top_dump (basic_block bb, FILE *file)
663 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
664 if (!bb_info || !bb_info->in)
667 fprintf (file, ";; ru in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
668 dump_bitmap (file, bb_info->in);
669 fprintf (file, ";; ru gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
670 dump_bitmap (file, bb_info->gen);
671 fprintf (file, ";; ru kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
672 dump_bitmap (file, bb_info->kill);
676 /* Debugging info at bottom of bb. */
679 df_ru_bottom_dump (basic_block bb, FILE *file)
681 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
682 if (!bb_info || !bb_info->out)
685 fprintf (file, ";; ru out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
686 dump_bitmap (file, bb_info->out);
690 /* All of the information associated with every instance of the problem. */
692 static struct df_problem problem_RU =
694 DF_RU, /* Problem id. */
695 DF_BACKWARD, /* Direction. */
696 df_ru_alloc, /* Allocate the problem specific data. */
697 NULL, /* Reset global information. */
698 df_ru_free_bb_info, /* Free basic block info. */
699 df_ru_local_compute, /* Local compute function. */
700 df_ru_init_solution, /* Init the solution specific data. */
701 df_worklist_dataflow, /* Worklist solver. */
702 NULL, /* Confluence operator 0. */
703 df_ru_confluence_n, /* Confluence operator n. */
704 df_ru_transfer_function, /* Transfer function. */
705 NULL, /* Finalize function. */
706 df_ru_free, /* Free all of the problem information. */
707 df_ru_free, /* Remove this problem from the stack of dataflow problems. */
708 df_ru_start_dump, /* Debugging. */
709 df_ru_top_dump, /* Debugging start block. */
710 df_ru_bottom_dump, /* Debugging end block. */
711 NULL, /* Incremental solution verify start. */
712 NULL, /* Incremental solution verfiy end. */
713 NULL, /* Dependent problem. */
714 TV_DF_RU /* Timing variable. */
719 /* Create a new DATAFLOW instance and add it to an existing instance
720 of DF. The returned structure is what is used to get at the
724 df_ru_add_problem (void)
726 df_add_problem (&problem_RU);
730 /*----------------------------------------------------------------------------
733 Find the locations in the function where each definition site for a
734 pseudo reaches. In and out bitvectors are built for each basic
735 block. The id field in the ref is used to index into these sets.
736 See df.h for details.
737 ----------------------------------------------------------------------------*/
739 /* See the comment at the top of the Reaching Uses problem for how the
740 uses are represented in the kill sets. The same games are played
741 here for the defs. */
743 /* Private data used to compute the solution for this problem. These
744 data structures are not accessible outside of this module. */
745 struct df_rd_problem_data
747 /* The set of defs to regs invalidated by call. */
748 bitmap sparse_invalidated_by_call;
749 /* The set of defs to regs invalidate by call for rd. */
750 bitmap dense_invalidated_by_call;
751 /* An obstack for the bitmaps we need for this problem. */
752 bitmap_obstack rd_bitmaps;
755 /* Set basic block info. */
758 df_rd_set_bb_info (unsigned int index,
759 struct df_rd_bb_info *bb_info)
762 gcc_assert (index < df_rd->block_info_size);
763 df_rd->block_info[index] = bb_info;
767 /* Free basic block info. */
770 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
773 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
776 BITMAP_FREE (bb_info->kill);
777 BITMAP_FREE (bb_info->sparse_kill);
778 BITMAP_FREE (bb_info->gen);
779 BITMAP_FREE (bb_info->in);
780 BITMAP_FREE (bb_info->out);
781 pool_free (df_rd->block_pool, bb_info);
786 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
787 not touched unless the block is new. */
790 df_rd_alloc (bitmap all_blocks)
792 unsigned int bb_index;
794 struct df_rd_problem_data *problem_data;
796 if (!df_rd->block_pool)
797 df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
798 sizeof (struct df_rd_bb_info), 50);
800 if (df_rd->problem_data)
802 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
803 bitmap_clear (problem_data->sparse_invalidated_by_call);
804 bitmap_clear (problem_data->dense_invalidated_by_call);
808 problem_data = XNEW (struct df_rd_problem_data);
809 df_rd->problem_data = problem_data;
811 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
812 problem_data->sparse_invalidated_by_call
813 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
814 problem_data->dense_invalidated_by_call
815 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
818 df_grow_bb_info (df_rd);
820 /* Because of the clustering of all use sites for the same pseudo,
821 we have to process all of the blocks before doing the
824 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
826 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
829 bitmap_clear (bb_info->kill);
830 bitmap_clear (bb_info->sparse_kill);
831 bitmap_clear (bb_info->gen);
835 bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
836 df_rd_set_bb_info (bb_index, bb_info);
837 bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
838 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
839 bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
840 bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
841 bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
847 /* Process a list of DEFs for df_rd_bb_local_compute. */
850 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
851 struct df_ref **def_rec,
852 enum df_ref_flags top_flag)
856 struct df_ref *def = *def_rec;
857 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
859 unsigned int regno = DF_REF_REGNO (def);
860 unsigned int begin = DF_DEFS_BEGIN (regno);
861 unsigned int n_defs = DF_DEFS_COUNT (regno);
863 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
864 || (regno >= FIRST_PSEUDO_REGISTER))
866 /* Only the last def(s) for a regno in the block has any
868 if (!bitmap_bit_p (seen_in_block, regno))
870 /* The first def for regno in insn gets to knock out the
871 defs from other instructions. */
872 if ((!bitmap_bit_p (seen_in_insn, regno))
873 /* If the def is to only part of the reg, it does
874 not kill the other defs that reach here. */
875 && (!(DF_REF_FLAGS (def) &
876 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
878 if (n_defs > DF_SPARSE_THRESHOLD)
880 bitmap_set_bit (bb_info->sparse_kill, regno);
881 bitmap_clear_range(bb_info->gen, begin, n_defs);
885 bitmap_set_range (bb_info->kill, begin, n_defs);
886 bitmap_clear_range (bb_info->gen, begin, n_defs);
890 bitmap_set_bit (seen_in_insn, regno);
891 /* All defs for regno in the instruction may be put into
893 if (!(DF_REF_FLAGS (def)
894 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
895 bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
903 /* Compute local reaching def info for basic block BB. */
906 df_rd_bb_local_compute (unsigned int bb_index)
908 basic_block bb = BASIC_BLOCK (bb_index);
909 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
912 bitmap_clear (seen_in_block);
913 bitmap_clear (seen_in_insn);
915 /* Artificials are only hard regs. */
916 if (!(df->changeable_flags & DF_NO_HARD_REGS))
917 df_rd_bb_local_compute_process_def (bb_info,
918 df_get_artificial_defs (bb_index),
921 FOR_BB_INSNS_REVERSE (bb, insn)
923 unsigned int uid = INSN_UID (insn);
928 df_rd_bb_local_compute_process_def (bb_info,
929 DF_INSN_UID_DEFS (uid), 0);
931 /* This complex dance with the two bitmaps is required because
932 instructions can assign twice to the same pseudo. This
933 generally happens with calls that will have one def for the
934 result and another def for the clobber. If only one vector
935 is used and the clobber goes first, the result will be
937 bitmap_ior_into (seen_in_block, seen_in_insn);
938 bitmap_clear (seen_in_insn);
941 /* Process the artificial defs at the top of the block last since we
942 are going backwards through the block and these are logically at
944 if (!(df->changeable_flags & DF_NO_HARD_REGS))
945 df_rd_bb_local_compute_process_def (bb_info,
946 df_get_artificial_defs (bb_index),
951 /* Compute local reaching def info for each basic block within BLOCKS. */
954 df_rd_local_compute (bitmap all_blocks)
956 unsigned int bb_index;
959 struct df_rd_problem_data *problem_data
960 = (struct df_rd_problem_data *) df_rd->problem_data;
961 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
962 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
966 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
968 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
970 df_rd_bb_local_compute (bb_index);
973 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
974 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
976 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
977 bitmap_set_bit (sparse_invalidated, regno);
979 bitmap_set_range (dense_invalidated,
980 DF_DEFS_BEGIN (regno),
981 DF_DEFS_COUNT (regno));
987 /* Initialize the solution bit vectors for problem. */
990 df_rd_init_solution (bitmap all_blocks)
992 unsigned int bb_index;
995 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
997 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
999 bitmap_copy (bb_info->out, bb_info->gen);
1000 bitmap_clear (bb_info->in);
1004 /* In of target gets or of out of source. */
1007 df_rd_confluence_n (edge e)
1009 bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
1010 bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
1012 if (e->flags & EDGE_EH)
1014 struct df_rd_problem_data *problem_data
1015 = (struct df_rd_problem_data *) df_rd->problem_data;
1016 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
1017 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
1020 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1022 bitmap_copy (tmp, op2);
1023 bitmap_and_compl_into (tmp, dense_invalidated);
1025 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
1027 bitmap_clear_range (tmp,
1028 DF_DEFS_BEGIN (regno),
1029 DF_DEFS_COUNT (regno));
1031 bitmap_ior_into (op1, tmp);
1035 bitmap_ior_into (op1, op2);
1039 /* Transfer function. */
1042 df_rd_transfer_function (int bb_index)
1044 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
1047 bitmap in = bb_info->in;
1048 bitmap out = bb_info->out;
1049 bitmap gen = bb_info->gen;
1050 bitmap kill = bb_info->kill;
1051 bitmap sparse_kill = bb_info->sparse_kill;
1053 if (bitmap_empty_p (sparse_kill))
1054 return bitmap_ior_and_compl (out, gen, in, kill);
1057 struct df_rd_problem_data *problem_data;
1058 bool changed = false;
1061 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
1062 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
1063 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
1064 tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
1066 bitmap_copy (tmp, in);
1067 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
1069 bitmap_clear_range (tmp,
1070 DF_DEFS_BEGIN (regno),
1071 DF_DEFS_COUNT (regno));
1073 bitmap_and_compl_into (tmp, kill);
1074 bitmap_ior_into (tmp, gen);
1075 changed = !bitmap_equal_p (tmp, out);
1088 /* Free all storage associated with the problem. */
1094 struct df_rd_problem_data *problem_data
1095 = (struct df_rd_problem_data *) df_rd->problem_data;
1099 for (i = 0; i < df_rd->block_info_size; i++)
1101 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
1104 BITMAP_FREE (bb_info->kill);
1105 BITMAP_FREE (bb_info->sparse_kill);
1106 BITMAP_FREE (bb_info->gen);
1107 BITMAP_FREE (bb_info->in);
1108 BITMAP_FREE (bb_info->out);
1112 free_alloc_pool (df_rd->block_pool);
1113 BITMAP_FREE (problem_data->sparse_invalidated_by_call);
1114 BITMAP_FREE (problem_data->dense_invalidated_by_call);
1115 bitmap_obstack_release (&problem_data->rd_bitmaps);
1117 df_rd->block_info_size = 0;
1118 free (df_rd->block_info);
1119 free (df_rd->problem_data);
1125 /* Debugging info. */
1128 df_rd_start_dump (FILE *file)
1130 struct df_rd_problem_data *problem_data
1131 = (struct df_rd_problem_data *) df_rd->problem_data;
1132 unsigned int m = DF_REG_SIZE(df);
1135 if (!df_rd->block_info)
1138 fprintf (file, ";; Reaching defs:\n\n");
1140 fprintf (file, " sparse invalidated \t");
1141 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
1142 fprintf (file, " dense invalidated \t");
1143 dump_bitmap (file, problem_data->dense_invalidated_by_call);
1145 for (regno = 0; regno < m; regno++)
1146 if (DF_DEFS_COUNT (regno))
1147 fprintf (file, "%d[%d,%d] ", regno,
1148 DF_DEFS_BEGIN (regno),
1149 DF_DEFS_COUNT (regno));
1150 fprintf (file, "\n");
1155 /* Debugging info at top of bb. */
1158 df_rd_top_dump (basic_block bb, FILE *file)
1160 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
1161 if (!bb_info || !bb_info->in)
1164 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
1165 dump_bitmap (file, bb_info->in);
1166 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
1167 dump_bitmap (file, bb_info->gen);
1168 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
1169 dump_bitmap (file, bb_info->kill);
1173 /* Debugging info at top of bb. */
1176 df_rd_bottom_dump (basic_block bb, FILE *file)
1178 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
1179 if (!bb_info || !bb_info->out)
1182 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
1183 dump_bitmap (file, bb_info->out);
1186 /* All of the information associated with every instance of the problem. */
1188 static struct df_problem problem_RD =
1190 DF_RD, /* Problem id. */
1191 DF_FORWARD, /* Direction. */
1192 df_rd_alloc, /* Allocate the problem specific data. */
1193 NULL, /* Reset global information. */
1194 df_rd_free_bb_info, /* Free basic block info. */
1195 df_rd_local_compute, /* Local compute function. */
1196 df_rd_init_solution, /* Init the solution specific data. */
1197 df_worklist_dataflow, /* Worklist solver. */
1198 NULL, /* Confluence operator 0. */
1199 df_rd_confluence_n, /* Confluence operator n. */
1200 df_rd_transfer_function, /* Transfer function. */
1201 NULL, /* Finalize function. */
1202 df_rd_free, /* Free all of the problem information. */
1203 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
1204 df_rd_start_dump, /* Debugging. */
1205 df_rd_top_dump, /* Debugging start block. */
1206 df_rd_bottom_dump, /* Debugging end block. */
1207 NULL, /* Incremental solution verify start. */
1208 NULL, /* Incremental solution verfiy end. */
1209 NULL, /* Dependent problem. */
1210 TV_DF_RD /* Timing variable. */
1215 /* Create a new DATAFLOW instance and add it to an existing instance
1216 of DF. The returned structure is what is used to get at the
1220 df_rd_add_problem (void)
1222 df_add_problem (&problem_RD);
1227 /*----------------------------------------------------------------------------
1230 Find the locations in the function where any use of a pseudo can
1231 reach in the backwards direction. In and out bitvectors are built
1232 for each basic block. The regnum is used to index into these sets.
1233 See df.h for details.
1234 ----------------------------------------------------------------------------*/
1236 /* Private data used to verify the solution for this problem. */
1237 struct df_lr_problem_data
1244 /* Set basic block info. */
1247 df_lr_set_bb_info (unsigned int index,
1248 struct df_lr_bb_info *bb_info)
1251 gcc_assert (index < df_lr->block_info_size);
1252 df_lr->block_info[index] = bb_info;
1256 /* Free basic block info. */
1259 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1262 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
1265 BITMAP_FREE (bb_info->use);
1266 BITMAP_FREE (bb_info->def);
1267 if (bb_info->in == bb_info->top)
1268 bb_info->top = NULL;
1271 BITMAP_FREE (bb_info->top);
1272 BITMAP_FREE (bb_info->ause);
1273 BITMAP_FREE (bb_info->adef);
1275 BITMAP_FREE (bb_info->in);
1276 BITMAP_FREE (bb_info->out);
1277 pool_free (df_lr->block_pool, bb_info);
1282 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
1283 not touched unless the block is new. */
1286 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1288 unsigned int bb_index;
1291 if (!df_lr->block_pool)
1292 df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
1293 sizeof (struct df_lr_bb_info), 50);
1295 df_grow_bb_info (df_lr);
1297 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
1299 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1302 bitmap_clear (bb_info->def);
1303 bitmap_clear (bb_info->use);
1306 bitmap_clear (bb_info->adef);
1307 bitmap_clear (bb_info->ause);
1312 bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
1313 df_lr_set_bb_info (bb_index, bb_info);
1314 bb_info->use = BITMAP_ALLOC (NULL);
1315 bb_info->def = BITMAP_ALLOC (NULL);
1316 bb_info->in = BITMAP_ALLOC (NULL);
1317 bb_info->out = BITMAP_ALLOC (NULL);
1318 bb_info->top = bb_info->in;
1319 bb_info->adef = NULL;
1320 bb_info->ause = NULL;
1326 /* Reset the global solution for recalculation. */
1329 df_lr_reset (bitmap all_blocks)
1331 unsigned int bb_index;
1334 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1336 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1337 gcc_assert (bb_info);
1338 bitmap_clear (bb_info->in);
1339 bitmap_clear (bb_info->out);
1340 bitmap_clear (bb_info->top);
1345 /* Compute local live register info for basic block BB. */
1348 df_lr_bb_local_compute (unsigned int bb_index)
1350 basic_block bb = BASIC_BLOCK (bb_index);
1351 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1353 struct df_ref **def_rec;
1354 struct df_ref **use_rec;
1356 /* Process the registers set in an exception handler. */
1357 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1359 struct df_ref *def = *def_rec;
1360 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
1362 unsigned int dregno = DF_REF_REGNO (def);
1363 bitmap_set_bit (bb_info->def, dregno);
1364 bitmap_clear_bit (bb_info->use, dregno);
1368 /* Process the hardware registers that are always live. */
1369 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
1371 struct df_ref *use = *use_rec;
1372 /* Add use to set of uses in this BB. */
1373 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
1374 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1377 FOR_BB_INSNS_REVERSE (bb, insn)
1379 unsigned int uid = INSN_UID (insn);
1386 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1388 struct df_ref *def = *def_rec;
1389 unsigned int dregno = DF_REF_REGNO (def);
1391 if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
1393 if (dregno >= FIRST_PSEUDO_REGISTER
1394 || !(SIBLING_CALL_P (insn)
1395 && bitmap_bit_p (df->exit_block_uses, dregno)
1396 && !refers_to_regno_p (dregno, dregno+1,
1397 current_function_return_rtx,
1400 /* If the def is to only part of the reg, it does
1401 not kill the other defs that reach here. */
1402 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
1404 bitmap_set_bit (bb_info->def, dregno);
1405 bitmap_clear_bit (bb_info->use, dregno);
1410 /* This is the return value. */
1411 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
1413 bitmap_set_bit (bb_info->def, dregno);
1414 bitmap_clear_bit (bb_info->use, dregno);
1420 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1422 struct df_ref *def = *def_rec;
1423 /* If the def is to only part of the reg, it does
1424 not kill the other defs that reach here. */
1425 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
1427 unsigned int dregno = DF_REF_REGNO (def);
1428 bitmap_set_bit (bb_info->def, dregno);
1429 bitmap_clear_bit (bb_info->use, dregno);
1434 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1436 struct df_ref *use = *use_rec;
1437 /* Add use to set of uses in this BB. */
1438 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1441 /* Process the registers set in an exception handler. */
1442 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1444 struct df_ref *def = *def_rec;
1445 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1446 && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
1448 unsigned int dregno = DF_REF_REGNO (def);
1449 if (bb_info->adef == NULL)
1451 gcc_assert (bb_info->ause == NULL);
1452 gcc_assert (bb_info->top == bb_info->in);
1453 bb_info->adef = BITMAP_ALLOC (NULL);
1454 bb_info->ause = BITMAP_ALLOC (NULL);
1455 bb_info->top = BITMAP_ALLOC (NULL);
1457 bitmap_set_bit (bb_info->adef, dregno);
1462 /* Process the uses that are live into an exception handler. */
1463 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
1465 struct df_ref *use = *use_rec;
1466 /* Add use to set of uses in this BB. */
1467 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
1469 if (bb_info->adef == NULL)
1471 gcc_assert (bb_info->ause == NULL);
1472 gcc_assert (bb_info->top == bb_info->in);
1473 bb_info->adef = BITMAP_ALLOC (NULL);
1474 bb_info->ause = BITMAP_ALLOC (NULL);
1475 bb_info->top = BITMAP_ALLOC (NULL);
1477 bitmap_set_bit (bb_info->ause, DF_REF_REGNO (use));
1484 /* Compute local live register info for each basic block within BLOCKS. */
1487 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1489 unsigned int bb_index;
1492 bitmap_clear (df->hardware_regs_used);
1494 /* The all-important stack pointer must always be live. */
1495 bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
1497 /* Before reload, there are a few registers that must be forced
1498 live everywhere -- which might not already be the case for
1499 blocks within infinite loops. */
1500 if (!reload_completed)
1502 /* Any reference to any pseudo before reload is a potential
1503 reference of the frame pointer. */
1504 bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
1506 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1507 /* Pseudos with argument area equivalences may require
1508 reloading via the argument pointer. */
1509 if (fixed_regs[ARG_POINTER_REGNUM])
1510 bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
1513 /* Any constant, or pseudo with constant equivalences, may
1514 require reloading from memory using the pic register. */
1515 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1516 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1517 bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
1520 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
1522 if (bb_index == EXIT_BLOCK)
1524 /* The exit block is special for this problem and its bits are
1525 computed from thin air. */
1526 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
1527 bitmap_copy (bb_info->use, df->exit_block_uses);
1530 df_lr_bb_local_compute (bb_index);
1533 bitmap_clear (df_lr->out_of_date_transfer_functions);
1537 /* Initialize the solution vectors. */
1540 df_lr_init (bitmap all_blocks)
1542 unsigned int bb_index;
1545 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1547 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1548 bitmap_copy (bb_info->in, bb_info->use);
1549 bitmap_clear (bb_info->out);
1554 /* Confluence function that processes infinite loops. This might be a
1555 noreturn function that throws. And even if it isn't, getting the
1556 unwind info right helps debugging. */
1558 df_lr_confluence_0 (basic_block bb)
1560 bitmap op1 = df_lr_get_bb_info (bb->index)->out;
1561 if (bb != EXIT_BLOCK_PTR)
1562 bitmap_copy (op1, df->hardware_regs_used);
1566 /* Confluence function that ignores fake edges. */
1569 df_lr_confluence_n (edge e)
1571 bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
1572 bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
1574 /* Call-clobbered registers die across exception and call edges. */
1575 /* ??? Abnormal call edges ignored for the moment, as this gets
1576 confused by sibling call edges, which crashes reg-stack. */
1577 if (e->flags & EDGE_EH)
1578 bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
1580 bitmap_ior_into (op1, op2);
1582 bitmap_ior_into (op1, df->hardware_regs_used);
1586 /* Transfer function. */
1589 df_lr_transfer_function (int bb_index)
1591 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1592 bitmap in = bb_info->in;
1593 bitmap out = bb_info->out;
1594 bitmap use = bb_info->use;
1595 bitmap def = bb_info->def;
1596 bitmap top = bb_info->top;
1597 bitmap ause = bb_info->ause;
1598 bitmap adef = bb_info->adef;
1601 changed = bitmap_ior_and_compl (top, use, out, def);
1604 gcc_assert (ause && adef);
1605 changed |= bitmap_ior_and_compl (in, ause, top, adef);
1612 /* Run the fast dce as a side effect of building LR. */
1615 df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1617 if (df->changeable_flags & DF_LR_RUN_DCE)
1620 if (df_lr->problem_data && df_lr->solutions_dirty)
1622 /* If we are here, then it is because we are both verifying
1623 the solution and the dce changed the function. In that case
1624 the verification info built will be wrong. So we leave the
1625 dirty flag true so that the verifier will skip the checking
1626 part and just clean up.*/
1627 df_lr->solutions_dirty = true;
1630 df_lr->solutions_dirty = false;
1633 df_lr->solutions_dirty = false;
1637 /* Free all storage associated with the problem. */
1642 if (df_lr->block_info)
1645 for (i = 0; i < df_lr->block_info_size; i++)
1647 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1650 BITMAP_FREE (bb_info->use);
1651 BITMAP_FREE (bb_info->def);
1652 if (bb_info->in == bb_info->top)
1653 bb_info->top = NULL;
1656 BITMAP_FREE (bb_info->top);
1657 BITMAP_FREE (bb_info->ause);
1658 BITMAP_FREE (bb_info->adef);
1660 BITMAP_FREE (bb_info->in);
1661 BITMAP_FREE (bb_info->out);
1664 free_alloc_pool (df_lr->block_pool);
1666 df_lr->block_info_size = 0;
1667 free (df_lr->block_info);
1670 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1675 /* Debugging info at top of bb. */
1678 df_lr_top_dump (basic_block bb, FILE *file)
1680 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1681 struct df_lr_problem_data *problem_data;
1682 if (!bb_info || !bb_info->in)
1685 fprintf (file, ";; lr in \t");
1686 df_print_regset (file, bb_info->in);
1687 if (df_lr->problem_data)
1689 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1690 fprintf (file, ";; old in \t");
1691 df_print_regset (file, problem_data->in[bb->index]);
1693 fprintf (file, ";; lr use \t");
1694 df_print_regset (file, bb_info->use);
1695 fprintf (file, ";; lr def \t");
1696 df_print_regset (file, bb_info->def);
1700 /* Debugging info at bottom of bb. */
1703 df_lr_bottom_dump (basic_block bb, FILE *file)
1705 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1706 struct df_lr_problem_data *problem_data;
1707 if (!bb_info || !bb_info->out)
1710 fprintf (file, ";; lr out \t");
1711 df_print_regset (file, bb_info->out);
1712 if (df_lr->problem_data)
1714 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1715 fprintf (file, ";; old out \t");
1716 df_print_regset (file, problem_data->out[bb->index]);
1721 /* Build the datastructure to verify that the solution to the dataflow
1722 equations is not dirty. */
1725 df_lr_verify_solution_start (void)
1728 struct df_lr_problem_data *problem_data;
1729 if (df_lr->solutions_dirty)
1731 df_lr->problem_data = NULL;
1735 /* Set it true so that the solution is recomputed. */
1736 df_lr->solutions_dirty = true;
1738 problem_data = XNEW (struct df_lr_problem_data);
1739 df_lr->problem_data = problem_data;
1740 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1741 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1745 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1746 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1747 bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1748 bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1753 /* Compare the saved datastructure and the new solution to the dataflow
1757 df_lr_verify_solution_end (void)
1759 struct df_lr_problem_data *problem_data;
1762 if (df_lr->problem_data == NULL)
1765 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1767 if (df_lr->solutions_dirty)
1768 /* Do not check if the solution is still dirty. See the comment
1769 in df_lr_local_finalize for details. */
1770 df_lr->solutions_dirty = false;
1774 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1775 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1777 /*df_dump (stderr);*/
1782 /* Cannot delete them immediately because you may want to dump them
1783 if the comparison fails. */
1786 BITMAP_FREE (problem_data->in[bb->index]);
1787 BITMAP_FREE (problem_data->out[bb->index]);
1790 free (problem_data->in);
1791 free (problem_data->out);
1792 free (problem_data);
1793 df_lr->problem_data = NULL;
1797 /* All of the information associated with every instance of the problem. */
1799 static struct df_problem problem_LR =
1801 DF_LR, /* Problem id. */
1802 DF_BACKWARD, /* Direction. */
1803 df_lr_alloc, /* Allocate the problem specific data. */
1804 df_lr_reset, /* Reset global information. */
1805 df_lr_free_bb_info, /* Free basic block info. */
1806 df_lr_local_compute, /* Local compute function. */
1807 df_lr_init, /* Init the solution specific data. */
1808 df_worklist_dataflow, /* Worklist solver. */
1809 df_lr_confluence_0, /* Confluence operator 0. */
1810 df_lr_confluence_n, /* Confluence operator n. */
1811 df_lr_transfer_function, /* Transfer function. */
1812 df_lr_local_finalize, /* Finalize function. */
1813 df_lr_free, /* Free all of the problem information. */
1814 NULL, /* Remove this problem from the stack of dataflow problems. */
1815 NULL, /* Debugging. */
1816 df_lr_top_dump, /* Debugging start block. */
1817 df_lr_bottom_dump, /* Debugging end block. */
1818 df_lr_verify_solution_start,/* Incremental solution verify start. */
1819 df_lr_verify_solution_end, /* Incremental solution verify end. */
1820 NULL, /* Dependent problem. */
1821 TV_DF_LR /* Timing variable. */
1825 /* Create a new DATAFLOW instance and add it to an existing instance
1826 of DF. The returned structure is what is used to get at the
1830 df_lr_add_problem (void)
1832 df_add_problem (&problem_LR);
1833 /* These will be initialized when df_scan_blocks processes each
1835 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1839 /* Verify that all of the lr related info is consistent and
1843 df_lr_verify_transfer_functions (void)
1856 saved_def = BITMAP_ALLOC (NULL);
1857 saved_use = BITMAP_ALLOC (NULL);
1858 saved_adef = BITMAP_ALLOC (NULL);
1859 saved_ause = BITMAP_ALLOC (NULL);
1860 all_blocks = BITMAP_ALLOC (NULL);
1864 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1865 bitmap_set_bit (all_blocks, bb->index);
1869 /* Make a copy of the transfer functions and then compute
1870 new ones to see if the transfer functions have
1872 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1875 bitmap_copy (saved_def, bb_info->def);
1876 bitmap_copy (saved_use, bb_info->use);
1877 bitmap_clear (bb_info->def);
1878 bitmap_clear (bb_info->use);
1883 bitmap_copy (saved_adef, bb_info->adef);
1884 bitmap_copy (saved_ause, bb_info->ause);
1885 bitmap_clear (bb_info->adef);
1886 bitmap_clear (bb_info->ause);
1891 df_lr_bb_local_compute (bb->index);
1892 gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1893 gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1897 gcc_assert (bb_info->adef);
1898 gcc_assert (bb_info->ause);
1899 gcc_assert (bitmap_equal_p (saved_adef, bb_info->adef));
1900 gcc_assert (bitmap_equal_p (saved_ause, bb_info->ause));
1904 gcc_assert (!bb_info->adef);
1905 gcc_assert (!bb_info->ause);
1911 /* If we do not have basic block info, the block must be in
1912 the list of dirty blocks or else some one has added a
1913 block behind our backs. */
1914 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1917 /* Make sure no one created a block without following
1919 gcc_assert (df_scan_get_bb_info (bb->index));
1922 /* Make sure there are no dirty bits in blocks that have been deleted. */
1923 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1926 BITMAP_FREE (saved_def);
1927 BITMAP_FREE (saved_use);
1928 BITMAP_FREE (saved_adef);
1929 BITMAP_FREE (saved_ause);
1930 BITMAP_FREE (all_blocks);
1935 /*----------------------------------------------------------------------------
1936 COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
1938 First find the set of uses for registers that are reachable from
1939 the entry block without passing thru a definition. In and out
1940 bitvectors are built for each basic block. The regnum is used to
1941 index into these sets. See df.h for details.
1943 Then the in and out sets here are the anded results of the in and
1944 out sets from the lr and ur
1946 ----------------------------------------------------------------------------*/
1948 /* Private data used to verify the solution for this problem. */
1949 struct df_live_problem_data
1956 /* Set basic block info. */
1959 df_live_set_bb_info (unsigned int index,
1960 struct df_live_bb_info *bb_info)
1962 gcc_assert (df_live);
1963 gcc_assert (index < df_live->block_info_size);
1964 df_live->block_info[index] = bb_info;
1968 /* Free basic block info. */
1971 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1974 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1977 BITMAP_FREE (bb_info->gen);
1978 BITMAP_FREE (bb_info->kill);
1979 BITMAP_FREE (bb_info->in);
1980 BITMAP_FREE (bb_info->out);
1981 pool_free (df_live->block_pool, bb_info);
1986 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1987 not touched unless the block is new. */
1990 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1992 unsigned int bb_index;
1995 if (!df_live->block_pool)
1996 df_live->block_pool = create_alloc_pool ("df_live_block pool",
1997 sizeof (struct df_live_bb_info), 100);
1999 df_grow_bb_info (df_live);
2001 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
2003 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2006 bitmap_clear (bb_info->kill);
2007 bitmap_clear (bb_info->gen);
2011 bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
2012 df_live_set_bb_info (bb_index, bb_info);
2013 bb_info->kill = BITMAP_ALLOC (NULL);
2014 bb_info->gen = BITMAP_ALLOC (NULL);
2015 bb_info->in = BITMAP_ALLOC (NULL);
2016 bb_info->out = BITMAP_ALLOC (NULL);
2022 /* Reset the global solution for recalculation. */
2025 df_live_reset (bitmap all_blocks)
2027 unsigned int bb_index;
2030 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2032 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
2033 gcc_assert (bb_info);
2034 bitmap_clear (bb_info->in);
2035 bitmap_clear (bb_info->out);
2040 /* Compute local uninitialized register info for basic block BB. */
2043 df_live_bb_local_compute (unsigned int bb_index)
2045 basic_block bb = BASIC_BLOCK (bb_index);
2046 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2048 struct df_ref **def_rec;
2051 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2053 struct df_ref *def = *def_rec;
2054 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2055 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
2058 FOR_BB_INSNS (bb, insn)
2060 unsigned int uid = INSN_UID (insn);
2061 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2063 /* Inserting labels does not always trigger the incremental
2067 gcc_assert (!INSN_P (insn));
2068 df_insn_create_insn_record (insn);
2071 DF_INSN_LUID (insn) = luid;
2076 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2078 struct df_ref *def = *def_rec;
2079 unsigned int regno = DF_REF_REGNO (def);
2081 if (DF_REF_FLAGS_IS_SET (def,
2082 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2083 /* All partial or conditional def
2084 seen are included in the gen set. */
2085 bitmap_set_bit (bb_info->gen, regno);
2086 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
2087 /* Only must clobbers for the entire reg destroy the
2089 bitmap_set_bit (bb_info->kill, regno);
2090 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2091 bitmap_set_bit (bb_info->gen, regno);
2095 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2097 struct df_ref *def = *def_rec;
2098 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2099 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
2104 /* Compute local uninitialized register info. */
2107 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2109 unsigned int bb_index;
2112 df_grow_insn_info ();
2114 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
2117 df_live_bb_local_compute (bb_index);
2120 bitmap_clear (df_live->out_of_date_transfer_functions);
2124 /* Initialize the solution vectors. */
2127 df_live_init (bitmap all_blocks)
2129 unsigned int bb_index;
2132 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2134 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2136 bitmap_copy (bb_info->out, bb_info->gen);
2137 bitmap_clear (bb_info->in);
2141 /* Confluence function that ignores fake edges. */
2144 df_live_confluence_n (edge e)
2146 bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
2147 bitmap op2 = df_live_get_bb_info (e->src->index)->out;
2149 if (e->flags & EDGE_FAKE)
2152 bitmap_ior_into (op1, op2);
2156 /* Transfer function. */
2159 df_live_transfer_function (int bb_index)
2161 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2162 bitmap in = bb_info->in;
2163 bitmap out = bb_info->out;
2164 bitmap gen = bb_info->gen;
2165 bitmap kill = bb_info->kill;
2167 return bitmap_ior_and_compl (out, gen, in, kill);
2171 /* And the LR and UR info to produce the LIVE info. */
2174 df_live_local_finalize (bitmap all_blocks)
2177 if (df_live->solutions_dirty)
2180 unsigned int bb_index;
2182 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2184 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
2185 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
2187 /* No register may reach a location where it is not used. Thus
2188 we trim the rr result to the places where it is used. */
2189 bitmap_and_into (bb_live_info->in, bb_lr_info->in);
2190 bitmap_and_into (bb_live_info->out, bb_lr_info->out);
2193 df_live->solutions_dirty = false;
2198 /* Free all storage associated with the problem. */
2203 if (df_live->block_info)
2207 for (i = 0; i < df_live->block_info_size; i++)
2209 struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
2212 BITMAP_FREE (bb_info->gen);
2213 BITMAP_FREE (bb_info->kill);
2214 BITMAP_FREE (bb_info->in);
2215 BITMAP_FREE (bb_info->out);
2219 free_alloc_pool (df_live->block_pool);
2220 df_live->block_info_size = 0;
2221 free (df_live->block_info);
2223 BITMAP_FREE (df_live->out_of_date_transfer_functions);
2228 /* Debugging info at top of bb. */
2231 df_live_top_dump (basic_block bb, FILE *file)
2233 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2234 struct df_live_problem_data *problem_data;
2236 if (!bb_info || !bb_info->in)
2239 fprintf (file, ";; live in \t");
2240 df_print_regset (file, bb_info->in);
2241 if (df_live->problem_data)
2243 problem_data = (struct df_live_problem_data *)df_live->problem_data;
2244 fprintf (file, ";; old in \t");
2245 df_print_regset (file, problem_data->in[bb->index]);
2247 fprintf (file, ";; live gen \t");
2248 df_print_regset (file, bb_info->gen);
2249 fprintf (file, ";; live kill\t");
2250 df_print_regset (file, bb_info->kill);
2254 /* Debugging info at bottom of bb. */
2257 df_live_bottom_dump (basic_block bb, FILE *file)
2259 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2260 struct df_live_problem_data *problem_data;
2262 if (!bb_info || !bb_info->out)
2265 fprintf (file, ";; live out \t");
2266 df_print_regset (file, bb_info->out);
2267 if (df_live->problem_data)
2269 problem_data = (struct df_live_problem_data *)df_live->problem_data;
2270 fprintf (file, ";; old out \t");
2271 df_print_regset (file, problem_data->out[bb->index]);
2276 /* Build the datastructure to verify that the solution to the dataflow
2277 equations is not dirty. */
2280 df_live_verify_solution_start (void)
2283 struct df_live_problem_data *problem_data;
2284 if (df_live->solutions_dirty)
2286 df_live->problem_data = NULL;
2290 /* Set it true so that the solution is recomputed. */
2291 df_live->solutions_dirty = true;
2293 problem_data = XNEW (struct df_live_problem_data);
2294 df_live->problem_data = problem_data;
2295 problem_data->in = XNEWVEC (bitmap, last_basic_block);
2296 problem_data->out = XNEWVEC (bitmap, last_basic_block);
2300 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
2301 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
2302 bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
2303 bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
2308 /* Compare the saved datastructure and the new solution to the dataflow
2312 df_live_verify_solution_end (void)
2314 struct df_live_problem_data *problem_data;
2317 if (df_live->problem_data == NULL)
2320 problem_data = (struct df_live_problem_data *)df_live->problem_data;
2324 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
2325 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
2327 /*df_dump (stderr);*/
2332 /* Cannot delete them immediately because you may want to dump them
2333 if the comparison fails. */
2336 BITMAP_FREE (problem_data->in[bb->index]);
2337 BITMAP_FREE (problem_data->out[bb->index]);
2340 free (problem_data->in);
2341 free (problem_data->out);
2342 free (problem_data);
2343 df_live->problem_data = NULL;
2347 /* All of the information associated with every instance of the problem. */
2349 static struct df_problem problem_LIVE =
2351 DF_LIVE, /* Problem id. */
2352 DF_FORWARD, /* Direction. */
2353 df_live_alloc, /* Allocate the problem specific data. */
2354 df_live_reset, /* Reset global information. */
2355 df_live_free_bb_info, /* Free basic block info. */
2356 df_live_local_compute, /* Local compute function. */
2357 df_live_init, /* Init the solution specific data. */
2358 df_worklist_dataflow, /* Worklist solver. */
2359 NULL, /* Confluence operator 0. */
2360 df_live_confluence_n, /* Confluence operator n. */
2361 df_live_transfer_function, /* Transfer function. */
2362 df_live_local_finalize, /* Finalize function. */
2363 df_live_free, /* Free all of the problem information. */
2364 df_live_free, /* Remove this problem from the stack of dataflow problems. */
2365 NULL, /* Debugging. */
2366 df_live_top_dump, /* Debugging start block. */
2367 df_live_bottom_dump, /* Debugging end block. */
2368 df_live_verify_solution_start,/* Incremental solution verify start. */
2369 df_live_verify_solution_end, /* Incremental solution verify end. */
2370 &problem_LR, /* Dependent problem. */
2371 TV_DF_LIVE /* Timing variable. */
2375 /* Create a new DATAFLOW instance and add it to an existing instance
2376 of DF. The returned structure is what is used to get at the
2380 df_live_add_problem (void)
2382 df_add_problem (&problem_LIVE);
2383 /* These will be initialized when df_scan_blocks processes each
2385 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2389 /* Verify that all of the lr related info is consistent and
2393 df_live_verify_transfer_functions (void)
2403 saved_gen = BITMAP_ALLOC (NULL);
2404 saved_kill = BITMAP_ALLOC (NULL);
2405 all_blocks = BITMAP_ALLOC (NULL);
2407 df_grow_insn_info ();
2411 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2412 bitmap_set_bit (all_blocks, bb->index);
2416 /* Make a copy of the transfer functions and then compute
2417 new ones to see if the transfer functions have
2419 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
2422 bitmap_copy (saved_gen, bb_info->gen);
2423 bitmap_copy (saved_kill, bb_info->kill);
2424 bitmap_clear (bb_info->gen);
2425 bitmap_clear (bb_info->kill);
2427 df_live_bb_local_compute (bb->index);
2428 gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
2429 gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
2434 /* If we do not have basic block info, the block must be in
2435 the list of dirty blocks or else some one has added a
2436 block behind our backs. */
2437 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
2440 /* Make sure no one created a block without following
2442 gcc_assert (df_scan_get_bb_info (bb->index));
2445 /* Make sure there are no dirty bits in blocks that have been deleted. */
2446 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
2448 BITMAP_FREE (saved_gen);
2449 BITMAP_FREE (saved_kill);
2450 BITMAP_FREE (all_blocks);
2455 /*----------------------------------------------------------------------------
2456 UNINITIALIZED REGISTERS WITH EARLYCLOBBER
2458 Find the set of uses for registers that are reachable from the entry
2459 block without passing thru a definition. In and out bitvectors are built
2460 for each basic block. The regnum is used to index into these sets.
2461 See df.h for details.
2463 This is a variant of the UR problem above that has a lot of special
2464 features just for the register allocation phase. This problem
2465 should go away if someone would fix the interference graph.
2467 ----------------------------------------------------------------------------*/
2469 /* Private data used to compute the solution for this problem. These
2470 data structures are not accessible outside of this module. */
2471 struct df_urec_problem_data
2473 bool earlyclobbers_found; /* True if any instruction contains an
2476 bitmap stack_regs; /* Registers that may be allocated to a STACK_REGS. */
2481 /* Set basic block info. */
2484 df_urec_set_bb_info (unsigned int index,
2485 struct df_urec_bb_info *bb_info)
2487 gcc_assert (df_urec);
2488 gcc_assert (index < df_urec->block_info_size);
2489 df_urec->block_info[index] = bb_info;
2493 /* Free basic block info. */
2496 df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2499 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
2502 BITMAP_FREE (bb_info->gen);
2503 BITMAP_FREE (bb_info->kill);
2504 BITMAP_FREE (bb_info->in);
2505 BITMAP_FREE (bb_info->out);
2506 BITMAP_FREE (bb_info->earlyclobber);
2507 pool_free (df_urec->block_pool, bb_info);
2512 /* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
2513 not touched unless the block is new. */
2516 df_urec_alloc (bitmap all_blocks)
2519 unsigned int bb_index;
2521 struct df_urec_problem_data *problem_data
2522 = (struct df_urec_problem_data *) df_urec->problem_data;
2524 if (!df_urec->block_pool)
2525 df_urec->block_pool = create_alloc_pool ("df_urec_block pool",
2526 sizeof (struct df_urec_bb_info), 50);
2528 if (!df_urec->problem_data)
2530 problem_data = XNEW (struct df_urec_problem_data);
2531 df_urec->problem_data = problem_data;
2533 problem_data->earlyclobbers_found = false;
2535 df_grow_bb_info (df_urec);
2537 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2539 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2542 bitmap_clear (bb_info->kill);
2543 bitmap_clear (bb_info->gen);
2544 bitmap_clear (bb_info->earlyclobber);
2548 bb_info = (struct df_urec_bb_info *) pool_alloc (df_urec->block_pool);
2549 df_urec_set_bb_info (bb_index, bb_info);
2550 bb_info->kill = BITMAP_ALLOC (NULL);
2551 bb_info->gen = BITMAP_ALLOC (NULL);
2552 bb_info->in = BITMAP_ALLOC (NULL);
2553 bb_info->out = BITMAP_ALLOC (NULL);
2554 bb_info->top = BITMAP_ALLOC (NULL);
2555 bb_info->earlyclobber = BITMAP_ALLOC (NULL);
2561 /* The function modifies local info for register REG being changed in
2562 SETTER. DATA is used to pass the current basic block info. */
2565 df_urec_mark_reg_change (rtx reg, rtx setter, void *data)
2570 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2572 if (GET_CODE (reg) == SUBREG)
2573 reg = SUBREG_REG (reg);
2578 regno = REGNO (reg);
2579 if (regno < FIRST_PSEUDO_REGISTER)
2581 endregno = END_HARD_REGNO (reg);
2582 for (i = regno; i < endregno; i++)
2584 bitmap_set_bit (bb_info->kill, i);
2586 if (GET_CODE (setter) != CLOBBER)
2587 bitmap_set_bit (bb_info->gen, i);
2589 bitmap_clear_bit (bb_info->gen, i);
2594 bitmap_set_bit (bb_info->kill, regno);
2596 if (GET_CODE (setter) != CLOBBER)
2597 bitmap_set_bit (bb_info->gen, regno);
2599 bitmap_clear_bit (bb_info->gen, regno);
2602 /* Classes of registers which could be early clobbered in the current
2605 static VEC(int,heap) *earlyclobber_regclass;
2607 /* This function finds and stores register classes that could be early
2608 clobbered in INSN. If any earlyclobber classes are found, the function
2609 returns TRUE, in all other cases it returns FALSE. */
2612 df_urec_check_earlyclobber (rtx insn)
2617 extract_insn (insn);
2619 VEC_truncate (int, earlyclobber_regclass, 0);
2620 for (opno = 0; opno < recog_data.n_operands; opno++)
2625 enum reg_class class;
2626 const char *p = recog_data.constraints[opno];
2635 case '=': case '+': case '?':
2638 case 'm': case '<': case '>': case 'V': case 'o':
2639 case 'E': case 'F': case 'G': case 'H':
2640 case 's': case 'i': case 'n':
2641 case 'I': case 'J': case 'K': case 'L':
2642 case 'M': case 'N': case 'O': case 'P':
2644 case '0': case '1': case '2': case '3': case '4':
2645 case '5': case '6': case '7': case '8': case '9':
2646 /* These don't say anything we care about. */
2654 if (amp_p && class != NO_REGS)
2660 VEC_iterate (int, earlyclobber_regclass, i, rc);
2663 if (rc == (int) class)
2667 /* We use VEC_quick_push here because
2668 earlyclobber_regclass holds no more than
2669 N_REG_CLASSES elements. */
2670 VEC_quick_push (int, earlyclobber_regclass, (int) class);
2680 class = GENERAL_REGS;
2684 class = REG_CLASS_FROM_CONSTRAINT (c, p);
2689 p += CONSTRAINT_LEN (c, p);
2696 /* The function checks that pseudo-register *X has a class
2697 intersecting with the class of pseudo-register could be early
2698 clobbered in the same insn.
2700 This function is a no-op if earlyclobber_regclass is empty.
2702 Reload can assign the same hard register to uninitialized
2703 pseudo-register and early clobbered pseudo-register in an insn if
2704 the pseudo-register is used first time in given BB and not lived at
2705 the BB start. To prevent this we don't change life information for
2706 such pseudo-registers. */
2709 df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
2711 enum reg_class pref_class, alt_class;
2713 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2715 if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
2720 if (bitmap_bit_p (bb_info->kill, regno)
2721 || bitmap_bit_p (bb_info->gen, regno))
2723 pref_class = reg_preferred_class (regno);
2724 alt_class = reg_alternate_class (regno);
2725 for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
2727 if (reg_classes_intersect_p (rc, pref_class)
2729 && reg_classes_intersect_p (rc, alt_class)))
2731 bitmap_set_bit (bb_info->earlyclobber, regno);
2739 /* The function processes all pseudo-registers in *X with the aid of
2740 previous function. */
2743 df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
2745 for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
2749 /* Compute local uninitialized register info for basic block BB. */
2752 df_urec_bb_local_compute (unsigned int bb_index)
2754 basic_block bb = BASIC_BLOCK (bb_index);
2755 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2757 struct df_ref **def_rec;
2759 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2761 struct df_ref *def = *def_rec;
2762 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2764 unsigned int regno = DF_REF_REGNO (def);
2765 bitmap_set_bit (bb_info->gen, regno);
2769 FOR_BB_INSNS (bb, insn)
2773 note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
2774 if (df_urec_check_earlyclobber (insn))
2776 struct df_urec_problem_data *problem_data
2777 = (struct df_urec_problem_data *) df_urec->problem_data;
2778 problem_data->earlyclobbers_found = true;
2779 note_uses (&PATTERN (insn),
2780 df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
2785 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2787 struct df_ref *def = *def_rec;
2788 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2790 unsigned int regno = DF_REF_REGNO (def);
2791 bitmap_set_bit (bb_info->gen, regno);
2797 /* Compute local uninitialized register info. */
2800 df_urec_local_compute (bitmap all_blocks)
2802 unsigned int bb_index;
2806 HARD_REG_SET stack_hard_regs, used;
2807 struct df_urec_problem_data *problem_data
2808 = (struct df_urec_problem_data *) df_urec->problem_data;
2810 /* Any register that MAY be allocated to a register stack (like the
2811 387) is treated poorly. Each such register is marked as being
2812 live everywhere. This keeps the register allocator and the
2813 subsequent passes from doing anything useful with these values.
2815 FIXME: This seems like an incredibly poor idea. */
2817 CLEAR_HARD_REG_SET (stack_hard_regs);
2818 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
2819 SET_HARD_REG_BIT (stack_hard_regs, i);
2820 problem_data->stack_regs = BITMAP_ALLOC (NULL);
2821 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2823 COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
2824 IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
2825 AND_HARD_REG_SET (used, stack_hard_regs);
2826 if (!hard_reg_set_empty_p (used))
2827 bitmap_set_bit (problem_data->stack_regs, i);
2831 /* We know that earlyclobber_regclass holds no more than
2832 N_REG_CLASSES elements. See df_urec_check_earlyclobber. */
2833 earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
2835 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2837 df_urec_bb_local_compute (bb_index);
2840 VEC_free (int, heap, earlyclobber_regclass);
2844 /* Initialize the solution vectors. */
2847 df_urec_init (bitmap all_blocks)
2849 unsigned int bb_index;
2852 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2854 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2856 bitmap_copy (bb_info->out, bb_info->gen);
2857 bitmap_clear (bb_info->in);
2862 /* Or in the stack regs, hard regs and early clobber regs into the
2863 urec_in sets of all of the blocks. */
2867 df_urec_local_finalize (bitmap all_blocks)
2869 bitmap tmp = BITMAP_ALLOC (NULL);
2871 unsigned int bb_index;
2872 struct df_urec_problem_data *problem_data
2873 = (struct df_urec_problem_data *) df_urec->problem_data;
2875 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2877 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2878 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
2880 if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
2882 if (problem_data->earlyclobbers_found)
2883 bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
2886 /* We can not use the same stack register for uninitialized
2887 pseudo-register and another living pseudo-register
2888 because if the uninitialized pseudo-register dies,
2889 subsequent pass reg-stack will be confused (it will
2890 believe that the other register dies). */
2891 bitmap_ior_into (bb_info->in, problem_data->stack_regs);
2892 bitmap_ior_into (bb_info->out, problem_data->stack_regs);
2896 /* No register may reach a location where it is not used. Thus
2897 we trim the rr result to the places where it is used. */
2898 bitmap_and_into (bb_info->in, bb_lr_info->in);
2899 bitmap_and_into (bb_info->out, bb_lr_info->out);
2900 bitmap_copy (bb_info->top, bb_info->in);
2901 if (bb_lr_info->adef)
2902 bitmap_ior_into (bb_info->top, bb_lr_info->adef);
2903 bitmap_and_into (bb_info->top, bb_lr_info->top);
2905 /* Hard registers may still stick in the ur_out set, but not
2906 be in the ur_in set, if their only mention was in a call
2907 in this block. This is because a call kills in the lr
2908 problem but does not kill in the rr problem. To clean
2909 this up, we execute the transfer function on the lr_in
2910 set and then use that to knock bits out of ur_out. */
2911 bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
2913 bitmap_and_into (bb_info->out, tmp);
2918 BITMAP_FREE (problem_data->stack_regs);
2924 /* Confluence function that ignores fake edges. */
2927 df_urec_confluence_n (edge e)
2929 bitmap op1 = df_urec_get_bb_info (e->dest->index)->in;
2930 bitmap op2 = df_urec_get_bb_info (e->src->index)->out;
2932 if (e->flags & EDGE_FAKE)
2935 bitmap_ior_into (op1, op2);
2939 /* Transfer function. */
2942 df_urec_transfer_function (int bb_index)
2944 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2945 bitmap in = bb_info->in;
2946 bitmap out = bb_info->out;
2947 bitmap gen = bb_info->gen;
2948 bitmap kill = bb_info->kill;
2950 return bitmap_ior_and_compl (out, gen, in, kill);
2954 /* Free all storage associated with the problem. */
2959 if (df_urec->block_info)
2963 for (i = 0; i < df_urec->block_info_size; i++)
2965 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (i);
2968 BITMAP_FREE (bb_info->gen);
2969 BITMAP_FREE (bb_info->kill);
2970 BITMAP_FREE (bb_info->in);
2971 BITMAP_FREE (bb_info->out);
2972 BITMAP_FREE (bb_info->earlyclobber);
2973 BITMAP_FREE (bb_info->top);
2977 free_alloc_pool (df_urec->block_pool);
2979 df_urec->block_info_size = 0;
2980 free (df_urec->block_info);
2981 free (df_urec->problem_data);
2987 /* Debugging info at top of bb. */
2990 df_urec_top_dump (basic_block bb, FILE *file)
2992 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
2993 if (!bb_info || !bb_info->in)
2996 fprintf (file, ";; urec in \t");
2997 df_print_regset (file, bb_info->in);
2998 fprintf (file, ";; urec gen \t");
2999 df_print_regset (file, bb_info->gen);
3000 fprintf (file, ";; urec kill\t");
3001 df_print_regset (file, bb_info->kill);
3002 fprintf (file, ";; urec ec\t");
3003 df_print_regset (file, bb_info->earlyclobber);
3007 /* Debugging info at bottom of bb. */
3010 df_urec_bottom_dump (basic_block bb, FILE *file)
3012 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
3013 if (!bb_info || !bb_info->out)
3015 fprintf (file, ";; urec out \t");
3016 df_print_regset (file, bb_info->out);
3020 /* All of the information associated with every instance of the problem. */
3022 static struct df_problem problem_UREC =
3024 DF_UREC, /* Problem id. */
3025 DF_FORWARD, /* Direction. */
3026 df_urec_alloc, /* Allocate the problem specific data. */
3027 NULL, /* Reset global information. */
3028 df_urec_free_bb_info, /* Free basic block info. */
3029 df_urec_local_compute, /* Local compute function. */
3030 df_urec_init, /* Init the solution specific data. */
3031 df_worklist_dataflow, /* Worklist solver. */
3032 NULL, /* Confluence operator 0. */
3033 df_urec_confluence_n, /* Confluence operator n. */
3034 df_urec_transfer_function, /* Transfer function. */
3035 df_urec_local_finalize, /* Finalize function. */
3036 df_urec_free, /* Free all of the problem information. */
3037 df_urec_free, /* Remove this problem from the stack of dataflow problems. */
3038 NULL, /* Debugging. */
3039 df_urec_top_dump, /* Debugging start block. */
3040 df_urec_bottom_dump, /* Debugging end block. */
3041 NULL, /* Incremental solution verify start. */
3042 NULL, /* Incremental solution verfiy end. */
3043 &problem_LR, /* Dependent problem. */
3044 TV_DF_UREC /* Timing variable. */
3048 /* Create a new DATAFLOW instance and add it to an existing instance
3049 of DF. The returned structure is what is used to get at the
3053 df_urec_add_problem (void)
3055 df_add_problem (&problem_UREC);
3060 /*----------------------------------------------------------------------------
3061 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
3063 Link either the defs to the uses and / or the uses to the defs.
3065 These problems are set up like the other dataflow problems so that
3066 they nicely fit into the framework. They are much simpler and only
3067 involve a single traversal of instructions and an examination of
3068 the reaching defs information (the dependent problem).
3069 ----------------------------------------------------------------------------*/
3071 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
3073 /* Create a du or ud chain from SRC to DST and link it into SRC. */
3076 df_chain_create (struct df_ref *src, struct df_ref *dst)
3078 struct df_link *head = DF_REF_CHAIN (src);
3079 struct df_link *link = pool_alloc (df_chain->block_pool);;
3081 DF_REF_CHAIN (src) = link;
3088 /* Delete any du or ud chains that start at REF and point to
3091 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
3093 struct df_link *chain = DF_REF_CHAIN (ref);
3094 struct df_link *prev = NULL;
3098 if (chain->ref == target)
3101 prev->next = chain->next;
3103 DF_REF_CHAIN (ref) = chain->next;
3104 pool_free (df_chain->block_pool, chain);
3108 chain = chain->next;
3113 /* Delete a du or ud chain that leave or point to REF. */
3116 df_chain_unlink (struct df_ref *ref)
3118 struct df_link *chain = DF_REF_CHAIN (ref);
3121 struct df_link *next = chain->next;
3122 /* Delete the other side if it exists. */
3123 df_chain_unlink_1 (chain->ref, ref);
3124 pool_free (df_chain->block_pool, chain);
3127 DF_REF_CHAIN (ref) = NULL;
3131 /* Copy the du or ud chain starting at FROM_REF and attach it to
3135 df_chain_copy (struct df_ref *to_ref,
3136 struct df_link *from_ref)
3140 df_chain_create (to_ref, from_ref->ref);
3141 from_ref = from_ref->next;
3146 /* Remove this problem from the stack of dataflow problems. */
3149 df_chain_remove_problem (void)
3152 unsigned int bb_index;
3154 /* Wholesale destruction of the old chains. */
3155 if (df_chain->block_pool)
3156 free_alloc_pool (df_chain->block_pool);
3158 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
3161 struct df_ref **def_rec;
3162 struct df_ref **use_rec;
3163 basic_block bb = BASIC_BLOCK (bb_index);
3165 if (df_chain_problem_p (DF_DU_CHAIN))
3166 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
3167 DF_REF_CHAIN (*def_rec) = NULL;
3168 if (df_chain_problem_p (DF_UD_CHAIN))
3169 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
3170 DF_REF_CHAIN (*use_rec) = NULL;
3172 FOR_BB_INSNS (bb, insn)
3174 unsigned int uid = INSN_UID (insn);
3178 if (df_chain_problem_p (DF_DU_CHAIN))
3179 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3180 DF_REF_CHAIN (*def_rec) = NULL;
3181 if (df_chain_problem_p (DF_UD_CHAIN))
3183 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3184 DF_REF_CHAIN (*use_rec) = NULL;
3185 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
3186 DF_REF_CHAIN (*use_rec) = NULL;
3192 bitmap_clear (df_chain->out_of_date_transfer_functions);
3193 df_chain->block_pool = NULL;
3197 /* Remove the chain problem completely. */
3200 df_chain_fully_remove_problem (void)
3202 df_chain_remove_problem ();
3203 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
3208 /* Create def-use or use-def chains. */
3211 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3213 df_chain_remove_problem ();
3214 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
3215 sizeof (struct df_link), 50);
3219 /* Reset all of the chains when the set of basic blocks changes. */
3222 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
3224 df_chain_remove_problem ();
3228 /* Create the chains for a list of USEs. */
3231 df_chain_create_bb_process_use (bitmap local_rd,
3232 struct df_ref **use_rec,
3233 enum df_ref_flags top_flag)
3236 unsigned int def_index;
3240 struct df_ref *use = *use_rec;
3241 unsigned int uregno = DF_REF_REGNO (use);
3242 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3243 || (uregno >= FIRST_PSEUDO_REGISTER))
3245 /* Do not want to go through this for an uninitialized var. */
3246 int count = DF_DEFS_COUNT (uregno);
3249 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
3251 unsigned int first_index = DF_DEFS_BEGIN (uregno);
3252 unsigned int last_index = first_index + count - 1;
3254 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
3257 if (def_index > last_index)
3260 def = DF_DEFS_GET (def_index);
3261 if (df_chain_problem_p (DF_DU_CHAIN))
3262 df_chain_create (def, use);
3263 if (df_chain_problem_p (DF_UD_CHAIN))
3264 df_chain_create (use, def);
3275 /* Create chains from reaching defs bitmaps for basic block BB. */
3278 df_chain_create_bb (unsigned int bb_index)
3280 basic_block bb = BASIC_BLOCK (bb_index);
3281 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
3283 bitmap cpy = BITMAP_ALLOC (NULL);
3284 struct df_ref **def_rec;
3286 bitmap_copy (cpy, bb_info->in);
3287 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
3289 /* Since we are going forwards, process the artificial uses first
3290 then the artificial defs second. */
3293 /* Create the chains for the artificial uses from the EH_USES at the
3294 beginning of the block. */
3296 /* Artificials are only hard regs. */
3297 if (!(df->changeable_flags & DF_NO_HARD_REGS))
3298 df_chain_create_bb_process_use (cpy,
3299 df_get_artificial_uses (bb->index),
3303 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3305 struct df_ref *def = *def_rec;
3306 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3308 unsigned int dregno = DF_REF_REGNO (def);
3309 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3310 bitmap_clear_range (cpy,
3311 DF_DEFS_BEGIN (dregno),
3312 DF_DEFS_COUNT (dregno));
3313 bitmap_set_bit (cpy, DF_REF_ID (def));
3317 /* Process the regular instructions next. */
3318 FOR_BB_INSNS (bb, insn)
3320 struct df_ref **def_rec;
3321 unsigned int uid = INSN_UID (insn);
3326 /* Now scan the uses and link them up with the defs that remain
3327 in the cpy vector. */
3329 df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
3331 if (df->changeable_flags & DF_EQ_NOTES)
3332 df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
3335 /* Since we are going forwards, process the defs second. This
3336 pass only changes the bits in cpy. */
3337 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3339 struct df_ref *def = *def_rec;
3340 unsigned int dregno = DF_REF_REGNO (def);
3341 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3342 || (dregno >= FIRST_PSEUDO_REGISTER))
3344 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3345 bitmap_clear_range (cpy,
3346 DF_DEFS_BEGIN (dregno),
3347 DF_DEFS_COUNT (dregno));
3348 if (!(DF_REF_FLAGS (def)
3349 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3350 bitmap_set_bit (cpy, DF_REF_ID (def));
3355 /* Create the chains for the artificial uses of the hard registers
3356 at the end of the block. */
3357 if (!(df->changeable_flags & DF_NO_HARD_REGS))
3358 df_chain_create_bb_process_use (cpy,
3359 df_get_artificial_uses (bb->index),
3365 /* Create def-use chains from reaching use bitmaps for basic blocks
3369 df_chain_finalize (bitmap all_blocks)
3371 unsigned int bb_index;
3374 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3376 df_chain_create_bb (bb_index);
3381 /* Free all storage associated with the problem. */
3384 df_chain_free (void)
3386 free_alloc_pool (df_chain->block_pool);
3387 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
3392 /* Debugging info. */
3395 df_chain_top_dump (basic_block bb, FILE *file)
3397 if (df_chain_problem_p (DF_DU_CHAIN))
3400 struct df_ref **def_rec = df_get_artificial_defs (bb->index);
3404 fprintf (file, ";; DU chains for artificial defs\n");
3407 struct df_ref *def = *def_rec;
3408 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
3409 df_chain_dump (DF_REF_CHAIN (def), file);
3410 fprintf (file, "\n");
3415 FOR_BB_INSNS (bb, insn)
3417 unsigned int uid = INSN_UID (insn);
3420 def_rec = DF_INSN_UID_DEFS (uid);
3423 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
3424 DF_INSN_LUID (insn), uid);
3428 struct df_ref *def = *def_rec;
3429 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
3430 if (def->flags & DF_REF_READ_WRITE)
3431 fprintf (file, "read/write ");
3432 df_chain_dump (DF_REF_CHAIN (def), file);
3433 fprintf (file, "\n");
3444 df_chain_bottom_dump (basic_block bb, FILE *file)
3446 if (df_chain_problem_p (DF_UD_CHAIN))
3449 struct df_ref **use_rec = df_get_artificial_uses (bb->index);
3453 fprintf (file, ";; UD chains for artificial uses\n");
3456 struct df_ref *use = *use_rec;
3457 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
3458 df_chain_dump (DF_REF_CHAIN (use), file);
3459 fprintf (file, "\n");
3464 FOR_BB_INSNS (bb, insn)
3466 unsigned int uid = INSN_UID (insn);
3469 struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
3470 use_rec = DF_INSN_UID_USES (uid);
3471 if (*use_rec || *eq_use_rec)
3473 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
3474 DF_INSN_LUID (insn), uid);
3478 struct df_ref *use = *use_rec;
3479 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
3480 if (use->flags & DF_REF_READ_WRITE)
3481 fprintf (file, "read/write ");
3482 df_chain_dump (DF_REF_CHAIN (use), file);
3483 fprintf (file, "\n");
3488 struct df_ref *use = *eq_use_rec;
3489 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
3490 df_chain_dump (DF_REF_CHAIN (use), file);
3491 fprintf (file, "\n");
3501 static struct df_problem problem_CHAIN =
3503 DF_CHAIN, /* Problem id. */
3504 DF_NONE, /* Direction. */
3505 df_chain_alloc, /* Allocate the problem specific data. */
3506 df_chain_reset, /* Reset global information. */
3507 NULL, /* Free basic block info. */
3508 NULL, /* Local compute function. */
3509 NULL, /* Init the solution specific data. */
3510 NULL, /* Iterative solver. */
3511 NULL, /* Confluence operator 0. */
3512 NULL, /* Confluence operator n. */
3513 NULL, /* Transfer function. */
3514 df_chain_finalize, /* Finalize function. */
3515 df_chain_free, /* Free all of the problem information. */
3516 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
3517 NULL, /* Debugging. */
3518 df_chain_top_dump, /* Debugging start block. */
3519 df_chain_bottom_dump, /* Debugging end block. */
3520 NULL, /* Incremental solution verify start. */
3521 NULL, /* Incremental solution verfiy end. */
3522 &problem_RD, /* Dependent problem. */
3523 TV_DF_CHAIN /* Timing variable. */
3527 /* Create a new DATAFLOW instance and add it to an existing instance
3528 of DF. The returned structure is what is used to get at the
3532 df_chain_add_problem (enum df_chain_flags chain_flags)
3534 df_add_problem (&problem_CHAIN);
3535 df_chain->local_flags = (unsigned int)chain_flags;
3536 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
3539 #undef df_chain_problem_p
3542 /*----------------------------------------------------------------------------
3543 This pass computes REG_DEAD and REG_UNUSED notes.
3544 ----------------------------------------------------------------------------*/
3546 #ifdef REG_DEAD_DEBUGGING
3548 df_print_note (const char *prefix, rtx insn, rtx note)
3552 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3553 print_rtl (dump_file, note);
3554 fprintf (dump_file, "\n");
3560 /* After reg-stack, the x86 floating point stack regs are difficult to
3561 analyze because of all of the pushes, pops and rotations. Thus, we
3562 just leave the notes alone. */
3566 df_ignore_stack_reg (int regno)
3568 return regstack_completed
3569 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3573 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3580 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3581 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3584 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3586 rtx *pprev = ®_NOTES (insn);
3593 switch (REG_NOTE_KIND (link))
3596 /* After reg-stack, we need to ignore any unused notes
3597 for the stack registers. */
3598 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3600 pprev = &XEXP (link, 1);
3605 rtx next = XEXP (link, 1);
3606 #ifdef REG_DEAD_DEBUGGING
3607 df_print_note ("deleting: ", insn, link);
3609 XEXP (link, 1) = dead;
3611 *pprev = link = next;
3616 /* After reg-stack, we need to ignore any unused notes
3617 for the stack registers. */
3618 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3620 pprev = &XEXP (link, 1);
3625 rtx next = XEXP (link, 1);
3626 #ifdef REG_DEAD_DEBUGGING
3627 df_print_note ("deleting: ", insn, link);
3629 XEXP (link, 1) = unused;
3631 *pprev = link = next;
3636 pprev = &XEXP (link, 1);
3642 *old_dead_notes = dead;
3643 *old_unused_notes = unused;
3647 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3648 list, otherwise create a new one. */
3651 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3657 if (XEXP (this, 0) == reg)
3660 XEXP (prev, 1) = XEXP (this, 1);
3662 old = XEXP (this, 1);
3663 XEXP (this, 1) = REG_NOTES (insn);
3664 REG_NOTES (insn) = this;
3670 this = XEXP (this, 1);
3673 /* Did not find the note. */
3674 REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
3678 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3679 based on the bits in LIVE. Do not generate notes for registers in
3680 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3681 not generated if the reg is both read and written by the
3686 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3687 bitmap live, bitmap do_not_gen,
3688 bitmap artificial_uses)
3690 bool all_dead = true;
3693 #ifdef REG_DEAD_DEBUGGING
3695 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3696 mws->start_regno, mws->end_regno);
3698 for (r=mws->start_regno; r <= mws->end_regno; r++)
3699 if ((bitmap_bit_p (live, r))
3700 || bitmap_bit_p (artificial_uses, r))
3708 unsigned int regno = mws->start_regno;
3709 old = df_set_note (REG_UNUSED, insn, old, *(mws->loc));
3711 #ifdef REG_DEAD_DEBUGGING
3712 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3714 bitmap_set_bit (do_not_gen, regno);
3715 /* Only do this if the value is totally dead. */
3718 for (r=mws->start_regno; r <= mws->end_regno; r++)
3721 if ((!bitmap_bit_p (live, r))
3722 && (!bitmap_bit_p (artificial_uses, r)))
3724 old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3725 #ifdef REG_DEAD_DEBUGGING
3726 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3729 bitmap_set_bit (do_not_gen, r);
3735 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3736 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3737 from being set if the instruction both reads and writes the
3741 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3742 bitmap live, bitmap do_not_gen,
3743 bitmap artificial_uses)
3745 bool all_dead = true;
3748 #ifdef REG_DEAD_DEBUGGING
3751 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3752 mws->start_regno, mws->end_regno);
3753 df_print_regset (dump_file, do_not_gen);
3754 fprintf (dump_file, " live =");
3755 df_print_regset (dump_file, live);
3756 fprintf (dump_file, " artificial uses =");
3757 df_print_regset (dump_file, artificial_uses);
3761 for (r = mws->start_regno; r <= mws->end_regno; r++)
3762 if ((bitmap_bit_p (live, r))
3763 || bitmap_bit_p (artificial_uses, r)
3764 || bitmap_bit_p (do_not_gen, r))
3772 if (!bitmap_bit_p (do_not_gen, mws->start_regno))
3774 /* Add a dead note for the entire multi word register. */
3775 old = df_set_note (REG_DEAD, insn, old, *(mws->loc));
3776 #ifdef REG_DEAD_DEBUGGING
3777 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3783 for (r = mws->start_regno; r <= mws->end_regno; r++)
3785 if ((!bitmap_bit_p (live, r))
3786 && (!bitmap_bit_p (artificial_uses, r))
3787 && (!bitmap_bit_p (do_not_gen, r)))
3789 old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3790 #ifdef REG_DEAD_DEBUGGING
3791 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3800 /* Create a REG_UNUSED note if necessary for DEF in INSN updating LIVE
3801 and DO_NOT_GEN. Do not generate notes for registers in artificial
3805 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
3806 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3808 unsigned int dregno = DF_REF_REGNO (def);
3810 #ifdef REG_DEAD_DEBUGGING
3813 fprintf (dump_file, " regular looking at def ");
3814 df_ref_debug (def, dump_file);
3818 if (!(bitmap_bit_p (live, dregno)
3819 || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3820 || bitmap_bit_p (artificial_uses, dregno)
3821 || df_ignore_stack_reg (dregno)))
3823 rtx reg = (DF_REF_LOC (def))
3824 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3825 old = df_set_note (REG_UNUSED, insn, old, reg);
3826 #ifdef REG_DEAD_DEBUGGING
3827 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3831 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
3832 bitmap_set_bit (do_not_gen, dregno);
3834 /* Kill this register if it is not a subreg store or conditional store. */
3835 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3836 bitmap_clear_bit (live, dregno);
3841 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3842 info: lifetime, bb, and number of defs and uses for basic block
3843 BB. The three bitvectors are scratch regs used here. */
3846 df_note_bb_compute (unsigned int bb_index,
3847 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3849 basic_block bb = BASIC_BLOCK (bb_index);
3851 struct df_ref **def_rec;
3852 struct df_ref **use_rec;
3854 bitmap_copy (live, df_get_live_out (bb));
3855 bitmap_clear (artificial_uses);
3857 #ifdef REG_DEAD_DEBUGGING
3860 fprintf (dump_file, "live at bottom ");
3861 df_print_regset (dump_file, live);
3865 /* Process the artificial defs and uses at the bottom of the block
3866 to begin processing. */
3867 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3869 struct df_ref *def = *def_rec;
3871 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3873 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3874 bitmap_clear_bit (live, DF_REF_REGNO (def));
3877 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3879 struct df_ref *use = *use_rec;
3880 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3882 unsigned int regno = DF_REF_REGNO (use);
3883 bitmap_set_bit (live, regno);
3885 /* Notes are not generated for any of the artificial registers
3886 at the bottom of the block. */
3887 bitmap_set_bit (artificial_uses, regno);
3891 #ifdef REG_DEAD_DEBUGGING
3894 fprintf (dump_file, "live before artificials out ");
3895 df_print_regset (dump_file, live);
3899 FOR_BB_INSNS_REVERSE (bb, insn)
3901 unsigned int uid = INSN_UID (insn);
3902 struct df_mw_hardreg **mws_rec;
3904 rtx old_unused_notes;
3909 bitmap_clear (do_not_gen);
3910 df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3912 /* Process the defs. */
3915 #ifdef REG_DEAD_DEBUGGING
3918 fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
3919 df_print_regset (dump_file, live);
3922 /* We only care about real sets for calls. Clobbers only
3923 may clobbers cannot be depended on. */
3924 mws_rec = DF_INSN_UID_MWS (uid);
3927 struct df_mw_hardreg *mws = *mws_rec;
3928 if ((mws->type == DF_REF_REG_DEF)
3929 && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
3931 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3932 mws, live, do_not_gen,
3937 /* All of the defs except the return value are some sort of
3938 clobber. This code is for the return. */
3939 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3941 struct df_ref *def = *def_rec;
3942 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3944 = df_create_unused_note (insn, old_unused_notes,
3945 def, live, do_not_gen,
3952 mws_rec = DF_INSN_UID_MWS (uid);
3955 struct df_mw_hardreg *mws = *mws_rec;
3956 if (mws->type == DF_REF_REG_DEF)
3958 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3959 mws, live, do_not_gen,
3964 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3966 struct df_ref *def = *def_rec;
3968 = df_create_unused_note (insn, old_unused_notes,
3969 def, live, do_not_gen,
3974 /* Process the uses. */
3975 mws_rec = DF_INSN_UID_MWS (uid);
3978 struct df_mw_hardreg *mws = *mws_rec;
3979 if ((mws->type != DF_REF_REG_DEF)
3980 && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
3982 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3983 mws, live, do_not_gen,
3988 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3990 struct df_ref *use = *use_rec;
3991 unsigned int uregno = DF_REF_REGNO (use);
3993 #ifdef REG_DEAD_DEBUGGING
3996 fprintf (dump_file, " regular looking at use ");
3997 df_ref_debug (use, dump_file);
4000 if (!bitmap_bit_p (live, uregno))
4002 if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
4003 && (!bitmap_bit_p (do_not_gen, uregno))
4004 && (!bitmap_bit_p (artificial_uses, uregno))
4005 && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
4006 && (!df_ignore_stack_reg (uregno)))
4008 rtx reg = (DF_REF_LOC (use))
4009 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
4010 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
4012 #ifdef REG_DEAD_DEBUGGING
4013 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
4016 /* This register is now live. */
4017 bitmap_set_bit (live, uregno);
4021 while (old_unused_notes)
4023 rtx next = XEXP (old_unused_notes, 1);
4024 free_EXPR_LIST_node (old_unused_notes);
4025 old_unused_notes = next;
4027 while (old_dead_notes)
4029 rtx next = XEXP (old_dead_notes, 1);
4030 free_EXPR_LIST_node (old_dead_notes);
4031 old_dead_notes = next;
4037 /* Compute register info: lifetime, bb, and number of defs and uses. */
4039 df_note_compute (bitmap all_blocks)
4041 unsigned int bb_index;
4043 bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
4044 bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
4045 bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4047 #ifdef REG_DEAD_DEBUGGING
4049 print_rtl_with_bb (dump_file, get_insns());
4052 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4054 df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
4058 BITMAP_FREE (do_not_gen);
4059 BITMAP_FREE (artificial_uses);
4063 /* Free all storage associated with the problem. */
4072 /* All of the information associated every instance of the problem. */
4074 static struct df_problem problem_NOTE =
4076 DF_NOTE, /* Problem id. */
4077 DF_NONE, /* Direction. */
4078 NULL, /* Allocate the problem specific data. */
4079 NULL, /* Reset global information. */
4080 NULL, /* Free basic block info. */
4081 df_note_compute, /* Local compute function. */
4082 NULL, /* Init the solution specific data. */
4083 NULL, /* Iterative solver. */
4084 NULL, /* Confluence operator 0. */
4085 NULL, /* Confluence operator n. */
4086 NULL, /* Transfer function. */
4087 NULL, /* Finalize function. */
4088 df_note_free, /* Free all of the problem information. */
4089 df_note_free, /* Remove this problem from the stack of dataflow problems. */
4090 NULL, /* Debugging. */
4091 NULL, /* Debugging start block. */
4092 NULL, /* Debugging end block. */
4093 NULL, /* Incremental solution verify start. */
4094 NULL, /* Incremental solution verfiy end. */
4096 /* Technically this is only dependent on the live registers problem
4097 but it will produce information if built one of uninitialized
4098 register problems (UR, UREC) is also run. */
4099 &problem_LR, /* Dependent problem. */
4100 TV_DF_NOTE /* Timing variable. */
4104 /* Create a new DATAFLOW instance and add it to an existing instance
4105 of DF. The returned structure is what is used to get at the
4109 df_note_add_problem (void)
4111 df_add_problem (&problem_NOTE);
4117 /*----------------------------------------------------------------------------
4118 Functions for simulating the effects of single insns.
4120 You can either simulate in the forwards direction, starting from
4121 the top of a block or the backwards direction from the end of the
4122 block. The main difference is that if you go forwards, the uses
4123 are examined first then the defs, and if you go backwards, the defs
4124 are examined first then the uses.
4126 If you start at the top of the block, use one of DF_LIVE_IN or
4127 DF_LR_IN. If you start at the bottom of the block use one of
4128 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
4129 THEY WILL BE DESTROYED.
4131 ----------------------------------------------------------------------------*/
4134 /* Find the set of DEFs for INSN. */
4137 df_simulate_find_defs (rtx insn, bitmap defs)
4139 struct df_ref **def_rec;
4140 unsigned int uid = INSN_UID (insn);
4144 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4146 struct df_ref *def = *def_rec;
4147 unsigned int dregno = DF_REF_REGNO (def);
4149 if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
4151 if (dregno >= FIRST_PSEUDO_REGISTER
4152 || !(SIBLING_CALL_P (insn)
4153 && bitmap_bit_p (df->exit_block_uses, dregno)
4154 && !refers_to_regno_p (dregno, dregno+1,
4155 current_function_return_rtx,
4158 /* If the def is to only part of the reg, it does
4159 not kill the other defs that reach here. */
4160 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4161 bitmap_set_bit (defs, dregno);
4165 /* This is the return value. */
4166 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4167 bitmap_set_bit (defs, dregno);
4172 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4174 struct df_ref *def = *def_rec;
4175 /* If the def is to only part of the reg, it does
4176 not kill the other defs that reach here. */
4177 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4178 bitmap_set_bit (defs, DF_REF_REGNO (def));
4184 /* Simulate the effects of the defs of INSN on LIVE. */
4187 df_simulate_defs (rtx insn, bitmap live)
4189 struct df_ref **def_rec;
4190 unsigned int uid = INSN_UID (insn);
4194 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4196 struct df_ref *def = *def_rec;
4197 unsigned int dregno = DF_REF_REGNO (def);
4199 if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
4201 if (dregno >= FIRST_PSEUDO_REGISTER
4202 || !(SIBLING_CALL_P (insn)
4203 && bitmap_bit_p (df->exit_block_uses, dregno)
4204 && !refers_to_regno_p (dregno, dregno+1,
4205 current_function_return_rtx,
4208 /* If the def is to only part of the reg, it does
4209 not kill the other defs that reach here. */
4210 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4211 bitmap_clear_bit (live, dregno);
4215 /* This is the return value. */
4216 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4217 bitmap_clear_bit (live, dregno);
4222 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4224 struct df_ref *def = *def_rec;
4225 unsigned int dregno = DF_REF_REGNO (def);
4227 /* If the def is to only part of the reg, it does
4228 not kill the other defs that reach here. */
4229 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4230 bitmap_clear_bit (live, dregno);
4236 /* Simulate the effects of the uses of INSN on LIVE. */
4239 df_simulate_uses (rtx insn, bitmap live)
4241 struct df_ref **use_rec;
4242 unsigned int uid = INSN_UID (insn);
4244 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
4246 struct df_ref *use = *use_rec;
4247 /* Add use to set of uses in this BB. */
4248 bitmap_set_bit (live, DF_REF_REGNO (use));
4253 /* Add back the always live regs in BB to LIVE. */
4256 df_simulate_fixup_sets (basic_block bb, bitmap live)
4258 /* These regs are considered always live so if they end up dying
4259 because of some def, we need to bring the back again. */
4260 if (df_has_eh_preds (bb))
4261 bitmap_ior_into (live, df->eh_block_artificial_uses);
4263 bitmap_ior_into (live, df->regular_block_artificial_uses);
4267 /* Apply the artifical uses and defs at the top of BB in a forwards
4271 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
4273 struct df_ref **def_rec;
4274 struct df_ref **use_rec;
4275 int bb_index = bb->index;
4277 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4279 struct df_ref *use = *use_rec;
4280 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4281 bitmap_set_bit (live, DF_REF_REGNO (use));
4284 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4286 struct df_ref *def = *def_rec;
4287 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4288 bitmap_clear_bit (live, DF_REF_REGNO (def));
4293 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4296 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
4298 if (! INSN_P (insn))
4301 df_simulate_uses (insn, live);
4302 df_simulate_defs (insn, live);
4303 df_simulate_fixup_sets (bb, live);
4307 /* Apply the artifical uses and defs at the end of BB in a backwards
4311 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
4313 struct df_ref **def_rec;
4314 struct df_ref **use_rec;
4315 int bb_index = bb->index;
4317 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4319 struct df_ref *def = *def_rec;
4320 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
4321 bitmap_clear_bit (live, DF_REF_REGNO (def));
4324 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4326 struct df_ref *use = *use_rec;
4327 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
4328 bitmap_set_bit (live, DF_REF_REGNO (use));
4333 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
4336 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
4338 if (! INSN_P (insn))
4341 df_simulate_defs (insn, live);
4342 df_simulate_uses (insn, live);
4343 df_simulate_fixup_sets (bb, live);