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 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "alloc-pool.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
48 /* Note that turning REG_DEAD_DEBUGGING on will cause
49 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50 addresses in the dumps. */
52 #define REG_DEAD_DEBUGGING
55 #define DF_SPARSE_THRESHOLD 32
57 static bitmap seen_in_block
= NULL
;
58 static bitmap seen_in_insn
= NULL
;
61 /*----------------------------------------------------------------------------
62 Public functions access functions for the dataflow problems.
63 ----------------------------------------------------------------------------*/
64 /* Get the live at out set for BB no matter what problem happens to be
65 defined. This function is used by the register allocators who
66 choose different dataflow problems depending on the optimization
70 df_get_live_out (basic_block bb
)
75 return DF_RA_LIVE_OUT (bb
);
77 return DF_LIVE_OUT (bb
);
79 return DF_LR_OUT (bb
);
82 /* Get the live at in set for BB no matter what problem happens to be
83 defined. This function is used by the register allocators who
84 choose different dataflow problems depending on the optimization
88 df_get_live_in (basic_block bb
)
93 return DF_RA_LIVE_IN (bb
);
95 return DF_LIVE_IN (bb
);
100 /* Get the live at top set for BB no matter what problem happens to be
101 defined. This function is used by the register allocators who
102 choose different dataflow problems depending on the optimization
106 df_get_live_top (basic_block bb
)
111 return DF_RA_LIVE_TOP (bb
);
113 return DF_LR_TOP (bb
);
117 /*----------------------------------------------------------------------------
119 ----------------------------------------------------------------------------*/
121 /* Generic versions to get the void* version of the block info. Only
122 used inside the problem instance vectors. */
124 /* Grow the bb_info array. */
127 df_grow_bb_info (struct dataflow
*dflow
)
129 unsigned int new_size
= last_basic_block
+ 1;
130 if (dflow
->block_info_size
< new_size
)
132 new_size
+= new_size
/ 4;
133 dflow
->block_info
= xrealloc (dflow
->block_info
,
134 new_size
*sizeof (void*));
135 memset (dflow
->block_info
+ dflow
->block_info_size
, 0,
136 (new_size
- dflow
->block_info_size
) *sizeof (void *));
137 dflow
->block_info_size
= new_size
;
141 /* Dump a def-use or use-def chain for REF to FILE. */
144 df_chain_dump (struct df_link
*link
, FILE *file
)
146 fprintf (file
, "{ ");
147 for (; link
; link
= link
->next
)
149 fprintf (file
, "%c%d(bb %d insn %d) ",
150 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
151 DF_REF_ID (link
->ref
),
152 DF_REF_BBNO (link
->ref
),
153 DF_REF_INSN (link
->ref
) ? DF_REF_INSN_UID (link
->ref
) : -1);
159 /* Print some basic block info as part of df_dump. */
162 df_print_bb_index (basic_block bb
, FILE *file
)
167 fprintf (file
, "\n( ");
168 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
170 basic_block pred
= e
->src
;
171 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
173 fprintf (file
, ")->[%d]->( ", bb
->index
);
174 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
176 basic_block succ
= e
->dest
;
177 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
179 fprintf (file
, ")\n");
184 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
190 seen_in_block
= BITMAP_ALLOC (&df_bitmap_obstack
);
191 seen_in_insn
= BITMAP_ALLOC (&df_bitmap_obstack
);
198 BITMAP_FREE (seen_in_block
);
199 BITMAP_FREE (seen_in_insn
);
204 /*----------------------------------------------------------------------------
207 Find the locations in the function where each definition site for a
208 pseudo reaches. In and out bitvectors are built for each basic
209 block. The id field in the ref is used to index into these sets.
210 See df.h for details.
211 ----------------------------------------------------------------------------*/
213 /* See the comment at the top of the Reaching Uses problem for how the
214 uses are represented in the kill sets. The same games are played
215 here for the defs. */
217 /* Private data used to compute the solution for this problem. These
218 data structures are not accessible outside of this module. */
219 struct df_rd_problem_data
221 /* The set of defs to regs invalidated by call. */
222 bitmap sparse_invalidated_by_call
;
223 /* The set of defs to regs invalidate by call for rd. */
224 bitmap dense_invalidated_by_call
;
225 /* An obstack for the bitmaps we need for this problem. */
226 bitmap_obstack rd_bitmaps
;
229 /* Set basic block info. */
232 df_rd_set_bb_info (unsigned int index
,
233 struct df_rd_bb_info
*bb_info
)
236 gcc_assert (index
< df_rd
->block_info_size
);
237 df_rd
->block_info
[index
] = bb_info
;
241 /* Free basic block info. */
244 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
247 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
250 BITMAP_FREE (bb_info
->kill
);
251 BITMAP_FREE (bb_info
->sparse_kill
);
252 BITMAP_FREE (bb_info
->gen
);
253 BITMAP_FREE (bb_info
->in
);
254 BITMAP_FREE (bb_info
->out
);
255 pool_free (df_rd
->block_pool
, bb_info
);
260 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
261 not touched unless the block is new. */
264 df_rd_alloc (bitmap all_blocks
)
266 unsigned int bb_index
;
268 struct df_rd_problem_data
*problem_data
;
270 if (!df_rd
->block_pool
)
271 df_rd
->block_pool
= create_alloc_pool ("df_rd_block pool",
272 sizeof (struct df_rd_bb_info
), 50);
274 if (df_rd
->problem_data
)
276 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
277 bitmap_clear (problem_data
->sparse_invalidated_by_call
);
278 bitmap_clear (problem_data
->dense_invalidated_by_call
);
282 problem_data
= XNEW (struct df_rd_problem_data
);
283 df_rd
->problem_data
= problem_data
;
285 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
286 problem_data
->sparse_invalidated_by_call
287 = BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
288 problem_data
->dense_invalidated_by_call
289 = BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
292 df_grow_bb_info (df_rd
);
294 /* Because of the clustering of all use sites for the same pseudo,
295 we have to process all of the blocks before doing the
298 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
300 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
303 bitmap_clear (bb_info
->kill
);
304 bitmap_clear (bb_info
->sparse_kill
);
305 bitmap_clear (bb_info
->gen
);
309 bb_info
= (struct df_rd_bb_info
*) pool_alloc (df_rd
->block_pool
);
310 df_rd_set_bb_info (bb_index
, bb_info
);
311 bb_info
->kill
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
312 bb_info
->sparse_kill
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
313 bb_info
->gen
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
314 bb_info
->in
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
315 bb_info
->out
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
318 df_rd
->optional_p
= true;
322 /* Process a list of DEFs for df_rd_bb_local_compute. */
325 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
326 struct df_ref
**def_rec
,
327 enum df_ref_flags top_flag
)
331 struct df_ref
*def
= *def_rec
;
332 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
334 unsigned int regno
= DF_REF_REGNO (def
);
335 unsigned int begin
= DF_DEFS_BEGIN (regno
);
336 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
338 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
339 || (regno
>= FIRST_PSEUDO_REGISTER
))
341 /* Only the last def(s) for a regno in the block has any
343 if (!bitmap_bit_p (seen_in_block
, regno
))
345 /* The first def for regno in insn gets to knock out the
346 defs from other instructions. */
347 if ((!bitmap_bit_p (seen_in_insn
, regno
))
348 /* If the def is to only part of the reg, it does
349 not kill the other defs that reach here. */
350 && (!(DF_REF_FLAGS (def
) &
351 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
353 if (n_defs
> DF_SPARSE_THRESHOLD
)
355 bitmap_set_bit (bb_info
->sparse_kill
, regno
);
356 bitmap_clear_range(bb_info
->gen
, begin
, n_defs
);
360 bitmap_set_range (bb_info
->kill
, begin
, n_defs
);
361 bitmap_clear_range (bb_info
->gen
, begin
, n_defs
);
365 bitmap_set_bit (seen_in_insn
, regno
);
366 /* All defs for regno in the instruction may be put into
368 if (!(DF_REF_FLAGS (def
)
369 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
370 bitmap_set_bit (bb_info
->gen
, DF_REF_ID (def
));
378 /* Compute local reaching def info for basic block BB. */
381 df_rd_bb_local_compute (unsigned int bb_index
)
383 basic_block bb
= BASIC_BLOCK (bb_index
);
384 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
387 bitmap_clear (seen_in_block
);
388 bitmap_clear (seen_in_insn
);
390 /* Artificials are only hard regs. */
391 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
392 df_rd_bb_local_compute_process_def (bb_info
,
393 df_get_artificial_defs (bb_index
),
396 FOR_BB_INSNS_REVERSE (bb
, insn
)
398 unsigned int uid
= INSN_UID (insn
);
403 df_rd_bb_local_compute_process_def (bb_info
,
404 DF_INSN_UID_DEFS (uid
), 0);
406 /* This complex dance with the two bitmaps is required because
407 instructions can assign twice to the same pseudo. This
408 generally happens with calls that will have one def for the
409 result and another def for the clobber. If only one vector
410 is used and the clobber goes first, the result will be
412 bitmap_ior_into (seen_in_block
, seen_in_insn
);
413 bitmap_clear (seen_in_insn
);
416 /* Process the artificial defs at the top of the block last since we
417 are going backwards through the block and these are logically at
419 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
420 df_rd_bb_local_compute_process_def (bb_info
,
421 df_get_artificial_defs (bb_index
),
426 /* Compute local reaching def info for each basic block within BLOCKS. */
429 df_rd_local_compute (bitmap all_blocks
)
431 unsigned int bb_index
;
434 struct df_rd_problem_data
*problem_data
435 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
436 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
437 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
441 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
443 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
445 df_rd_bb_local_compute (bb_index
);
448 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
449 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call
, 0, regno
, bi
)
451 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
452 bitmap_set_bit (sparse_invalidated
, regno
);
454 bitmap_set_range (dense_invalidated
,
455 DF_DEFS_BEGIN (regno
),
456 DF_DEFS_COUNT (regno
));
462 /* Initialize the solution bit vectors for problem. */
465 df_rd_init_solution (bitmap all_blocks
)
467 unsigned int bb_index
;
470 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
472 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
474 bitmap_copy (bb_info
->out
, bb_info
->gen
);
475 bitmap_clear (bb_info
->in
);
479 /* In of target gets or of out of source. */
482 df_rd_confluence_n (edge e
)
484 bitmap op1
= df_rd_get_bb_info (e
->dest
->index
)->in
;
485 bitmap op2
= df_rd_get_bb_info (e
->src
->index
)->out
;
487 if (e
->flags
& EDGE_EH
)
489 struct df_rd_problem_data
*problem_data
490 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
491 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
492 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
495 bitmap tmp
= BITMAP_ALLOC (&df_bitmap_obstack
);
497 bitmap_copy (tmp
, op2
);
498 bitmap_and_compl_into (tmp
, dense_invalidated
);
500 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
502 bitmap_clear_range (tmp
,
503 DF_DEFS_BEGIN (regno
),
504 DF_DEFS_COUNT (regno
));
506 bitmap_ior_into (op1
, tmp
);
510 bitmap_ior_into (op1
, op2
);
514 /* Transfer function. */
517 df_rd_transfer_function (int bb_index
)
519 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
522 bitmap in
= bb_info
->in
;
523 bitmap out
= bb_info
->out
;
524 bitmap gen
= bb_info
->gen
;
525 bitmap kill
= bb_info
->kill
;
526 bitmap sparse_kill
= bb_info
->sparse_kill
;
528 if (bitmap_empty_p (sparse_kill
))
529 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
532 struct df_rd_problem_data
*problem_data
;
533 bool changed
= false;
536 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
537 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
538 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
539 tmp
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
541 bitmap_copy (tmp
, in
);
542 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
544 bitmap_clear_range (tmp
,
545 DF_DEFS_BEGIN (regno
),
546 DF_DEFS_COUNT (regno
));
548 bitmap_and_compl_into (tmp
, kill
);
549 bitmap_ior_into (tmp
, gen
);
550 changed
= !bitmap_equal_p (tmp
, out
);
563 /* Free all storage associated with the problem. */
569 struct df_rd_problem_data
*problem_data
570 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
574 for (i
= 0; i
< df_rd
->block_info_size
; i
++)
576 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (i
);
579 BITMAP_FREE (bb_info
->kill
);
580 BITMAP_FREE (bb_info
->sparse_kill
);
581 BITMAP_FREE (bb_info
->gen
);
582 BITMAP_FREE (bb_info
->in
);
583 BITMAP_FREE (bb_info
->out
);
587 free_alloc_pool (df_rd
->block_pool
);
588 BITMAP_FREE (problem_data
->sparse_invalidated_by_call
);
589 BITMAP_FREE (problem_data
->dense_invalidated_by_call
);
590 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
592 df_rd
->block_info_size
= 0;
593 free (df_rd
->block_info
);
594 free (df_rd
->problem_data
);
600 /* Debugging info. */
603 df_rd_start_dump (FILE *file
)
605 struct df_rd_problem_data
*problem_data
606 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
607 unsigned int m
= DF_REG_SIZE(df
);
610 if (!df_rd
->block_info
)
613 fprintf (file
, ";; Reaching defs:\n\n");
615 fprintf (file
, " sparse invalidated \t");
616 dump_bitmap (file
, problem_data
->sparse_invalidated_by_call
);
617 fprintf (file
, " dense invalidated \t");
618 dump_bitmap (file
, problem_data
->dense_invalidated_by_call
);
620 for (regno
= 0; regno
< m
; regno
++)
621 if (DF_DEFS_COUNT (regno
))
622 fprintf (file
, "%d[%d,%d] ", regno
,
623 DF_DEFS_BEGIN (regno
),
624 DF_DEFS_COUNT (regno
));
625 fprintf (file
, "\n");
630 /* Debugging info at top of bb. */
633 df_rd_top_dump (basic_block bb
, FILE *file
)
635 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
636 if (!bb_info
|| !bb_info
->in
)
639 fprintf (file
, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info
->in
));
640 dump_bitmap (file
, bb_info
->in
);
641 fprintf (file
, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info
->gen
));
642 dump_bitmap (file
, bb_info
->gen
);
643 fprintf (file
, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info
->kill
));
644 dump_bitmap (file
, bb_info
->kill
);
648 /* Debugging info at top of bb. */
651 df_rd_bottom_dump (basic_block bb
, FILE *file
)
653 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
654 if (!bb_info
|| !bb_info
->out
)
657 fprintf (file
, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info
->out
));
658 dump_bitmap (file
, bb_info
->out
);
661 /* All of the information associated with every instance of the problem. */
663 static struct df_problem problem_RD
=
665 DF_RD
, /* Problem id. */
666 DF_FORWARD
, /* Direction. */
667 df_rd_alloc
, /* Allocate the problem specific data. */
668 NULL
, /* Reset global information. */
669 df_rd_free_bb_info
, /* Free basic block info. */
670 df_rd_local_compute
, /* Local compute function. */
671 df_rd_init_solution
, /* Init the solution specific data. */
672 df_worklist_dataflow
, /* Worklist solver. */
673 NULL
, /* Confluence operator 0. */
674 df_rd_confluence_n
, /* Confluence operator n. */
675 df_rd_transfer_function
, /* Transfer function. */
676 NULL
, /* Finalize function. */
677 df_rd_free
, /* Free all of the problem information. */
678 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
679 df_rd_start_dump
, /* Debugging. */
680 df_rd_top_dump
, /* Debugging start block. */
681 df_rd_bottom_dump
, /* Debugging end block. */
682 NULL
, /* Incremental solution verify start. */
683 NULL
, /* Incremental solution verify end. */
684 NULL
, /* Dependent problem. */
685 TV_DF_RD
, /* Timing variable. */
686 true /* Reset blocks on dropping out of blocks_to_analyze. */
691 /* Create a new DATAFLOW instance and add it to an existing instance
692 of DF. The returned structure is what is used to get at the
696 df_rd_add_problem (void)
698 df_add_problem (&problem_RD
);
703 /*----------------------------------------------------------------------------
706 Find the locations in the function where any use of a pseudo can
707 reach in the backwards direction. In and out bitvectors are built
708 for each basic block. The regnum is used to index into these sets.
709 See df.h for details.
710 ----------------------------------------------------------------------------*/
712 /* Private data used to verify the solution for this problem. */
713 struct df_lr_problem_data
720 /* Set basic block info. */
723 df_lr_set_bb_info (unsigned int index
,
724 struct df_lr_bb_info
*bb_info
)
727 gcc_assert (index
< df_lr
->block_info_size
);
728 df_lr
->block_info
[index
] = bb_info
;
732 /* Free basic block info. */
735 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
738 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
741 BITMAP_FREE (bb_info
->use
);
742 BITMAP_FREE (bb_info
->def
);
743 if (bb_info
->in
== bb_info
->top
)
747 BITMAP_FREE (bb_info
->top
);
748 BITMAP_FREE (bb_info
->ause
);
749 BITMAP_FREE (bb_info
->adef
);
751 BITMAP_FREE (bb_info
->in
);
752 BITMAP_FREE (bb_info
->out
);
753 pool_free (df_lr
->block_pool
, bb_info
);
758 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
759 not touched unless the block is new. */
762 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
764 unsigned int bb_index
;
767 if (!df_lr
->block_pool
)
768 df_lr
->block_pool
= create_alloc_pool ("df_lr_block pool",
769 sizeof (struct df_lr_bb_info
), 50);
771 df_grow_bb_info (df_lr
);
773 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
775 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
778 bitmap_clear (bb_info
->def
);
779 bitmap_clear (bb_info
->use
);
782 bitmap_clear (bb_info
->adef
);
783 bitmap_clear (bb_info
->ause
);
788 bb_info
= (struct df_lr_bb_info
*) pool_alloc (df_lr
->block_pool
);
789 df_lr_set_bb_info (bb_index
, bb_info
);
790 bb_info
->use
= BITMAP_ALLOC (NULL
);
791 bb_info
->def
= BITMAP_ALLOC (NULL
);
792 bb_info
->in
= BITMAP_ALLOC (NULL
);
793 bb_info
->out
= BITMAP_ALLOC (NULL
);
794 bb_info
->top
= bb_info
->in
;
795 bb_info
->adef
= NULL
;
796 bb_info
->ause
= NULL
;
800 df_lr
->optional_p
= false;
804 /* Reset the global solution for recalculation. */
807 df_lr_reset (bitmap all_blocks
)
809 unsigned int bb_index
;
812 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
814 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
815 gcc_assert (bb_info
);
816 bitmap_clear (bb_info
->in
);
817 bitmap_clear (bb_info
->out
);
818 bitmap_clear (bb_info
->top
);
823 /* Compute local live register info for basic block BB. */
826 df_lr_bb_local_compute (unsigned int bb_index
)
828 basic_block bb
= BASIC_BLOCK (bb_index
);
829 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
831 struct df_ref
**def_rec
;
832 struct df_ref
**use_rec
;
834 /* Process the registers set in an exception handler. */
835 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
837 struct df_ref
*def
= *def_rec
;
838 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
840 unsigned int dregno
= DF_REF_REGNO (def
);
841 bitmap_set_bit (bb_info
->def
, dregno
);
842 bitmap_clear_bit (bb_info
->use
, dregno
);
846 /* Process the hardware registers that are always live. */
847 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
849 struct df_ref
*use
= *use_rec
;
850 /* Add use to set of uses in this BB. */
851 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
852 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
855 FOR_BB_INSNS_REVERSE (bb
, insn
)
857 unsigned int uid
= INSN_UID (insn
);
862 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
864 struct df_ref
*def
= *def_rec
;
865 /* If the def is to only part of the reg, it does
866 not kill the other defs that reach here. */
867 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
869 unsigned int dregno
= DF_REF_REGNO (def
);
870 bitmap_set_bit (bb_info
->def
, dregno
);
871 bitmap_clear_bit (bb_info
->use
, dregno
);
875 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
877 struct df_ref
*use
= *use_rec
;
878 /* Add use to set of uses in this BB. */
879 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
882 /* Process the registers set in an exception handler. */
883 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
885 struct df_ref
*def
= *def_rec
;
886 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
887 && (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))))
889 unsigned int dregno
= DF_REF_REGNO (def
);
890 if (bb_info
->adef
== NULL
)
892 gcc_assert (bb_info
->ause
== NULL
);
893 gcc_assert (bb_info
->top
== bb_info
->in
);
894 bb_info
->adef
= BITMAP_ALLOC (NULL
);
895 bb_info
->ause
= BITMAP_ALLOC (NULL
);
896 bb_info
->top
= BITMAP_ALLOC (NULL
);
898 bitmap_set_bit (bb_info
->adef
, dregno
);
903 /* Process the uses that are live into an exception handler. */
904 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
906 struct df_ref
*use
= *use_rec
;
907 /* Add use to set of uses in this BB. */
908 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
910 if (bb_info
->adef
== NULL
)
912 gcc_assert (bb_info
->ause
== NULL
);
913 gcc_assert (bb_info
->top
== bb_info
->in
);
914 bb_info
->adef
= BITMAP_ALLOC (NULL
);
915 bb_info
->ause
= BITMAP_ALLOC (NULL
);
916 bb_info
->top
= BITMAP_ALLOC (NULL
);
918 bitmap_set_bit (bb_info
->ause
, DF_REF_REGNO (use
));
923 /* If the df_live problem is not defined, such as at -O0 and -O1, we
924 still need to keep the luids up to date. This is normally done
925 in the df_live problem since this problem has a forwards
928 df_recompute_luids (bb
);
932 /* Compute local live register info for each basic block within BLOCKS. */
935 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
937 unsigned int bb_index
;
940 bitmap_clear (df
->hardware_regs_used
);
942 /* The all-important stack pointer must always be live. */
943 bitmap_set_bit (df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
945 /* Before reload, there are a few registers that must be forced
946 live everywhere -- which might not already be the case for
947 blocks within infinite loops. */
948 if (!reload_completed
)
950 /* Any reference to any pseudo before reload is a potential
951 reference of the frame pointer. */
952 bitmap_set_bit (df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
954 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
955 /* Pseudos with argument area equivalences may require
956 reloading via the argument pointer. */
957 if (fixed_regs
[ARG_POINTER_REGNUM
])
958 bitmap_set_bit (df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
961 /* Any constant, or pseudo with constant equivalences, may
962 require reloading from memory using the pic register. */
963 if ((unsigned) PIC_OFFSET_TABLE_REGNUM
!= INVALID_REGNUM
964 && fixed_regs
[PIC_OFFSET_TABLE_REGNUM
])
965 bitmap_set_bit (df
->hardware_regs_used
, PIC_OFFSET_TABLE_REGNUM
);
968 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
970 if (bb_index
== EXIT_BLOCK
)
972 /* The exit block is special for this problem and its bits are
973 computed from thin air. */
974 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
975 bitmap_copy (bb_info
->use
, df
->exit_block_uses
);
978 df_lr_bb_local_compute (bb_index
);
981 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
985 /* Initialize the solution vectors. */
988 df_lr_init (bitmap all_blocks
)
990 unsigned int bb_index
;
993 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
995 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
996 bitmap_copy (bb_info
->in
, bb_info
->use
);
997 bitmap_clear (bb_info
->out
);
1002 /* Confluence function that processes infinite loops. This might be a
1003 noreturn function that throws. And even if it isn't, getting the
1004 unwind info right helps debugging. */
1006 df_lr_confluence_0 (basic_block bb
)
1008 bitmap op1
= df_lr_get_bb_info (bb
->index
)->out
;
1009 if (bb
!= EXIT_BLOCK_PTR
)
1010 bitmap_copy (op1
, df
->hardware_regs_used
);
1014 /* Confluence function that ignores fake edges. */
1017 df_lr_confluence_n (edge e
)
1019 bitmap op1
= df_lr_get_bb_info (e
->src
->index
)->out
;
1020 bitmap op2
= df_lr_get_bb_info (e
->dest
->index
)->in
;
1022 /* Call-clobbered registers die across exception and call edges. */
1023 /* ??? Abnormal call edges ignored for the moment, as this gets
1024 confused by sibling call edges, which crashes reg-stack. */
1025 if (e
->flags
& EDGE_EH
)
1026 bitmap_ior_and_compl_into (op1
, op2
, df_invalidated_by_call
);
1028 bitmap_ior_into (op1
, op2
);
1030 bitmap_ior_into (op1
, df
->hardware_regs_used
);
1034 /* Transfer function. */
1037 df_lr_transfer_function (int bb_index
)
1039 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1040 bitmap in
= bb_info
->in
;
1041 bitmap out
= bb_info
->out
;
1042 bitmap use
= bb_info
->use
;
1043 bitmap def
= bb_info
->def
;
1044 bitmap top
= bb_info
->top
;
1045 bitmap ause
= bb_info
->ause
;
1046 bitmap adef
= bb_info
->adef
;
1049 changed
= bitmap_ior_and_compl (top
, use
, out
, def
);
1052 gcc_assert (ause
&& adef
);
1053 changed
|= bitmap_ior_and_compl (in
, ause
, top
, adef
);
1060 /* Run the fast dce as a side effect of building LR. */
1063 df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED
)
1065 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1068 if (df_lr
->problem_data
&& df_lr
->solutions_dirty
)
1070 /* If we are here, then it is because we are both verifying
1071 the solution and the dce changed the function. In that case
1072 the verification info built will be wrong. So we leave the
1073 dirty flag true so that the verifier will skip the checking
1074 part and just clean up.*/
1075 df_lr
->solutions_dirty
= true;
1078 df_lr
->solutions_dirty
= false;
1081 df_lr
->solutions_dirty
= false;
1085 /* Free all storage associated with the problem. */
1090 if (df_lr
->block_info
)
1093 for (i
= 0; i
< df_lr
->block_info_size
; i
++)
1095 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (i
);
1098 BITMAP_FREE (bb_info
->use
);
1099 BITMAP_FREE (bb_info
->def
);
1100 if (bb_info
->in
== bb_info
->top
)
1101 bb_info
->top
= NULL
;
1104 BITMAP_FREE (bb_info
->top
);
1105 BITMAP_FREE (bb_info
->ause
);
1106 BITMAP_FREE (bb_info
->adef
);
1108 BITMAP_FREE (bb_info
->in
);
1109 BITMAP_FREE (bb_info
->out
);
1112 free_alloc_pool (df_lr
->block_pool
);
1114 df_lr
->block_info_size
= 0;
1115 free (df_lr
->block_info
);
1118 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1123 /* Debugging info at top of bb. */
1126 df_lr_top_dump (basic_block bb
, FILE *file
)
1128 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1129 struct df_lr_problem_data
*problem_data
;
1130 if (!bb_info
|| !bb_info
->in
)
1133 fprintf (file
, ";; lr in \t");
1134 df_print_regset (file
, bb_info
->in
);
1135 if (df_lr
->problem_data
)
1137 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1138 fprintf (file
, ";; old in \t");
1139 df_print_regset (file
, problem_data
->in
[bb
->index
]);
1141 fprintf (file
, ";; lr use \t");
1142 df_print_regset (file
, bb_info
->use
);
1143 fprintf (file
, ";; lr def \t");
1144 df_print_regset (file
, bb_info
->def
);
1148 /* Debugging info at bottom of bb. */
1151 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1153 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1154 struct df_lr_problem_data
*problem_data
;
1155 if (!bb_info
|| !bb_info
->out
)
1158 fprintf (file
, ";; lr out \t");
1159 df_print_regset (file
, bb_info
->out
);
1160 if (df_lr
->problem_data
)
1162 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1163 fprintf (file
, ";; old out \t");
1164 df_print_regset (file
, problem_data
->out
[bb
->index
]);
1169 /* Build the datastructure to verify that the solution to the dataflow
1170 equations is not dirty. */
1173 df_lr_verify_solution_start (void)
1176 struct df_lr_problem_data
*problem_data
;
1177 if (df_lr
->solutions_dirty
)
1179 df_lr
->problem_data
= NULL
;
1183 /* Set it true so that the solution is recomputed. */
1184 df_lr
->solutions_dirty
= true;
1186 problem_data
= XNEW (struct df_lr_problem_data
);
1187 df_lr
->problem_data
= problem_data
;
1188 problem_data
->in
= XNEWVEC (bitmap
, last_basic_block
);
1189 problem_data
->out
= XNEWVEC (bitmap
, last_basic_block
);
1193 problem_data
->in
[bb
->index
] = BITMAP_ALLOC (NULL
);
1194 problem_data
->out
[bb
->index
] = BITMAP_ALLOC (NULL
);
1195 bitmap_copy (problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1196 bitmap_copy (problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1201 /* Compare the saved datastructure and the new solution to the dataflow
1205 df_lr_verify_solution_end (void)
1207 struct df_lr_problem_data
*problem_data
;
1210 if (df_lr
->problem_data
== NULL
)
1213 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1215 if (df_lr
->solutions_dirty
)
1216 /* Do not check if the solution is still dirty. See the comment
1217 in df_lr_local_finalize for details. */
1218 df_lr
->solutions_dirty
= false;
1222 if ((!bitmap_equal_p (problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1223 || (!bitmap_equal_p (problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1225 /*df_dump (stderr);*/
1230 /* Cannot delete them immediately because you may want to dump them
1231 if the comparison fails. */
1234 BITMAP_FREE (problem_data
->in
[bb
->index
]);
1235 BITMAP_FREE (problem_data
->out
[bb
->index
]);
1238 free (problem_data
->in
);
1239 free (problem_data
->out
);
1240 free (problem_data
);
1241 df_lr
->problem_data
= NULL
;
1245 /* All of the information associated with every instance of the problem. */
1247 static struct df_problem problem_LR
=
1249 DF_LR
, /* Problem id. */
1250 DF_BACKWARD
, /* Direction. */
1251 df_lr_alloc
, /* Allocate the problem specific data. */
1252 df_lr_reset
, /* Reset global information. */
1253 df_lr_free_bb_info
, /* Free basic block info. */
1254 df_lr_local_compute
, /* Local compute function. */
1255 df_lr_init
, /* Init the solution specific data. */
1256 df_worklist_dataflow
, /* Worklist solver. */
1257 df_lr_confluence_0
, /* Confluence operator 0. */
1258 df_lr_confluence_n
, /* Confluence operator n. */
1259 df_lr_transfer_function
, /* Transfer function. */
1260 df_lr_local_finalize
, /* Finalize function. */
1261 df_lr_free
, /* Free all of the problem information. */
1262 NULL
, /* Remove this problem from the stack of dataflow problems. */
1263 NULL
, /* Debugging. */
1264 df_lr_top_dump
, /* Debugging start block. */
1265 df_lr_bottom_dump
, /* Debugging end block. */
1266 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1267 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1268 NULL
, /* Dependent problem. */
1269 TV_DF_LR
, /* Timing variable. */
1270 false /* Reset blocks on dropping out of blocks_to_analyze. */
1274 /* Create a new DATAFLOW instance and add it to an existing instance
1275 of DF. The returned structure is what is used to get at the
1279 df_lr_add_problem (void)
1281 df_add_problem (&problem_LR
);
1282 /* These will be initialized when df_scan_blocks processes each
1284 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1288 /* Verify that all of the lr related info is consistent and
1292 df_lr_verify_transfer_functions (void)
1305 saved_def
= BITMAP_ALLOC (NULL
);
1306 saved_use
= BITMAP_ALLOC (NULL
);
1307 saved_adef
= BITMAP_ALLOC (NULL
);
1308 saved_ause
= BITMAP_ALLOC (NULL
);
1309 all_blocks
= BITMAP_ALLOC (NULL
);
1313 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1314 bitmap_set_bit (all_blocks
, bb
->index
);
1318 /* Make a copy of the transfer functions and then compute
1319 new ones to see if the transfer functions have
1321 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1324 bitmap_copy (saved_def
, bb_info
->def
);
1325 bitmap_copy (saved_use
, bb_info
->use
);
1326 bitmap_clear (bb_info
->def
);
1327 bitmap_clear (bb_info
->use
);
1332 bitmap_copy (saved_adef
, bb_info
->adef
);
1333 bitmap_copy (saved_ause
, bb_info
->ause
);
1334 bitmap_clear (bb_info
->adef
);
1335 bitmap_clear (bb_info
->ause
);
1340 df_lr_bb_local_compute (bb
->index
);
1341 gcc_assert (bitmap_equal_p (saved_def
, bb_info
->def
));
1342 gcc_assert (bitmap_equal_p (saved_use
, bb_info
->use
));
1346 gcc_assert (bb_info
->adef
);
1347 gcc_assert (bb_info
->ause
);
1348 gcc_assert (bitmap_equal_p (saved_adef
, bb_info
->adef
));
1349 gcc_assert (bitmap_equal_p (saved_ause
, bb_info
->ause
));
1353 gcc_assert (!bb_info
->adef
);
1354 gcc_assert (!bb_info
->ause
);
1360 /* If we do not have basic block info, the block must be in
1361 the list of dirty blocks or else some one has added a
1362 block behind our backs. */
1363 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1366 /* Make sure no one created a block without following
1368 gcc_assert (df_scan_get_bb_info (bb
->index
));
1371 /* Make sure there are no dirty bits in blocks that have been deleted. */
1372 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1375 BITMAP_FREE (saved_def
);
1376 BITMAP_FREE (saved_use
);
1377 BITMAP_FREE (saved_adef
);
1378 BITMAP_FREE (saved_ause
);
1379 BITMAP_FREE (all_blocks
);
1384 /*----------------------------------------------------------------------------
1385 COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
1387 First find the set of uses for registers that are reachable from
1388 the entry block without passing thru a definition. In and out
1389 bitvectors are built for each basic block. The regnum is used to
1390 index into these sets. See df.h for details.
1392 Then the in and out sets here are the anded results of the in and
1393 out sets from the lr and ur
1395 ----------------------------------------------------------------------------*/
1397 /* Private data used to verify the solution for this problem. */
1398 struct df_live_problem_data
1405 /* Set basic block info. */
1408 df_live_set_bb_info (unsigned int index
,
1409 struct df_live_bb_info
*bb_info
)
1411 gcc_assert (df_live
);
1412 gcc_assert (index
< df_live
->block_info_size
);
1413 df_live
->block_info
[index
] = bb_info
;
1417 /* Free basic block info. */
1420 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1423 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1426 BITMAP_FREE (bb_info
->gen
);
1427 BITMAP_FREE (bb_info
->kill
);
1428 BITMAP_FREE (bb_info
->in
);
1429 BITMAP_FREE (bb_info
->out
);
1430 pool_free (df_live
->block_pool
, bb_info
);
1435 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1436 not touched unless the block is new. */
1439 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1441 unsigned int bb_index
;
1444 if (!df_live
->block_pool
)
1445 df_live
->block_pool
= create_alloc_pool ("df_live_block pool",
1446 sizeof (struct df_live_bb_info
), 100);
1448 df_grow_bb_info (df_live
);
1450 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1452 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1455 bitmap_clear (bb_info
->kill
);
1456 bitmap_clear (bb_info
->gen
);
1460 bb_info
= (struct df_live_bb_info
*) pool_alloc (df_live
->block_pool
);
1461 df_live_set_bb_info (bb_index
, bb_info
);
1462 bb_info
->kill
= BITMAP_ALLOC (NULL
);
1463 bb_info
->gen
= BITMAP_ALLOC (NULL
);
1464 bb_info
->in
= BITMAP_ALLOC (NULL
);
1465 bb_info
->out
= BITMAP_ALLOC (NULL
);
1468 df_live
->optional_p
= (optimize
<= 1);
1472 /* Reset the global solution for recalculation. */
1475 df_live_reset (bitmap all_blocks
)
1477 unsigned int bb_index
;
1480 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1482 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1483 gcc_assert (bb_info
);
1484 bitmap_clear (bb_info
->in
);
1485 bitmap_clear (bb_info
->out
);
1490 /* Compute local uninitialized register info for basic block BB. */
1493 df_live_bb_local_compute (unsigned int bb_index
)
1495 basic_block bb
= BASIC_BLOCK (bb_index
);
1496 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1498 struct df_ref
**def_rec
;
1501 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1503 struct df_ref
*def
= *def_rec
;
1504 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
1505 bitmap_set_bit (bb_info
->gen
, DF_REF_REGNO (def
));
1508 FOR_BB_INSNS (bb
, insn
)
1510 unsigned int uid
= INSN_UID (insn
);
1511 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1513 /* Inserting labels does not always trigger the incremental
1517 gcc_assert (!INSN_P (insn
));
1518 df_insn_create_insn_record (insn
);
1521 DF_INSN_LUID (insn
) = luid
;
1526 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1528 struct df_ref
*def
= *def_rec
;
1529 unsigned int regno
= DF_REF_REGNO (def
);
1531 if (DF_REF_FLAGS_IS_SET (def
,
1532 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1533 /* All partial or conditional def
1534 seen are included in the gen set. */
1535 bitmap_set_bit (bb_info
->gen
, regno
);
1536 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1537 /* Only must clobbers for the entire reg destroy the
1539 bitmap_set_bit (bb_info
->kill
, regno
);
1540 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1541 bitmap_set_bit (bb_info
->gen
, regno
);
1545 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1547 struct df_ref
*def
= *def_rec
;
1548 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
1549 bitmap_set_bit (bb_info
->gen
, DF_REF_REGNO (def
));
1554 /* Compute local uninitialized register info. */
1557 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1559 unsigned int bb_index
;
1562 df_grow_insn_info ();
1564 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1567 df_live_bb_local_compute (bb_index
);
1570 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1574 /* Initialize the solution vectors. */
1577 df_live_init (bitmap all_blocks
)
1579 unsigned int bb_index
;
1582 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1584 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1586 bitmap_copy (bb_info
->out
, bb_info
->gen
);
1587 bitmap_clear (bb_info
->in
);
1591 /* Confluence function that ignores fake edges. */
1594 df_live_confluence_n (edge e
)
1596 bitmap op1
= df_live_get_bb_info (e
->dest
->index
)->in
;
1597 bitmap op2
= df_live_get_bb_info (e
->src
->index
)->out
;
1599 if (e
->flags
& EDGE_FAKE
)
1602 bitmap_ior_into (op1
, op2
);
1606 /* Transfer function. */
1609 df_live_transfer_function (int bb_index
)
1611 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1612 bitmap in
= bb_info
->in
;
1613 bitmap out
= bb_info
->out
;
1614 bitmap gen
= bb_info
->gen
;
1615 bitmap kill
= bb_info
->kill
;
1617 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
1621 /* And the LR and UR info to produce the LIVE info. */
1624 df_live_local_finalize (bitmap all_blocks
)
1627 if (df_live
->solutions_dirty
)
1630 unsigned int bb_index
;
1632 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1634 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1635 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1637 /* No register may reach a location where it is not used. Thus
1638 we trim the rr result to the places where it is used. */
1639 bitmap_and_into (bb_live_info
->in
, bb_lr_info
->in
);
1640 bitmap_and_into (bb_live_info
->out
, bb_lr_info
->out
);
1643 df_live
->solutions_dirty
= false;
1648 /* Free all storage associated with the problem. */
1653 if (df_live
->block_info
)
1657 for (i
= 0; i
< df_live
->block_info_size
; i
++)
1659 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (i
);
1662 BITMAP_FREE (bb_info
->gen
);
1663 BITMAP_FREE (bb_info
->kill
);
1664 BITMAP_FREE (bb_info
->in
);
1665 BITMAP_FREE (bb_info
->out
);
1669 free_alloc_pool (df_live
->block_pool
);
1670 df_live
->block_info_size
= 0;
1671 free (df_live
->block_info
);
1673 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1678 /* Debugging info at top of bb. */
1681 df_live_top_dump (basic_block bb
, FILE *file
)
1683 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1684 struct df_live_problem_data
*problem_data
;
1686 if (!bb_info
|| !bb_info
->in
)
1689 fprintf (file
, ";; live in \t");
1690 df_print_regset (file
, bb_info
->in
);
1691 if (df_live
->problem_data
)
1693 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1694 fprintf (file
, ";; old in \t");
1695 df_print_regset (file
, problem_data
->in
[bb
->index
]);
1697 fprintf (file
, ";; live gen \t");
1698 df_print_regset (file
, bb_info
->gen
);
1699 fprintf (file
, ";; live kill\t");
1700 df_print_regset (file
, bb_info
->kill
);
1704 /* Debugging info at bottom of bb. */
1707 df_live_bottom_dump (basic_block bb
, FILE *file
)
1709 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1710 struct df_live_problem_data
*problem_data
;
1712 if (!bb_info
|| !bb_info
->out
)
1715 fprintf (file
, ";; live out \t");
1716 df_print_regset (file
, bb_info
->out
);
1717 if (df_live
->problem_data
)
1719 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1720 fprintf (file
, ";; old out \t");
1721 df_print_regset (file
, problem_data
->out
[bb
->index
]);
1726 /* Build the datastructure to verify that the solution to the dataflow
1727 equations is not dirty. */
1730 df_live_verify_solution_start (void)
1733 struct df_live_problem_data
*problem_data
;
1734 if (df_live
->solutions_dirty
)
1736 df_live
->problem_data
= NULL
;
1740 /* Set it true so that the solution is recomputed. */
1741 df_live
->solutions_dirty
= true;
1743 problem_data
= XNEW (struct df_live_problem_data
);
1744 df_live
->problem_data
= problem_data
;
1745 problem_data
->in
= XNEWVEC (bitmap
, last_basic_block
);
1746 problem_data
->out
= XNEWVEC (bitmap
, last_basic_block
);
1750 problem_data
->in
[bb
->index
] = BITMAP_ALLOC (NULL
);
1751 problem_data
->out
[bb
->index
] = BITMAP_ALLOC (NULL
);
1752 bitmap_copy (problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1753 bitmap_copy (problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1758 /* Compare the saved datastructure and the new solution to the dataflow
1762 df_live_verify_solution_end (void)
1764 struct df_live_problem_data
*problem_data
;
1767 if (df_live
->problem_data
== NULL
)
1770 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1774 if ((!bitmap_equal_p (problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1775 || (!bitmap_equal_p (problem_data
->out
[bb
->index
], DF_LIVE_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_live
->problem_data
= NULL
;
1797 /* All of the information associated with every instance of the problem. */
1799 static struct df_problem problem_LIVE
=
1801 DF_LIVE
, /* Problem id. */
1802 DF_FORWARD
, /* Direction. */
1803 df_live_alloc
, /* Allocate the problem specific data. */
1804 df_live_reset
, /* Reset global information. */
1805 df_live_free_bb_info
, /* Free basic block info. */
1806 df_live_local_compute
, /* Local compute function. */
1807 df_live_init
, /* Init the solution specific data. */
1808 df_worklist_dataflow
, /* Worklist solver. */
1809 NULL
, /* Confluence operator 0. */
1810 df_live_confluence_n
, /* Confluence operator n. */
1811 df_live_transfer_function
, /* Transfer function. */
1812 df_live_local_finalize
, /* Finalize function. */
1813 df_live_free
, /* Free all of the problem information. */
1814 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1815 NULL
, /* Debugging. */
1816 df_live_top_dump
, /* Debugging start block. */
1817 df_live_bottom_dump
, /* Debugging end block. */
1818 df_live_verify_solution_start
,/* Incremental solution verify start. */
1819 df_live_verify_solution_end
, /* Incremental solution verify end. */
1820 &problem_LR
, /* Dependent problem. */
1821 TV_DF_LIVE
, /* Timing variable. */
1822 false /* Reset blocks on dropping out of blocks_to_analyze. */
1826 /* Create a new DATAFLOW instance and add it to an existing instance
1827 of DF. The returned structure is what is used to get at the
1831 df_live_add_problem (void)
1833 df_add_problem (&problem_LIVE
);
1834 /* These will be initialized when df_scan_blocks processes each
1836 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1840 /* Set all of the blocks as dirty. This needs to be done if this
1841 problem is added after all of the insns have been scanned. */
1844 df_live_set_all_dirty (void)
1848 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1853 /* Verify that all of the lr related info is consistent and
1857 df_live_verify_transfer_functions (void)
1867 saved_gen
= BITMAP_ALLOC (NULL
);
1868 saved_kill
= BITMAP_ALLOC (NULL
);
1869 all_blocks
= BITMAP_ALLOC (NULL
);
1871 df_grow_insn_info ();
1875 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1876 bitmap_set_bit (all_blocks
, bb
->index
);
1880 /* Make a copy of the transfer functions and then compute
1881 new ones to see if the transfer functions have
1883 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1886 bitmap_copy (saved_gen
, bb_info
->gen
);
1887 bitmap_copy (saved_kill
, bb_info
->kill
);
1888 bitmap_clear (bb_info
->gen
);
1889 bitmap_clear (bb_info
->kill
);
1891 df_live_bb_local_compute (bb
->index
);
1892 gcc_assert (bitmap_equal_p (saved_gen
, bb_info
->gen
));
1893 gcc_assert (bitmap_equal_p (saved_kill
, bb_info
->kill
));
1898 /* If we do not have basic block info, the block must be in
1899 the list of dirty blocks or else some one has added a
1900 block behind our backs. */
1901 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1904 /* Make sure no one created a block without following
1906 gcc_assert (df_scan_get_bb_info (bb
->index
));
1909 /* Make sure there are no dirty bits in blocks that have been deleted. */
1910 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1912 BITMAP_FREE (saved_gen
);
1913 BITMAP_FREE (saved_kill
);
1914 BITMAP_FREE (all_blocks
);
1919 /*----------------------------------------------------------------------------
1920 UNINITIALIZED REGISTERS WITH EARLYCLOBBER
1922 Find the set of uses for registers that are reachable from the entry
1923 block without passing thru a definition. In and out bitvectors are built
1924 for each basic block. The regnum is used to index into these sets.
1925 See df.h for details.
1927 This is a variant of the UR problem above that has a lot of special
1928 features just for the register allocation phase. This problem
1929 should go away if someone would fix the interference graph.
1931 ----------------------------------------------------------------------------*/
1933 /* Private data used to compute the solution for this problem. These
1934 data structures are not accessible outside of this module. */
1935 struct df_urec_problem_data
1937 bool earlyclobbers_found
; /* True if any instruction contains an
1940 bitmap stack_regs
; /* Registers that may be allocated to a STACK_REGS. */
1945 /* Set basic block info. */
1948 df_urec_set_bb_info (unsigned int index
,
1949 struct df_urec_bb_info
*bb_info
)
1951 gcc_assert (df_urec
);
1952 gcc_assert (index
< df_urec
->block_info_size
);
1953 df_urec
->block_info
[index
] = bb_info
;
1957 /* Free basic block info. */
1960 df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1963 struct df_urec_bb_info
*bb_info
= (struct df_urec_bb_info
*) vbb_info
;
1966 BITMAP_FREE (bb_info
->gen
);
1967 BITMAP_FREE (bb_info
->kill
);
1968 BITMAP_FREE (bb_info
->in
);
1969 BITMAP_FREE (bb_info
->out
);
1970 BITMAP_FREE (bb_info
->earlyclobber
);
1971 pool_free (df_urec
->block_pool
, bb_info
);
1976 /* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
1977 not touched unless the block is new. */
1980 df_urec_alloc (bitmap all_blocks
)
1983 unsigned int bb_index
;
1985 struct df_urec_problem_data
*problem_data
1986 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
1988 if (!df_urec
->block_pool
)
1989 df_urec
->block_pool
= create_alloc_pool ("df_urec_block pool",
1990 sizeof (struct df_urec_bb_info
), 50);
1992 if (!df_urec
->problem_data
)
1994 problem_data
= XNEW (struct df_urec_problem_data
);
1995 df_urec
->problem_data
= problem_data
;
1997 problem_data
->earlyclobbers_found
= false;
1999 df_grow_bb_info (df_urec
);
2001 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2003 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2006 bitmap_clear (bb_info
->kill
);
2007 bitmap_clear (bb_info
->gen
);
2008 bitmap_clear (bb_info
->earlyclobber
);
2012 bb_info
= (struct df_urec_bb_info
*) pool_alloc (df_urec
->block_pool
);
2013 df_urec_set_bb_info (bb_index
, bb_info
);
2014 bb_info
->kill
= BITMAP_ALLOC (NULL
);
2015 bb_info
->gen
= BITMAP_ALLOC (NULL
);
2016 bb_info
->in
= BITMAP_ALLOC (NULL
);
2017 bb_info
->out
= BITMAP_ALLOC (NULL
);
2018 bb_info
->top
= BITMAP_ALLOC (NULL
);
2019 bb_info
->earlyclobber
= BITMAP_ALLOC (NULL
);
2022 df_urec
->optional_p
= true;
2026 /* The function modifies local info for register REG being changed in
2027 SETTER. DATA is used to pass the current basic block info. */
2030 df_urec_mark_reg_change (rtx reg
, const_rtx setter
, void *data
)
2035 struct df_urec_bb_info
*bb_info
= (struct df_urec_bb_info
*) data
;
2037 if (GET_CODE (reg
) == SUBREG
)
2038 reg
= SUBREG_REG (reg
);
2043 regno
= REGNO (reg
);
2044 if (regno
< FIRST_PSEUDO_REGISTER
)
2046 endregno
= END_HARD_REGNO (reg
);
2047 for (i
= regno
; i
< endregno
; i
++)
2049 bitmap_set_bit (bb_info
->kill
, i
);
2051 if (GET_CODE (setter
) != CLOBBER
)
2052 bitmap_set_bit (bb_info
->gen
, i
);
2054 bitmap_clear_bit (bb_info
->gen
, i
);
2059 bitmap_set_bit (bb_info
->kill
, regno
);
2061 if (GET_CODE (setter
) != CLOBBER
)
2062 bitmap_set_bit (bb_info
->gen
, regno
);
2064 bitmap_clear_bit (bb_info
->gen
, regno
);
2067 /* Classes of registers which could be early clobbered in the current
2070 static VEC(int,heap
) *earlyclobber_regclass
;
2072 /* This function finds and stores register classes that could be early
2073 clobbered in INSN. If any earlyclobber classes are found, the function
2074 returns TRUE, in all other cases it returns FALSE. */
2077 df_urec_check_earlyclobber (rtx insn
)
2082 extract_insn (insn
);
2084 VEC_truncate (int, earlyclobber_regclass
, 0);
2085 for (opno
= 0; opno
< recog_data
.n_operands
; opno
++)
2090 enum reg_class
class;
2091 const char *p
= recog_data
.constraints
[opno
];
2100 case '=': case '+': case '?':
2103 case 'm': case '<': case '>': case 'V': case 'o':
2104 case 'E': case 'F': case 'G': case 'H':
2105 case 's': case 'i': case 'n':
2106 case 'I': case 'J': case 'K': case 'L':
2107 case 'M': case 'N': case 'O': case 'P':
2109 case '0': case '1': case '2': case '3': case '4':
2110 case '5': case '6': case '7': case '8': case '9':
2111 /* These don't say anything we care about. */
2119 if (amp_p
&& class != NO_REGS
)
2125 VEC_iterate (int, earlyclobber_regclass
, i
, rc
);
2128 if (rc
== (int) class)
2132 /* We use VEC_quick_push here because
2133 earlyclobber_regclass holds no more than
2134 N_REG_CLASSES elements. */
2135 VEC_quick_push (int, earlyclobber_regclass
, (int) class);
2145 class = GENERAL_REGS
;
2149 class = REG_CLASS_FROM_CONSTRAINT (c
, p
);
2154 p
+= CONSTRAINT_LEN (c
, p
);
2161 /* The function checks that pseudo-register *X has a class
2162 intersecting with the class of pseudo-register could be early
2163 clobbered in the same insn.
2165 This function is a no-op if earlyclobber_regclass is empty.
2167 Reload can assign the same hard register to uninitialized
2168 pseudo-register and early clobbered pseudo-register in an insn if
2169 the pseudo-register is used first time in given BB and not lived at
2170 the BB start. To prevent this we don't change life information for
2171 such pseudo-registers. */
2174 df_urec_mark_reg_use_for_earlyclobber (rtx
*x
, void *data
)
2176 enum reg_class pref_class
, alt_class
;
2178 struct df_urec_bb_info
*bb_info
= (struct df_urec_bb_info
*) data
;
2180 if (REG_P (*x
) && REGNO (*x
) >= FIRST_PSEUDO_REGISTER
)
2185 if (bitmap_bit_p (bb_info
->kill
, regno
)
2186 || bitmap_bit_p (bb_info
->gen
, regno
))
2188 pref_class
= reg_preferred_class (regno
);
2189 alt_class
= reg_alternate_class (regno
);
2190 for (i
= 0; VEC_iterate (int, earlyclobber_regclass
, i
, rc
); i
++)
2192 if (reg_classes_intersect_p (rc
, pref_class
)
2194 && reg_classes_intersect_p (rc
, alt_class
)))
2196 bitmap_set_bit (bb_info
->earlyclobber
, regno
);
2204 /* The function processes all pseudo-registers in *X with the aid of
2205 previous function. */
2208 df_urec_mark_reg_use_for_earlyclobber_1 (rtx
*x
, void *data
)
2210 for_each_rtx (x
, df_urec_mark_reg_use_for_earlyclobber
, data
);
2214 /* Compute local uninitialized register info for basic block BB. */
2217 df_urec_bb_local_compute (unsigned int bb_index
)
2219 basic_block bb
= BASIC_BLOCK (bb_index
);
2220 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2222 struct df_ref
**def_rec
;
2224 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2226 struct df_ref
*def
= *def_rec
;
2227 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2229 unsigned int regno
= DF_REF_REGNO (def
);
2230 bitmap_set_bit (bb_info
->gen
, regno
);
2234 FOR_BB_INSNS (bb
, insn
)
2238 note_stores (PATTERN (insn
), df_urec_mark_reg_change
, bb_info
);
2239 if (df_urec_check_earlyclobber (insn
))
2241 struct df_urec_problem_data
*problem_data
2242 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2243 problem_data
->earlyclobbers_found
= true;
2244 note_uses (&PATTERN (insn
),
2245 df_urec_mark_reg_use_for_earlyclobber_1
, bb_info
);
2250 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2252 struct df_ref
*def
= *def_rec
;
2253 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
2255 unsigned int regno
= DF_REF_REGNO (def
);
2256 bitmap_set_bit (bb_info
->gen
, regno
);
2262 /* Compute local uninitialized register info. */
2265 df_urec_local_compute (bitmap all_blocks
)
2267 unsigned int bb_index
;
2271 HARD_REG_SET stack_hard_regs
, used
;
2272 struct df_urec_problem_data
*problem_data
2273 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2275 /* Any register that MAY be allocated to a register stack (like the
2276 387) is treated poorly. Each such register is marked as being
2277 live everywhere. This keeps the register allocator and the
2278 subsequent passes from doing anything useful with these values.
2280 FIXME: This seems like an incredibly poor idea. */
2282 CLEAR_HARD_REG_SET (stack_hard_regs
);
2283 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
2284 SET_HARD_REG_BIT (stack_hard_regs
, i
);
2285 problem_data
->stack_regs
= BITMAP_ALLOC (NULL
);
2286 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
2288 COPY_HARD_REG_SET (used
, reg_class_contents
[reg_preferred_class (i
)]);
2289 IOR_HARD_REG_SET (used
, reg_class_contents
[reg_alternate_class (i
)]);
2290 AND_HARD_REG_SET (used
, stack_hard_regs
);
2291 if (!hard_reg_set_empty_p (used
))
2292 bitmap_set_bit (problem_data
->stack_regs
, i
);
2296 /* We know that earlyclobber_regclass holds no more than
2297 N_REG_CLASSES elements. See df_urec_check_earlyclobber. */
2298 earlyclobber_regclass
= VEC_alloc (int, heap
, N_REG_CLASSES
);
2300 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2302 df_urec_bb_local_compute (bb_index
);
2305 VEC_free (int, heap
, earlyclobber_regclass
);
2309 /* Initialize the solution vectors. */
2312 df_urec_init (bitmap all_blocks
)
2314 unsigned int bb_index
;
2317 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2319 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2321 bitmap_copy (bb_info
->out
, bb_info
->gen
);
2322 bitmap_clear (bb_info
->in
);
2327 /* Or in the stack regs, hard regs and early clobber regs into the
2328 urec_in sets of all of the blocks. */
2332 df_urec_local_finalize (bitmap all_blocks
)
2334 bitmap tmp
= BITMAP_ALLOC (NULL
);
2336 unsigned int bb_index
;
2337 struct df_urec_problem_data
*problem_data
2338 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2340 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2342 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2343 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
2345 if (bb_index
!= ENTRY_BLOCK
&& bb_index
!= EXIT_BLOCK
)
2347 if (problem_data
->earlyclobbers_found
)
2348 bitmap_ior_into (bb_info
->in
, bb_info
->earlyclobber
);
2351 /* We can not use the same stack register for uninitialized
2352 pseudo-register and another living pseudo-register
2353 because if the uninitialized pseudo-register dies,
2354 subsequent pass reg-stack will be confused (it will
2355 believe that the other register dies). */
2356 bitmap_ior_into (bb_info
->in
, problem_data
->stack_regs
);
2357 bitmap_ior_into (bb_info
->out
, problem_data
->stack_regs
);
2361 /* No register may reach a location where it is not used. Thus
2362 we trim the rr result to the places where it is used. */
2363 bitmap_and_into (bb_info
->in
, bb_lr_info
->in
);
2364 bitmap_and_into (bb_info
->out
, bb_lr_info
->out
);
2365 bitmap_copy (bb_info
->top
, bb_info
->in
);
2366 if (bb_lr_info
->adef
)
2367 bitmap_ior_into (bb_info
->top
, bb_lr_info
->adef
);
2368 bitmap_and_into (bb_info
->top
, bb_lr_info
->top
);
2370 /* Hard registers may still stick in the ur_out set, but not
2371 be in the ur_in set, if their only mention was in a call
2372 in this block. This is because a call kills in the lr
2373 problem but does not kill in the rr problem. To clean
2374 this up, we execute the transfer function on the lr_in
2375 set and then use that to knock bits out of ur_out. */
2376 bitmap_ior_and_compl (tmp
, bb_info
->gen
, bb_lr_info
->in
,
2378 bitmap_and_into (bb_info
->out
, tmp
);
2383 BITMAP_FREE (problem_data
->stack_regs
);
2389 /* Confluence function that ignores fake edges. */
2392 df_urec_confluence_n (edge e
)
2394 bitmap op1
= df_urec_get_bb_info (e
->dest
->index
)->in
;
2395 bitmap op2
= df_urec_get_bb_info (e
->src
->index
)->out
;
2397 if (e
->flags
& EDGE_FAKE
)
2400 bitmap_ior_into (op1
, op2
);
2404 /* Transfer function. */
2407 df_urec_transfer_function (int bb_index
)
2409 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2410 bitmap in
= bb_info
->in
;
2411 bitmap out
= bb_info
->out
;
2412 bitmap gen
= bb_info
->gen
;
2413 bitmap kill
= bb_info
->kill
;
2415 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
2419 /* Free all storage associated with the problem. */
2424 if (df_urec
->block_info
)
2428 for (i
= 0; i
< df_urec
->block_info_size
; i
++)
2430 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (i
);
2433 BITMAP_FREE (bb_info
->gen
);
2434 BITMAP_FREE (bb_info
->kill
);
2435 BITMAP_FREE (bb_info
->in
);
2436 BITMAP_FREE (bb_info
->out
);
2437 BITMAP_FREE (bb_info
->earlyclobber
);
2438 BITMAP_FREE (bb_info
->top
);
2442 free_alloc_pool (df_urec
->block_pool
);
2444 df_urec
->block_info_size
= 0;
2445 free (df_urec
->block_info
);
2446 free (df_urec
->problem_data
);
2452 /* Debugging info at top of bb. */
2455 df_urec_top_dump (basic_block bb
, FILE *file
)
2457 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb
->index
);
2458 if (!bb_info
|| !bb_info
->in
)
2461 fprintf (file
, ";; urec in \t");
2462 df_print_regset (file
, bb_info
->in
);
2463 fprintf (file
, ";; urec gen \t");
2464 df_print_regset (file
, bb_info
->gen
);
2465 fprintf (file
, ";; urec kill\t");
2466 df_print_regset (file
, bb_info
->kill
);
2467 fprintf (file
, ";; urec ec\t");
2468 df_print_regset (file
, bb_info
->earlyclobber
);
2472 /* Debugging info at bottom of bb. */
2475 df_urec_bottom_dump (basic_block bb
, FILE *file
)
2477 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb
->index
);
2478 if (!bb_info
|| !bb_info
->out
)
2480 fprintf (file
, ";; urec out \t");
2481 df_print_regset (file
, bb_info
->out
);
2485 /* All of the information associated with every instance of the problem. */
2487 static struct df_problem problem_UREC
=
2489 DF_UREC
, /* Problem id. */
2490 DF_FORWARD
, /* Direction. */
2491 df_urec_alloc
, /* Allocate the problem specific data. */
2492 NULL
, /* Reset global information. */
2493 df_urec_free_bb_info
, /* Free basic block info. */
2494 df_urec_local_compute
, /* Local compute function. */
2495 df_urec_init
, /* Init the solution specific data. */
2496 df_worklist_dataflow
, /* Worklist solver. */
2497 NULL
, /* Confluence operator 0. */
2498 df_urec_confluence_n
, /* Confluence operator n. */
2499 df_urec_transfer_function
, /* Transfer function. */
2500 df_urec_local_finalize
, /* Finalize function. */
2501 df_urec_free
, /* Free all of the problem information. */
2502 df_urec_free
, /* Remove this problem from the stack of dataflow problems. */
2503 NULL
, /* Debugging. */
2504 df_urec_top_dump
, /* Debugging start block. */
2505 df_urec_bottom_dump
, /* Debugging end block. */
2506 NULL
, /* Incremental solution verify start. */
2507 NULL
, /* Incremental solution verify end. */
2508 &problem_LR
, /* Dependent problem. */
2509 TV_DF_UREC
, /* Timing variable. */
2510 false /* Reset blocks on dropping out of blocks_to_analyze. */
2514 /* Create a new DATAFLOW instance and add it to an existing instance
2515 of DF. The returned structure is what is used to get at the
2519 df_urec_add_problem (void)
2521 df_add_problem (&problem_UREC
);
2526 /*----------------------------------------------------------------------------
2527 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2529 Link either the defs to the uses and / or the uses to the defs.
2531 These problems are set up like the other dataflow problems so that
2532 they nicely fit into the framework. They are much simpler and only
2533 involve a single traversal of instructions and an examination of
2534 the reaching defs information (the dependent problem).
2535 ----------------------------------------------------------------------------*/
2537 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2539 /* Create a du or ud chain from SRC to DST and link it into SRC. */
2542 df_chain_create (struct df_ref
*src
, struct df_ref
*dst
)
2544 struct df_link
*head
= DF_REF_CHAIN (src
);
2545 struct df_link
*link
= pool_alloc (df_chain
->block_pool
);;
2547 DF_REF_CHAIN (src
) = link
;
2554 /* Delete any du or ud chains that start at REF and point to
2557 df_chain_unlink_1 (struct df_ref
*ref
, struct df_ref
*target
)
2559 struct df_link
*chain
= DF_REF_CHAIN (ref
);
2560 struct df_link
*prev
= NULL
;
2564 if (chain
->ref
== target
)
2567 prev
->next
= chain
->next
;
2569 DF_REF_CHAIN (ref
) = chain
->next
;
2570 pool_free (df_chain
->block_pool
, chain
);
2574 chain
= chain
->next
;
2579 /* Delete a du or ud chain that leave or point to REF. */
2582 df_chain_unlink (struct df_ref
*ref
)
2584 struct df_link
*chain
= DF_REF_CHAIN (ref
);
2587 struct df_link
*next
= chain
->next
;
2588 /* Delete the other side if it exists. */
2589 df_chain_unlink_1 (chain
->ref
, ref
);
2590 pool_free (df_chain
->block_pool
, chain
);
2593 DF_REF_CHAIN (ref
) = NULL
;
2597 /* Copy the du or ud chain starting at FROM_REF and attach it to
2601 df_chain_copy (struct df_ref
*to_ref
,
2602 struct df_link
*from_ref
)
2606 df_chain_create (to_ref
, from_ref
->ref
);
2607 from_ref
= from_ref
->next
;
2612 /* Remove this problem from the stack of dataflow problems. */
2615 df_chain_remove_problem (void)
2618 unsigned int bb_index
;
2620 /* Wholesale destruction of the old chains. */
2621 if (df_chain
->block_pool
)
2622 free_alloc_pool (df_chain
->block_pool
);
2624 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2627 struct df_ref
**def_rec
;
2628 struct df_ref
**use_rec
;
2629 basic_block bb
= BASIC_BLOCK (bb_index
);
2631 if (df_chain_problem_p (DF_DU_CHAIN
))
2632 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
2633 DF_REF_CHAIN (*def_rec
) = NULL
;
2634 if (df_chain_problem_p (DF_UD_CHAIN
))
2635 for (use_rec
= df_get_artificial_uses (bb
->index
); *use_rec
; use_rec
++)
2636 DF_REF_CHAIN (*use_rec
) = NULL
;
2638 FOR_BB_INSNS (bb
, insn
)
2640 unsigned int uid
= INSN_UID (insn
);
2644 if (df_chain_problem_p (DF_DU_CHAIN
))
2645 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2646 DF_REF_CHAIN (*def_rec
) = NULL
;
2647 if (df_chain_problem_p (DF_UD_CHAIN
))
2649 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2650 DF_REF_CHAIN (*use_rec
) = NULL
;
2651 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
2652 DF_REF_CHAIN (*use_rec
) = NULL
;
2658 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
2659 df_chain
->block_pool
= NULL
;
2663 /* Remove the chain problem completely. */
2666 df_chain_fully_remove_problem (void)
2668 df_chain_remove_problem ();
2669 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2674 /* Create def-use or use-def chains. */
2677 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2679 df_chain_remove_problem ();
2680 df_chain
->block_pool
= create_alloc_pool ("df_chain_block pool",
2681 sizeof (struct df_link
), 50);
2682 df_chain
->optional_p
= true;
2686 /* Reset all of the chains when the set of basic blocks changes. */
2689 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2691 df_chain_remove_problem ();
2695 /* Create the chains for a list of USEs. */
2698 df_chain_create_bb_process_use (bitmap local_rd
,
2699 struct df_ref
**use_rec
,
2700 enum df_ref_flags top_flag
)
2703 unsigned int def_index
;
2707 struct df_ref
*use
= *use_rec
;
2708 unsigned int uregno
= DF_REF_REGNO (use
);
2709 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2710 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2712 /* Do not want to go through this for an uninitialized var. */
2713 int count
= DF_DEFS_COUNT (uregno
);
2716 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2718 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2719 unsigned int last_index
= first_index
+ count
- 1;
2721 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2724 if (def_index
> last_index
)
2727 def
= DF_DEFS_GET (def_index
);
2728 if (df_chain_problem_p (DF_DU_CHAIN
))
2729 df_chain_create (def
, use
);
2730 if (df_chain_problem_p (DF_UD_CHAIN
))
2731 df_chain_create (use
, def
);
2742 /* Create chains from reaching defs bitmaps for basic block BB. */
2745 df_chain_create_bb (unsigned int bb_index
)
2747 basic_block bb
= BASIC_BLOCK (bb_index
);
2748 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2750 bitmap cpy
= BITMAP_ALLOC (NULL
);
2751 struct df_ref
**def_rec
;
2753 bitmap_copy (cpy
, bb_info
->in
);
2754 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2756 /* Since we are going forwards, process the artificial uses first
2757 then the artificial defs second. */
2760 /* Create the chains for the artificial uses from the EH_USES at the
2761 beginning of the block. */
2763 /* Artificials are only hard regs. */
2764 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2765 df_chain_create_bb_process_use (cpy
,
2766 df_get_artificial_uses (bb
->index
),
2770 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2772 struct df_ref
*def
= *def_rec
;
2773 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2775 unsigned int dregno
= DF_REF_REGNO (def
);
2776 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
2777 bitmap_clear_range (cpy
,
2778 DF_DEFS_BEGIN (dregno
),
2779 DF_DEFS_COUNT (dregno
));
2780 bitmap_set_bit (cpy
, DF_REF_ID (def
));
2784 /* Process the regular instructions next. */
2785 FOR_BB_INSNS (bb
, insn
)
2787 struct df_ref
**def_rec
;
2788 unsigned int uid
= INSN_UID (insn
);
2793 /* Now scan the uses and link them up with the defs that remain
2794 in the cpy vector. */
2796 df_chain_create_bb_process_use (cpy
, DF_INSN_UID_USES (uid
), 0);
2798 if (df
->changeable_flags
& DF_EQ_NOTES
)
2799 df_chain_create_bb_process_use (cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2802 /* Since we are going forwards, process the defs second. This
2803 pass only changes the bits in cpy. */
2804 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2806 struct df_ref
*def
= *def_rec
;
2807 unsigned int dregno
= DF_REF_REGNO (def
);
2808 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2809 || (dregno
>= FIRST_PSEUDO_REGISTER
))
2811 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
2812 bitmap_clear_range (cpy
,
2813 DF_DEFS_BEGIN (dregno
),
2814 DF_DEFS_COUNT (dregno
));
2815 if (!(DF_REF_FLAGS (def
)
2816 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
2817 bitmap_set_bit (cpy
, DF_REF_ID (def
));
2822 /* Create the chains for the artificial uses of the hard registers
2823 at the end of the block. */
2824 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2825 df_chain_create_bb_process_use (cpy
,
2826 df_get_artificial_uses (bb
->index
),
2832 /* Create def-use chains from reaching use bitmaps for basic blocks
2836 df_chain_finalize (bitmap all_blocks
)
2838 unsigned int bb_index
;
2841 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2843 df_chain_create_bb (bb_index
);
2848 /* Free all storage associated with the problem. */
2851 df_chain_free (void)
2853 free_alloc_pool (df_chain
->block_pool
);
2854 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2859 /* Debugging info. */
2862 df_chain_top_dump (basic_block bb
, FILE *file
)
2864 if (df_chain_problem_p (DF_DU_CHAIN
))
2867 struct df_ref
**def_rec
= df_get_artificial_defs (bb
->index
);
2871 fprintf (file
, ";; DU chains for artificial defs\n");
2874 struct df_ref
*def
= *def_rec
;
2875 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2876 df_chain_dump (DF_REF_CHAIN (def
), file
);
2877 fprintf (file
, "\n");
2882 FOR_BB_INSNS (bb
, insn
)
2884 unsigned int uid
= INSN_UID (insn
);
2887 def_rec
= DF_INSN_UID_DEFS (uid
);
2890 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2891 DF_INSN_LUID (insn
), uid
);
2895 struct df_ref
*def
= *def_rec
;
2896 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2897 if (def
->flags
& DF_REF_READ_WRITE
)
2898 fprintf (file
, "read/write ");
2899 df_chain_dump (DF_REF_CHAIN (def
), file
);
2900 fprintf (file
, "\n");
2911 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2913 if (df_chain_problem_p (DF_UD_CHAIN
))
2916 struct df_ref
**use_rec
= df_get_artificial_uses (bb
->index
);
2920 fprintf (file
, ";; UD chains for artificial uses\n");
2923 struct df_ref
*use
= *use_rec
;
2924 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2925 df_chain_dump (DF_REF_CHAIN (use
), file
);
2926 fprintf (file
, "\n");
2931 FOR_BB_INSNS (bb
, insn
)
2933 unsigned int uid
= INSN_UID (insn
);
2936 struct df_ref
**eq_use_rec
= DF_INSN_UID_EQ_USES (uid
);
2937 use_rec
= DF_INSN_UID_USES (uid
);
2938 if (*use_rec
|| *eq_use_rec
)
2940 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2941 DF_INSN_LUID (insn
), uid
);
2945 struct df_ref
*use
= *use_rec
;
2946 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2947 if (use
->flags
& DF_REF_READ_WRITE
)
2948 fprintf (file
, "read/write ");
2949 df_chain_dump (DF_REF_CHAIN (use
), file
);
2950 fprintf (file
, "\n");
2955 struct df_ref
*use
= *eq_use_rec
;
2956 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2957 df_chain_dump (DF_REF_CHAIN (use
), file
);
2958 fprintf (file
, "\n");
2968 static struct df_problem problem_CHAIN
=
2970 DF_CHAIN
, /* Problem id. */
2971 DF_NONE
, /* Direction. */
2972 df_chain_alloc
, /* Allocate the problem specific data. */
2973 df_chain_reset
, /* Reset global information. */
2974 NULL
, /* Free basic block info. */
2975 NULL
, /* Local compute function. */
2976 NULL
, /* Init the solution specific data. */
2977 NULL
, /* Iterative solver. */
2978 NULL
, /* Confluence operator 0. */
2979 NULL
, /* Confluence operator n. */
2980 NULL
, /* Transfer function. */
2981 df_chain_finalize
, /* Finalize function. */
2982 df_chain_free
, /* Free all of the problem information. */
2983 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2984 NULL
, /* Debugging. */
2985 df_chain_top_dump
, /* Debugging start block. */
2986 df_chain_bottom_dump
, /* Debugging end block. */
2987 NULL
, /* Incremental solution verify start. */
2988 NULL
, /* Incremental solution verify end. */
2989 &problem_RD
, /* Dependent problem. */
2990 TV_DF_CHAIN
, /* Timing variable. */
2991 false /* Reset blocks on dropping out of blocks_to_analyze. */
2995 /* Create a new DATAFLOW instance and add it to an existing instance
2996 of DF. The returned structure is what is used to get at the
3000 df_chain_add_problem (enum df_chain_flags chain_flags
)
3002 df_add_problem (&problem_CHAIN
);
3003 df_chain
->local_flags
= (unsigned int)chain_flags
;
3004 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
3007 #undef df_chain_problem_p
3010 /*----------------------------------------------------------------------------
3011 This pass computes REG_DEAD and REG_UNUSED notes.
3012 ----------------------------------------------------------------------------*/
3015 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
3017 df_note
->optional_p
= true;
3020 #ifdef REG_DEAD_DEBUGGING
3022 df_print_note (const char *prefix
, rtx insn
, rtx note
)
3026 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
3027 print_rtl (dump_file
, note
);
3028 fprintf (dump_file
, "\n");
3034 /* After reg-stack, the x86 floating point stack regs are difficult to
3035 analyze because of all of the pushes, pops and rotations. Thus, we
3036 just leave the notes alone. */
3040 df_ignore_stack_reg (int regno
)
3042 return regstack_completed
3043 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
3047 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
3054 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3055 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3058 df_kill_notes (rtx insn
, rtx
*old_dead_notes
, rtx
*old_unused_notes
)
3060 rtx
*pprev
= ®_NOTES (insn
);
3067 switch (REG_NOTE_KIND (link
))
3070 /* After reg-stack, we need to ignore any unused notes
3071 for the stack registers. */
3072 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3074 pprev
= &XEXP (link
, 1);
3079 rtx next
= XEXP (link
, 1);
3080 #ifdef REG_DEAD_DEBUGGING
3081 df_print_note ("deleting: ", insn
, link
);
3083 XEXP (link
, 1) = dead
;
3085 *pprev
= link
= next
;
3090 /* After reg-stack, we need to ignore any unused notes
3091 for the stack registers. */
3092 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3094 pprev
= &XEXP (link
, 1);
3099 rtx next
= XEXP (link
, 1);
3100 #ifdef REG_DEAD_DEBUGGING
3101 df_print_note ("deleting: ", insn
, link
);
3103 XEXP (link
, 1) = unused
;
3105 *pprev
= link
= next
;
3110 pprev
= &XEXP (link
, 1);
3116 *old_dead_notes
= dead
;
3117 *old_unused_notes
= unused
;
3121 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3122 list, otherwise create a new one. */
3125 df_set_note (enum reg_note note_type
, rtx insn
, rtx old
, rtx reg
)
3131 if (XEXP (this, 0) == reg
)
3134 XEXP (prev
, 1) = XEXP (this, 1);
3136 old
= XEXP (this, 1);
3137 XEXP (this, 1) = REG_NOTES (insn
);
3138 REG_NOTES (insn
) = this;
3144 this = XEXP (this, 1);
3147 /* Did not find the note. */
3148 REG_NOTES (insn
) = alloc_EXPR_LIST (note_type
, reg
, REG_NOTES (insn
));
3152 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3153 arguments. Return true if the register value described by MWS's
3154 mw_reg is known to be completely unused, and if mw_reg can therefore
3155 be used in a REG_UNUSED note. */
3158 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
3159 bitmap live
, bitmap artificial_uses
)
3163 /* If MWS describes a partial reference, create REG_UNUSED notes for
3164 individual hard registers. */
3165 if (mws
->flags
& DF_REF_PARTIAL
)
3168 /* Likewise if some part of the register is used. */
3169 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3170 if (bitmap_bit_p (live
, r
)
3171 || bitmap_bit_p (artificial_uses
, r
))
3174 gcc_assert (REG_P (mws
->mw_reg
));
3178 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3179 based on the bits in LIVE. Do not generate notes for registers in
3180 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3181 not generated if the reg is both read and written by the
3186 df_set_unused_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3187 bitmap live
, bitmap do_not_gen
,
3188 bitmap artificial_uses
)
3192 #ifdef REG_DEAD_DEBUGGING
3194 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
3195 mws
->start_regno
, mws
->end_regno
);
3198 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
3200 unsigned int regno
= mws
->start_regno
;
3201 old
= df_set_note (REG_UNUSED
, insn
, old
, mws
->mw_reg
);
3203 #ifdef REG_DEAD_DEBUGGING
3204 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3206 bitmap_set_bit (do_not_gen
, regno
);
3207 /* Only do this if the value is totally dead. */
3210 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3212 if (!bitmap_bit_p (live
, r
)
3213 && !bitmap_bit_p (artificial_uses
, r
))
3215 old
= df_set_note (REG_UNUSED
, insn
, old
, regno_reg_rtx
[r
]);
3216 #ifdef REG_DEAD_DEBUGGING
3217 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3220 bitmap_set_bit (do_not_gen
, r
);
3226 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3227 arguments. Return true if the register value described by MWS's
3228 mw_reg is known to be completely dead, and if mw_reg can therefore
3229 be used in a REG_DEAD note. */
3232 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
3233 bitmap live
, bitmap artificial_uses
,
3238 /* If MWS describes a partial reference, create REG_DEAD notes for
3239 individual hard registers. */
3240 if (mws
->flags
& DF_REF_PARTIAL
)
3243 /* Likewise if some part of the register is not dead. */
3244 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3245 if (bitmap_bit_p (live
, r
)
3246 || bitmap_bit_p (artificial_uses
, r
)
3247 || bitmap_bit_p (do_not_gen
, r
))
3250 gcc_assert (REG_P (mws
->mw_reg
));
3254 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3255 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3256 from being set if the instruction both reads and writes the
3260 df_set_dead_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3261 bitmap live
, bitmap do_not_gen
,
3262 bitmap artificial_uses
)
3266 #ifdef REG_DEAD_DEBUGGING
3269 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3270 mws
->start_regno
, mws
->end_regno
);
3271 df_print_regset (dump_file
, do_not_gen
);
3272 fprintf (dump_file
, " live =");
3273 df_print_regset (dump_file
, live
);
3274 fprintf (dump_file
, " artificial uses =");
3275 df_print_regset (dump_file
, artificial_uses
);
3279 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3281 /* Add a dead note for the entire multi word register. */
3282 old
= df_set_note (REG_DEAD
, insn
, old
, mws
->mw_reg
);
3283 #ifdef REG_DEAD_DEBUGGING
3284 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3289 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3290 if (!bitmap_bit_p (live
, r
)
3291 && !bitmap_bit_p (artificial_uses
, r
)
3292 && !bitmap_bit_p (do_not_gen
, r
))
3294 old
= df_set_note (REG_DEAD
, insn
, old
, regno_reg_rtx
[r
]);
3295 #ifdef REG_DEAD_DEBUGGING
3296 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3304 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3305 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3308 df_create_unused_note (rtx insn
, rtx old
, struct df_ref
*def
,
3309 bitmap live
, bitmap artificial_uses
)
3311 unsigned int dregno
= DF_REF_REGNO (def
);
3313 #ifdef REG_DEAD_DEBUGGING
3316 fprintf (dump_file
, " regular looking at def ");
3317 df_ref_debug (def
, dump_file
);
3321 if (!(bitmap_bit_p (live
, dregno
)
3322 || (DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3323 || bitmap_bit_p (artificial_uses
, dregno
)
3324 || df_ignore_stack_reg (dregno
)))
3326 rtx reg
= (DF_REF_LOC (def
))
3327 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3328 old
= df_set_note (REG_UNUSED
, insn
, old
, reg
);
3329 #ifdef REG_DEAD_DEBUGGING
3330 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3338 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3339 info: lifetime, bb, and number of defs and uses for basic block
3340 BB. The three bitvectors are scratch regs used here. */
3343 df_note_bb_compute (unsigned int bb_index
,
3344 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3346 basic_block bb
= BASIC_BLOCK (bb_index
);
3348 struct df_ref
**def_rec
;
3349 struct df_ref
**use_rec
;
3351 bitmap_copy (live
, df_get_live_out (bb
));
3352 bitmap_clear (artificial_uses
);
3354 #ifdef REG_DEAD_DEBUGGING
3357 fprintf (dump_file
, "live at bottom ");
3358 df_print_regset (dump_file
, live
);
3362 /* Process the artificial defs and uses at the bottom of the block
3363 to begin processing. */
3364 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3366 struct df_ref
*def
= *def_rec
;
3367 #ifdef REG_DEAD_DEBUGGING
3369 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3372 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3373 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3376 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3378 struct df_ref
*use
= *use_rec
;
3379 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3381 unsigned int regno
= DF_REF_REGNO (use
);
3382 bitmap_set_bit (live
, regno
);
3384 /* Notes are not generated for any of the artificial registers
3385 at the bottom of the block. */
3386 bitmap_set_bit (artificial_uses
, regno
);
3390 #ifdef REG_DEAD_DEBUGGING
3393 fprintf (dump_file
, "live before artificials out ");
3394 df_print_regset (dump_file
, live
);
3398 FOR_BB_INSNS_REVERSE (bb
, insn
)
3400 unsigned int uid
= INSN_UID (insn
);
3401 struct df_mw_hardreg
**mws_rec
;
3403 rtx old_unused_notes
;
3408 bitmap_clear (do_not_gen
);
3409 df_kill_notes (insn
, &old_dead_notes
, &old_unused_notes
);
3411 /* Process the defs. */
3414 #ifdef REG_DEAD_DEBUGGING
3417 fprintf (dump_file
, "processing call %d\n live =", INSN_UID (insn
));
3418 df_print_regset (dump_file
, live
);
3421 /* We only care about real sets for calls. Clobbers cannot
3422 be depended on to really die. */
3423 mws_rec
= DF_INSN_UID_MWS (uid
);
3426 struct df_mw_hardreg
*mws
= *mws_rec
;
3427 if ((mws
->type
== DF_REF_REG_DEF
)
3428 && !df_ignore_stack_reg (mws
->start_regno
))
3430 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3431 mws
, live
, do_not_gen
,
3436 /* All of the defs except the return value are some sort of
3437 clobber. This code is for the return. */
3438 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3440 struct df_ref
*def
= *def_rec
;
3441 unsigned int dregno
= DF_REF_REGNO (def
);
3442 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3445 = df_create_unused_note (insn
, old_unused_notes
,
3446 def
, live
, artificial_uses
);
3447 bitmap_set_bit (do_not_gen
, dregno
);
3450 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3451 bitmap_clear_bit (live
, dregno
);
3457 mws_rec
= DF_INSN_UID_MWS (uid
);
3460 struct df_mw_hardreg
*mws
= *mws_rec
;
3461 if (mws
->type
== DF_REF_REG_DEF
)
3463 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3464 mws
, live
, do_not_gen
,
3469 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3471 struct df_ref
*def
= *def_rec
;
3472 unsigned int dregno
= DF_REF_REGNO (def
);
3474 = df_create_unused_note (insn
, old_unused_notes
,
3475 def
, live
, artificial_uses
);
3477 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3478 bitmap_set_bit (do_not_gen
, dregno
);
3480 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3481 bitmap_clear_bit (live
, dregno
);
3485 /* Process the uses. */
3486 mws_rec
= DF_INSN_UID_MWS (uid
);
3489 struct df_mw_hardreg
*mws
= *mws_rec
;
3490 if ((mws
->type
!= DF_REF_REG_DEF
)
3491 && !df_ignore_stack_reg (mws
->start_regno
))
3493 = df_set_dead_notes_for_mw (insn
, old_dead_notes
,
3494 mws
, live
, do_not_gen
,
3499 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3501 struct df_ref
*use
= *use_rec
;
3502 unsigned int uregno
= DF_REF_REGNO (use
);
3504 #ifdef REG_DEAD_DEBUGGING
3507 fprintf (dump_file
, " regular looking at use ");
3508 df_ref_debug (use
, dump_file
);
3511 if (!bitmap_bit_p (live
, uregno
))
3513 if ( (!(DF_REF_FLAGS (use
) & DF_REF_MW_HARDREG
))
3514 && (!bitmap_bit_p (do_not_gen
, uregno
))
3515 && (!bitmap_bit_p (artificial_uses
, uregno
))
3516 && (!(DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
))
3517 && (!df_ignore_stack_reg (uregno
)))
3519 rtx reg
= (DF_REF_LOC (use
))
3520 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3521 old_dead_notes
= df_set_note (REG_DEAD
, insn
, old_dead_notes
, reg
);
3523 #ifdef REG_DEAD_DEBUGGING
3524 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3527 /* This register is now live. */
3528 bitmap_set_bit (live
, uregno
);
3532 while (old_unused_notes
)
3534 rtx next
= XEXP (old_unused_notes
, 1);
3535 free_EXPR_LIST_node (old_unused_notes
);
3536 old_unused_notes
= next
;
3538 while (old_dead_notes
)
3540 rtx next
= XEXP (old_dead_notes
, 1);
3541 free_EXPR_LIST_node (old_dead_notes
);
3542 old_dead_notes
= next
;
3548 /* Compute register info: lifetime, bb, and number of defs and uses. */
3550 df_note_compute (bitmap all_blocks
)
3552 unsigned int bb_index
;
3554 bitmap live
= BITMAP_ALLOC (&df_bitmap_obstack
);
3555 bitmap do_not_gen
= BITMAP_ALLOC (&df_bitmap_obstack
);
3556 bitmap artificial_uses
= BITMAP_ALLOC (&df_bitmap_obstack
);
3558 #ifdef REG_DEAD_DEBUGGING
3560 print_rtl_with_bb (dump_file
, get_insns());
3563 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3565 df_note_bb_compute (bb_index
, live
, do_not_gen
, artificial_uses
);
3569 BITMAP_FREE (do_not_gen
);
3570 BITMAP_FREE (artificial_uses
);
3574 /* Free all storage associated with the problem. */
3583 /* All of the information associated every instance of the problem. */
3585 static struct df_problem problem_NOTE
=
3587 DF_NOTE
, /* Problem id. */
3588 DF_NONE
, /* Direction. */
3589 df_note_alloc
, /* Allocate the problem specific data. */
3590 NULL
, /* Reset global information. */
3591 NULL
, /* Free basic block info. */
3592 df_note_compute
, /* Local compute function. */
3593 NULL
, /* Init the solution specific data. */
3594 NULL
, /* Iterative solver. */
3595 NULL
, /* Confluence operator 0. */
3596 NULL
, /* Confluence operator n. */
3597 NULL
, /* Transfer function. */
3598 NULL
, /* Finalize function. */
3599 df_note_free
, /* Free all of the problem information. */
3600 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3601 NULL
, /* Debugging. */
3602 NULL
, /* Debugging start block. */
3603 NULL
, /* Debugging end block. */
3604 NULL
, /* Incremental solution verify start. */
3605 NULL
, /* Incremental solution verify end. */
3607 /* Technically this is only dependent on the live registers problem
3608 but it will produce information if built one of uninitialized
3609 register problems (UR, UREC) is also run. */
3610 &problem_LR
, /* Dependent problem. */
3611 TV_DF_NOTE
, /* Timing variable. */
3612 false /* Reset blocks on dropping out of blocks_to_analyze. */
3616 /* Create a new DATAFLOW instance and add it to an existing instance
3617 of DF. The returned structure is what is used to get at the
3621 df_note_add_problem (void)
3623 df_add_problem (&problem_NOTE
);
3629 /*----------------------------------------------------------------------------
3630 Functions for simulating the effects of single insns.
3632 You can either simulate in the forwards direction, starting from
3633 the top of a block or the backwards direction from the end of the
3634 block. The main difference is that if you go forwards, the uses
3635 are examined first then the defs, and if you go backwards, the defs
3636 are examined first then the uses.
3638 If you start at the top of the block, use one of DF_LIVE_IN or
3639 DF_LR_IN. If you start at the bottom of the block use one of
3640 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3641 THEY WILL BE DESTROYED.
3643 ----------------------------------------------------------------------------*/
3646 /* Find the set of DEFs for INSN. */
3649 df_simulate_find_defs (rtx insn
, bitmap defs
)
3651 struct df_ref
**def_rec
;
3652 unsigned int uid
= INSN_UID (insn
);
3654 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3656 struct df_ref
*def
= *def_rec
;
3657 /* If the def is to only part of the reg, it does
3658 not kill the other defs that reach here. */
3659 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3660 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3665 /* Simulate the effects of the defs of INSN on LIVE. */
3668 df_simulate_defs (rtx insn
, bitmap live
)
3670 struct df_ref
**def_rec
;
3671 unsigned int uid
= INSN_UID (insn
);
3673 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3675 struct df_ref
*def
= *def_rec
;
3676 unsigned int dregno
= DF_REF_REGNO (def
);
3678 /* If the def is to only part of the reg, it does
3679 not kill the other defs that reach here. */
3680 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3681 bitmap_clear_bit (live
, dregno
);
3686 /* Simulate the effects of the uses of INSN on LIVE. */
3689 df_simulate_uses (rtx insn
, bitmap live
)
3691 struct df_ref
**use_rec
;
3692 unsigned int uid
= INSN_UID (insn
);
3694 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3696 struct df_ref
*use
= *use_rec
;
3697 /* Add use to set of uses in this BB. */
3698 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3703 /* Add back the always live regs in BB to LIVE. */
3706 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3708 /* These regs are considered always live so if they end up dying
3709 because of some def, we need to bring the back again. */
3710 if (df_has_eh_preds (bb
))
3711 bitmap_ior_into (live
, df
->eh_block_artificial_uses
);
3713 bitmap_ior_into (live
, df
->regular_block_artificial_uses
);
3717 /* Apply the artificial uses and defs at the top of BB in a forwards
3721 df_simulate_artificial_refs_at_top (basic_block bb
, bitmap live
)
3723 struct df_ref
**def_rec
;
3724 struct df_ref
**use_rec
;
3725 int bb_index
= bb
->index
;
3727 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3729 struct df_ref
*use
= *use_rec
;
3730 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3731 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3734 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3736 struct df_ref
*def
= *def_rec
;
3737 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3738 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3743 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3746 df_simulate_one_insn_forwards (basic_block bb
, rtx insn
, bitmap live
)
3748 if (! INSN_P (insn
))
3751 df_simulate_uses (insn
, live
);
3752 df_simulate_defs (insn
, live
);
3753 df_simulate_fixup_sets (bb
, live
);
3757 /* Apply the artificial uses and defs at the end of BB in a backwards
3761 df_simulate_artificial_refs_at_end (basic_block bb
, bitmap live
)
3763 struct df_ref
**def_rec
;
3764 struct df_ref
**use_rec
;
3765 int bb_index
= bb
->index
;
3767 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3769 struct df_ref
*def
= *def_rec
;
3770 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3771 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3774 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3776 struct df_ref
*use
= *use_rec
;
3777 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3778 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3783 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3786 df_simulate_one_insn_backwards (basic_block bb
, rtx insn
, bitmap live
)
3788 if (! INSN_P (insn
))
3791 df_simulate_defs (insn
, live
);
3792 df_simulate_uses (insn
, live
);
3793 df_simulate_fixup_sets (bb
, live
);