1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008, 2009 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "alloc-pool.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
48 /* Note that turning REG_DEAD_DEBUGGING on will cause
49 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50 addresses in the dumps. */
52 #define REG_DEAD_DEBUGGING
55 #define DF_SPARSE_THRESHOLD 32
57 static bitmap seen_in_block
= NULL
;
58 static bitmap seen_in_insn
= NULL
;
61 /*----------------------------------------------------------------------------
62 Public functions access functions for the dataflow problems.
63 ----------------------------------------------------------------------------*/
64 /* Get the live at out set for BB no matter what problem happens to be
65 defined. This function is used by the register allocators who
66 choose different dataflow problems depending on the optimization
70 df_get_live_out (basic_block bb
)
75 return DF_LIVE_OUT (bb
);
77 return DF_LR_OUT (bb
);
80 /* Get the live at in set for BB no matter what problem happens to be
81 defined. This function is used by the register allocators who
82 choose different dataflow problems depending on the optimization
86 df_get_live_in (basic_block bb
)
91 return DF_LIVE_IN (bb
);
96 /*----------------------------------------------------------------------------
98 ----------------------------------------------------------------------------*/
100 /* Generic versions to get the void* version of the block info. Only
101 used inside the problem instance vectors. */
103 /* Grow the bb_info array. */
106 df_grow_bb_info (struct dataflow
*dflow
)
108 unsigned int new_size
= last_basic_block
+ 1;
109 if (dflow
->block_info_size
< new_size
)
111 new_size
+= new_size
/ 4;
112 dflow
->block_info
= XRESIZEVEC (void *, dflow
->block_info
, new_size
);
113 memset (dflow
->block_info
+ dflow
->block_info_size
, 0,
114 (new_size
- dflow
->block_info_size
) *sizeof (void *));
115 dflow
->block_info_size
= new_size
;
119 /* Dump a def-use or use-def chain for REF to FILE. */
122 df_chain_dump (struct df_link
*link
, FILE *file
)
124 fprintf (file
, "{ ");
125 for (; link
; link
= link
->next
)
127 fprintf (file
, "%c%d(bb %d insn %d) ",
128 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
129 DF_REF_ID (link
->ref
),
130 DF_REF_BBNO (link
->ref
),
131 DF_REF_IS_ARTIFICIAL (link
->ref
) ? -1 : DF_REF_INSN_UID (link
->ref
));
137 /* Print some basic block info as part of df_dump. */
140 df_print_bb_index (basic_block bb
, FILE *file
)
145 fprintf (file
, "\n( ");
146 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
148 basic_block pred
= e
->src
;
149 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
151 fprintf (file
, ")->[%d]->( ", bb
->index
);
152 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
154 basic_block succ
= e
->dest
;
155 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
157 fprintf (file
, ")\n");
161 /*----------------------------------------------------------------------------
164 Find the locations in the function where each definition site for a
165 pseudo reaches. In and out bitvectors are built for each basic
166 block. The id field in the ref is used to index into these sets.
167 See df.h for details.
168 ----------------------------------------------------------------------------*/
170 /* This problem plays a large number of games for the sake of
173 1) The order of the bits in the bitvectors. After the scanning
174 phase, all of the defs are sorted. All of the defs for the reg 0
175 are first, followed by all defs for reg 1 and so on.
177 2) There are two kill sets, one if the number of defs is less or
178 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
181 <= : Data is built directly in the kill set.
183 > : One level of indirection is used to keep from generating long
184 strings of 1 bits in the kill sets. Bitvectors that are indexed
185 by the regnum are used to represent that there is a killing def
186 for the register. The confluence and transfer functions use
187 these along with the bitmap_clear_range call to remove ranges of
188 bits without actually generating a knockout vector.
190 The kill and sparse_kill and the dense_invalidated_by_call and
191 sparse_invalidated_by_call both play this game. */
193 /* Private data used to compute the solution for this problem. These
194 data structures are not accessible outside of this module. */
195 struct df_rd_problem_data
197 /* The set of defs to regs invalidated by call. */
198 bitmap sparse_invalidated_by_call
;
199 /* The set of defs to regs invalidate by call for rd. */
200 bitmap dense_invalidated_by_call
;
201 /* An obstack for the bitmaps we need for this problem. */
202 bitmap_obstack rd_bitmaps
;
205 /* Set basic block info. */
208 df_rd_set_bb_info (unsigned int index
,
209 struct df_rd_bb_info
*bb_info
)
212 gcc_assert (index
< df_rd
->block_info_size
);
213 df_rd
->block_info
[index
] = bb_info
;
217 /* Free basic block info. */
220 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
223 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
226 BITMAP_FREE (bb_info
->kill
);
227 BITMAP_FREE (bb_info
->sparse_kill
);
228 BITMAP_FREE (bb_info
->gen
);
229 BITMAP_FREE (bb_info
->in
);
230 BITMAP_FREE (bb_info
->out
);
231 pool_free (df_rd
->block_pool
, bb_info
);
236 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
237 not touched unless the block is new. */
240 df_rd_alloc (bitmap all_blocks
)
242 unsigned int bb_index
;
244 struct df_rd_problem_data
*problem_data
;
246 if (!df_rd
->block_pool
)
247 df_rd
->block_pool
= create_alloc_pool ("df_rd_block pool",
248 sizeof (struct df_rd_bb_info
), 50);
250 if (df_rd
->problem_data
)
252 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
253 bitmap_clear (problem_data
->sparse_invalidated_by_call
);
254 bitmap_clear (problem_data
->dense_invalidated_by_call
);
258 problem_data
= XNEW (struct df_rd_problem_data
);
259 df_rd
->problem_data
= problem_data
;
261 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
262 problem_data
->sparse_invalidated_by_call
263 = BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
264 problem_data
->dense_invalidated_by_call
265 = BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
268 df_grow_bb_info (df_rd
);
270 /* Because of the clustering of all use sites for the same pseudo,
271 we have to process all of the blocks before doing the
274 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
276 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
279 bitmap_clear (bb_info
->kill
);
280 bitmap_clear (bb_info
->sparse_kill
);
281 bitmap_clear (bb_info
->gen
);
285 bb_info
= (struct df_rd_bb_info
*) pool_alloc (df_rd
->block_pool
);
286 df_rd_set_bb_info (bb_index
, bb_info
);
287 bb_info
->kill
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
288 bb_info
->sparse_kill
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
289 bb_info
->gen
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
290 bb_info
->in
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
291 bb_info
->out
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
294 df_rd
->optional_p
= true;
298 /* Add the effect of the top artificial defs of BB to the reaching definitions
302 df_rd_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_rd
)
304 int bb_index
= bb
->index
;
306 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
308 df_ref def
= *def_rec
;
309 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
311 unsigned int dregno
= DF_REF_REGNO (def
);
312 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
313 bitmap_clear_range (local_rd
,
314 DF_DEFS_BEGIN (dregno
),
315 DF_DEFS_COUNT (dregno
));
316 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
321 /* Add the effect of the defs of INSN to the reaching definitions bitmap
325 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
328 unsigned uid
= INSN_UID (insn
);
331 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
333 df_ref def
= *def_rec
;
334 unsigned int dregno
= DF_REF_REGNO (def
);
335 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
336 || (dregno
>= FIRST_PSEUDO_REGISTER
))
338 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
339 bitmap_clear_range (local_rd
,
340 DF_DEFS_BEGIN (dregno
),
341 DF_DEFS_COUNT (dregno
));
342 if (!(DF_REF_FLAGS (def
)
343 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
344 bitmap_set_bit (local_rd
, DF_REF_ID (def
));
349 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
350 more complicated than just simulating, because we must produce the
351 gen and kill sets and hence deal with the two possible representations
355 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
361 df_ref def
= *def_rec
;
362 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
364 unsigned int regno
= DF_REF_REGNO (def
);
365 unsigned int begin
= DF_DEFS_BEGIN (regno
);
366 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
368 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
369 || (regno
>= FIRST_PSEUDO_REGISTER
))
371 /* Only the last def(s) for a regno in the block has any
373 if (!bitmap_bit_p (seen_in_block
, regno
))
375 /* The first def for regno in insn gets to knock out the
376 defs from other instructions. */
377 if ((!bitmap_bit_p (seen_in_insn
, regno
))
378 /* If the def is to only part of the reg, it does
379 not kill the other defs that reach here. */
380 && (!(DF_REF_FLAGS (def
) &
381 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
383 if (n_defs
> DF_SPARSE_THRESHOLD
)
385 bitmap_set_bit (bb_info
->sparse_kill
, regno
);
386 bitmap_clear_range(bb_info
->gen
, begin
, n_defs
);
390 bitmap_set_range (bb_info
->kill
, begin
, n_defs
);
391 bitmap_clear_range (bb_info
->gen
, begin
, n_defs
);
395 bitmap_set_bit (seen_in_insn
, regno
);
396 /* All defs for regno in the instruction may be put into
398 if (!(DF_REF_FLAGS (def
)
399 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
400 bitmap_set_bit (bb_info
->gen
, DF_REF_ID (def
));
408 /* Compute local reaching def info for basic block BB. */
411 df_rd_bb_local_compute (unsigned int bb_index
)
413 basic_block bb
= BASIC_BLOCK (bb_index
);
414 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
417 bitmap_clear (seen_in_block
);
418 bitmap_clear (seen_in_insn
);
420 /* Artificials are only hard regs. */
421 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
422 df_rd_bb_local_compute_process_def (bb_info
,
423 df_get_artificial_defs (bb_index
),
426 FOR_BB_INSNS_REVERSE (bb
, insn
)
428 unsigned int uid
= INSN_UID (insn
);
433 df_rd_bb_local_compute_process_def (bb_info
,
434 DF_INSN_UID_DEFS (uid
), 0);
436 /* This complex dance with the two bitmaps is required because
437 instructions can assign twice to the same pseudo. This
438 generally happens with calls that will have one def for the
439 result and another def for the clobber. If only one vector
440 is used and the clobber goes first, the result will be
442 bitmap_ior_into (seen_in_block
, seen_in_insn
);
443 bitmap_clear (seen_in_insn
);
446 /* Process the artificial defs at the top of the block last since we
447 are going backwards through the block and these are logically at
449 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
450 df_rd_bb_local_compute_process_def (bb_info
,
451 df_get_artificial_defs (bb_index
),
456 /* Compute local reaching def info for each basic block within BLOCKS. */
459 df_rd_local_compute (bitmap all_blocks
)
461 unsigned int bb_index
;
464 struct df_rd_problem_data
*problem_data
465 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
466 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
467 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
469 seen_in_block
= BITMAP_ALLOC (&df_bitmap_obstack
);
470 seen_in_insn
= BITMAP_ALLOC (&df_bitmap_obstack
);
472 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
474 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
476 df_rd_bb_local_compute (bb_index
);
479 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
480 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset
, 0, regno
, bi
)
482 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
483 bitmap_set_bit (sparse_invalidated
, regno
);
485 bitmap_set_range (dense_invalidated
,
486 DF_DEFS_BEGIN (regno
),
487 DF_DEFS_COUNT (regno
));
490 BITMAP_FREE (seen_in_block
);
491 BITMAP_FREE (seen_in_insn
);
495 /* Initialize the solution bit vectors for problem. */
498 df_rd_init_solution (bitmap all_blocks
)
500 unsigned int bb_index
;
503 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
505 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
507 bitmap_copy (bb_info
->out
, bb_info
->gen
);
508 bitmap_clear (bb_info
->in
);
512 /* In of target gets or of out of source. */
515 df_rd_confluence_n (edge e
)
517 bitmap op1
= df_rd_get_bb_info (e
->dest
->index
)->in
;
518 bitmap op2
= df_rd_get_bb_info (e
->src
->index
)->out
;
520 if (e
->flags
& EDGE_FAKE
)
523 if (e
->flags
& EDGE_EH
)
525 struct df_rd_problem_data
*problem_data
526 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
527 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
528 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
531 bitmap tmp
= BITMAP_ALLOC (&df_bitmap_obstack
);
533 bitmap_copy (tmp
, op2
);
534 bitmap_and_compl_into (tmp
, dense_invalidated
);
536 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
538 bitmap_clear_range (tmp
,
539 DF_DEFS_BEGIN (regno
),
540 DF_DEFS_COUNT (regno
));
542 bitmap_ior_into (op1
, tmp
);
546 bitmap_ior_into (op1
, op2
);
550 /* Transfer function. */
553 df_rd_transfer_function (int bb_index
)
555 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
558 bitmap in
= bb_info
->in
;
559 bitmap out
= bb_info
->out
;
560 bitmap gen
= bb_info
->gen
;
561 bitmap kill
= bb_info
->kill
;
562 bitmap sparse_kill
= bb_info
->sparse_kill
;
564 if (bitmap_empty_p (sparse_kill
))
565 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
568 struct df_rd_problem_data
*problem_data
;
569 bool changed
= false;
572 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
573 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
574 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
575 tmp
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
577 bitmap_copy (tmp
, in
);
578 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
580 bitmap_clear_range (tmp
,
581 DF_DEFS_BEGIN (regno
),
582 DF_DEFS_COUNT (regno
));
584 bitmap_and_compl_into (tmp
, kill
);
585 bitmap_ior_into (tmp
, gen
);
586 changed
= !bitmap_equal_p (tmp
, out
);
599 /* Free all storage associated with the problem. */
604 struct df_rd_problem_data
*problem_data
605 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
609 free_alloc_pool (df_rd
->block_pool
);
610 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
612 df_rd
->block_info_size
= 0;
613 free (df_rd
->block_info
);
614 free (df_rd
->problem_data
);
620 /* Debugging info. */
623 df_rd_start_dump (FILE *file
)
625 struct df_rd_problem_data
*problem_data
626 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
627 unsigned int m
= DF_REG_SIZE(df
);
630 if (!df_rd
->block_info
)
633 fprintf (file
, ";; Reaching defs:\n\n");
635 fprintf (file
, " sparse invalidated \t");
636 dump_bitmap (file
, problem_data
->sparse_invalidated_by_call
);
637 fprintf (file
, " dense invalidated \t");
638 dump_bitmap (file
, problem_data
->dense_invalidated_by_call
);
640 for (regno
= 0; regno
< m
; regno
++)
641 if (DF_DEFS_COUNT (regno
))
642 fprintf (file
, "%d[%d,%d] ", regno
,
643 DF_DEFS_BEGIN (regno
),
644 DF_DEFS_COUNT (regno
));
645 fprintf (file
, "\n");
650 /* Debugging info at top of bb. */
653 df_rd_top_dump (basic_block bb
, FILE *file
)
655 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
656 if (!bb_info
|| !bb_info
->in
)
659 fprintf (file
, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info
->in
));
660 dump_bitmap (file
, bb_info
->in
);
661 fprintf (file
, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info
->gen
));
662 dump_bitmap (file
, bb_info
->gen
);
663 fprintf (file
, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info
->kill
));
664 dump_bitmap (file
, bb_info
->kill
);
668 /* Debugging info at top of bb. */
671 df_rd_bottom_dump (basic_block bb
, FILE *file
)
673 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
674 if (!bb_info
|| !bb_info
->out
)
677 fprintf (file
, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info
->out
));
678 dump_bitmap (file
, bb_info
->out
);
681 /* All of the information associated with every instance of the problem. */
683 static struct df_problem problem_RD
=
685 DF_RD
, /* Problem id. */
686 DF_FORWARD
, /* Direction. */
687 df_rd_alloc
, /* Allocate the problem specific data. */
688 NULL
, /* Reset global information. */
689 df_rd_free_bb_info
, /* Free basic block info. */
690 df_rd_local_compute
, /* Local compute function. */
691 df_rd_init_solution
, /* Init the solution specific data. */
692 df_worklist_dataflow
, /* Worklist solver. */
693 NULL
, /* Confluence operator 0. */
694 df_rd_confluence_n
, /* Confluence operator n. */
695 df_rd_transfer_function
, /* Transfer function. */
696 NULL
, /* Finalize function. */
697 df_rd_free
, /* Free all of the problem information. */
698 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
699 df_rd_start_dump
, /* Debugging. */
700 df_rd_top_dump
, /* Debugging start block. */
701 df_rd_bottom_dump
, /* Debugging end block. */
702 NULL
, /* Incremental solution verify start. */
703 NULL
, /* Incremental solution verify end. */
704 NULL
, /* Dependent problem. */
705 TV_DF_RD
, /* Timing variable. */
706 true /* Reset blocks on dropping out of blocks_to_analyze. */
711 /* Create a new RD instance and add it to the existing instance
715 df_rd_add_problem (void)
717 df_add_problem (&problem_RD
);
722 /*----------------------------------------------------------------------------
725 Find the locations in the function where any use of a pseudo can
726 reach in the backwards direction. In and out bitvectors are built
727 for each basic block. The regno is used to index into these sets.
728 See df.h for details.
729 ----------------------------------------------------------------------------*/
731 /* Private data used to verify the solution for this problem. */
732 struct df_lr_problem_data
739 /* Set basic block info. */
742 df_lr_set_bb_info (unsigned int index
,
743 struct df_lr_bb_info
*bb_info
)
746 gcc_assert (index
< df_lr
->block_info_size
);
747 df_lr
->block_info
[index
] = bb_info
;
751 /* Free basic block info. */
754 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
757 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
760 BITMAP_FREE (bb_info
->use
);
761 BITMAP_FREE (bb_info
->def
);
762 BITMAP_FREE (bb_info
->in
);
763 BITMAP_FREE (bb_info
->out
);
764 pool_free (df_lr
->block_pool
, bb_info
);
769 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
770 not touched unless the block is new. */
773 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
775 unsigned int bb_index
;
778 if (!df_lr
->block_pool
)
779 df_lr
->block_pool
= create_alloc_pool ("df_lr_block pool",
780 sizeof (struct df_lr_bb_info
), 50);
782 df_grow_bb_info (df_lr
);
784 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
786 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
789 bitmap_clear (bb_info
->def
);
790 bitmap_clear (bb_info
->use
);
794 bb_info
= (struct df_lr_bb_info
*) pool_alloc (df_lr
->block_pool
);
795 df_lr_set_bb_info (bb_index
, bb_info
);
796 bb_info
->use
= BITMAP_ALLOC (NULL
);
797 bb_info
->def
= BITMAP_ALLOC (NULL
);
798 bb_info
->in
= BITMAP_ALLOC (NULL
);
799 bb_info
->out
= BITMAP_ALLOC (NULL
);
803 df_lr
->optional_p
= false;
807 /* Reset the global solution for recalculation. */
810 df_lr_reset (bitmap all_blocks
)
812 unsigned int bb_index
;
815 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
817 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
818 gcc_assert (bb_info
);
819 bitmap_clear (bb_info
->in
);
820 bitmap_clear (bb_info
->out
);
825 /* Compute local live register info for basic block BB. */
828 df_lr_bb_local_compute (unsigned int bb_index
)
830 basic_block bb
= BASIC_BLOCK (bb_index
);
831 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
836 /* Process the registers set in an exception handler. */
837 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
839 df_ref def
= *def_rec
;
840 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
842 unsigned int dregno
= DF_REF_REGNO (def
);
843 bitmap_set_bit (bb_info
->def
, dregno
);
844 bitmap_clear_bit (bb_info
->use
, dregno
);
848 /* Process the hardware registers that are always live. */
849 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
851 df_ref use
= *use_rec
;
852 /* Add use to set of uses in this BB. */
853 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
854 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
857 FOR_BB_INSNS_REVERSE (bb
, insn
)
859 unsigned int uid
= INSN_UID (insn
);
861 if (!NONDEBUG_INSN_P (insn
))
864 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
866 df_ref def
= *def_rec
;
867 /* If the def is to only part of the reg, it does
868 not kill the other defs that reach here. */
869 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
871 unsigned int dregno
= DF_REF_REGNO (def
);
872 bitmap_set_bit (bb_info
->def
, dregno
);
873 bitmap_clear_bit (bb_info
->use
, dregno
);
877 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
879 df_ref use
= *use_rec
;
880 /* Add use to set of uses in this BB. */
881 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
885 /* Process the registers set in an exception handler or the hard
886 frame pointer if this block is the target of a non local
888 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
890 df_ref def
= *def_rec
;
891 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
893 unsigned int dregno
= DF_REF_REGNO (def
);
894 bitmap_set_bit (bb_info
->def
, dregno
);
895 bitmap_clear_bit (bb_info
->use
, dregno
);
900 /* Process the uses that are live into an exception handler. */
901 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
903 df_ref use
= *use_rec
;
904 /* Add use to set of uses in this BB. */
905 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
906 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
910 /* If the df_live problem is not defined, such as at -O0 and -O1, we
911 still need to keep the luids up to date. This is normally done
912 in the df_live problem since this problem has a forwards
915 df_recompute_luids (bb
);
919 /* Compute local live register info for each basic block within BLOCKS. */
922 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
924 unsigned int bb_index
;
927 bitmap_clear (df
->hardware_regs_used
);
929 /* The all-important stack pointer must always be live. */
930 bitmap_set_bit (df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
932 /* Before reload, there are a few registers that must be forced
933 live everywhere -- which might not already be the case for
934 blocks within infinite loops. */
935 if (!reload_completed
)
937 /* Any reference to any pseudo before reload is a potential
938 reference of the frame pointer. */
939 bitmap_set_bit (df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
941 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
942 /* Pseudos with argument area equivalences may require
943 reloading via the argument pointer. */
944 if (fixed_regs
[ARG_POINTER_REGNUM
])
945 bitmap_set_bit (df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
948 /* Any constant, or pseudo with constant equivalences, may
949 require reloading from memory using the pic register. */
950 if ((unsigned) PIC_OFFSET_TABLE_REGNUM
!= INVALID_REGNUM
951 && fixed_regs
[PIC_OFFSET_TABLE_REGNUM
])
952 bitmap_set_bit (df
->hardware_regs_used
, PIC_OFFSET_TABLE_REGNUM
);
955 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
957 if (bb_index
== EXIT_BLOCK
)
959 /* The exit block is special for this problem and its bits are
960 computed from thin air. */
961 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
962 bitmap_copy (bb_info
->use
, df
->exit_block_uses
);
965 df_lr_bb_local_compute (bb_index
);
968 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
972 /* Initialize the solution vectors. */
975 df_lr_init (bitmap all_blocks
)
977 unsigned int bb_index
;
980 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
982 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
983 bitmap_copy (bb_info
->in
, bb_info
->use
);
984 bitmap_clear (bb_info
->out
);
989 /* Confluence function that processes infinite loops. This might be a
990 noreturn function that throws. And even if it isn't, getting the
991 unwind info right helps debugging. */
993 df_lr_confluence_0 (basic_block bb
)
995 bitmap op1
= df_lr_get_bb_info (bb
->index
)->out
;
996 if (bb
!= EXIT_BLOCK_PTR
)
997 bitmap_copy (op1
, df
->hardware_regs_used
);
1001 /* Confluence function that ignores fake edges. */
1004 df_lr_confluence_n (edge e
)
1006 bitmap op1
= df_lr_get_bb_info (e
->src
->index
)->out
;
1007 bitmap op2
= df_lr_get_bb_info (e
->dest
->index
)->in
;
1009 /* Call-clobbered registers die across exception and call edges. */
1010 /* ??? Abnormal call edges ignored for the moment, as this gets
1011 confused by sibling call edges, which crashes reg-stack. */
1012 if (e
->flags
& EDGE_EH
)
1013 bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
1015 bitmap_ior_into (op1
, op2
);
1017 bitmap_ior_into (op1
, df
->hardware_regs_used
);
1021 /* Transfer function. */
1024 df_lr_transfer_function (int bb_index
)
1026 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1027 bitmap in
= bb_info
->in
;
1028 bitmap out
= bb_info
->out
;
1029 bitmap use
= bb_info
->use
;
1030 bitmap def
= bb_info
->def
;
1032 return bitmap_ior_and_compl (in
, use
, out
, def
);
1036 /* Run the fast dce as a side effect of building LR. */
1039 df_lr_finalize (bitmap all_blocks
)
1041 df_lr
->solutions_dirty
= false;
1042 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1046 /* If dce deletes some instructions, we need to recompute the lr
1047 solution before proceeding further. The problem is that fast
1048 dce is a pessimestic dataflow algorithm. In the case where
1049 it deletes a statement S inside of a loop, the uses inside of
1050 S may not be deleted from the dataflow solution because they
1051 were carried around the loop. While it is conservatively
1052 correct to leave these extra bits, the standards of df
1053 require that we maintain the best possible (least fixed
1054 point) solution. The only way to do that is to redo the
1055 iteration from the beginning. See PR35805 for an
1057 if (df_lr
->solutions_dirty
)
1059 df_clear_flags (DF_LR_RUN_DCE
);
1060 df_lr_alloc (all_blocks
);
1061 df_lr_local_compute (all_blocks
);
1062 df_worklist_dataflow (df_lr
, all_blocks
, df
->postorder
, df
->n_blocks
);
1063 df_lr_finalize (all_blocks
);
1064 df_set_flags (DF_LR_RUN_DCE
);
1070 /* Free all storage associated with the problem. */
1075 if (df_lr
->block_info
)
1078 for (i
= 0; i
< df_lr
->block_info_size
; i
++)
1080 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (i
);
1083 BITMAP_FREE (bb_info
->use
);
1084 BITMAP_FREE (bb_info
->def
);
1085 BITMAP_FREE (bb_info
->in
);
1086 BITMAP_FREE (bb_info
->out
);
1089 free_alloc_pool (df_lr
->block_pool
);
1091 df_lr
->block_info_size
= 0;
1092 free (df_lr
->block_info
);
1095 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1100 /* Debugging info at top of bb. */
1103 df_lr_top_dump (basic_block bb
, FILE *file
)
1105 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1106 struct df_lr_problem_data
*problem_data
;
1107 if (!bb_info
|| !bb_info
->in
)
1110 fprintf (file
, ";; lr in \t");
1111 df_print_regset (file
, bb_info
->in
);
1112 if (df_lr
->problem_data
)
1114 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1115 fprintf (file
, ";; old in \t");
1116 df_print_regset (file
, problem_data
->in
[bb
->index
]);
1118 fprintf (file
, ";; lr use \t");
1119 df_print_regset (file
, bb_info
->use
);
1120 fprintf (file
, ";; lr def \t");
1121 df_print_regset (file
, bb_info
->def
);
1125 /* Debugging info at bottom of bb. */
1128 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1130 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1131 struct df_lr_problem_data
*problem_data
;
1132 if (!bb_info
|| !bb_info
->out
)
1135 fprintf (file
, ";; lr out \t");
1136 df_print_regset (file
, bb_info
->out
);
1137 if (df_lr
->problem_data
)
1139 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1140 fprintf (file
, ";; old out \t");
1141 df_print_regset (file
, problem_data
->out
[bb
->index
]);
1146 /* Build the datastructure to verify that the solution to the dataflow
1147 equations is not dirty. */
1150 df_lr_verify_solution_start (void)
1153 struct df_lr_problem_data
*problem_data
;
1154 if (df_lr
->solutions_dirty
)
1156 df_lr
->problem_data
= NULL
;
1160 /* Set it true so that the solution is recomputed. */
1161 df_lr
->solutions_dirty
= true;
1163 problem_data
= XNEW (struct df_lr_problem_data
);
1164 df_lr
->problem_data
= problem_data
;
1165 problem_data
->in
= XNEWVEC (bitmap
, last_basic_block
);
1166 problem_data
->out
= XNEWVEC (bitmap
, last_basic_block
);
1170 problem_data
->in
[bb
->index
] = BITMAP_ALLOC (NULL
);
1171 problem_data
->out
[bb
->index
] = BITMAP_ALLOC (NULL
);
1172 bitmap_copy (problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1173 bitmap_copy (problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1178 /* Compare the saved datastructure and the new solution to the dataflow
1182 df_lr_verify_solution_end (void)
1184 struct df_lr_problem_data
*problem_data
;
1187 if (df_lr
->problem_data
== NULL
)
1190 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1192 if (df_lr
->solutions_dirty
)
1193 /* Do not check if the solution is still dirty. See the comment
1194 in df_lr_finalize for details. */
1195 df_lr
->solutions_dirty
= false;
1199 if ((!bitmap_equal_p (problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1200 || (!bitmap_equal_p (problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1202 /*df_dump (stderr);*/
1207 /* Cannot delete them immediately because you may want to dump them
1208 if the comparison fails. */
1211 BITMAP_FREE (problem_data
->in
[bb
->index
]);
1212 BITMAP_FREE (problem_data
->out
[bb
->index
]);
1215 free (problem_data
->in
);
1216 free (problem_data
->out
);
1217 free (problem_data
);
1218 df_lr
->problem_data
= NULL
;
1222 /* All of the information associated with every instance of the problem. */
1224 static struct df_problem problem_LR
=
1226 DF_LR
, /* Problem id. */
1227 DF_BACKWARD
, /* Direction. */
1228 df_lr_alloc
, /* Allocate the problem specific data. */
1229 df_lr_reset
, /* Reset global information. */
1230 df_lr_free_bb_info
, /* Free basic block info. */
1231 df_lr_local_compute
, /* Local compute function. */
1232 df_lr_init
, /* Init the solution specific data. */
1233 df_worklist_dataflow
, /* Worklist solver. */
1234 df_lr_confluence_0
, /* Confluence operator 0. */
1235 df_lr_confluence_n
, /* Confluence operator n. */
1236 df_lr_transfer_function
, /* Transfer function. */
1237 df_lr_finalize
, /* Finalize function. */
1238 df_lr_free
, /* Free all of the problem information. */
1239 NULL
, /* Remove this problem from the stack of dataflow problems. */
1240 NULL
, /* Debugging. */
1241 df_lr_top_dump
, /* Debugging start block. */
1242 df_lr_bottom_dump
, /* Debugging end block. */
1243 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1244 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1245 NULL
, /* Dependent problem. */
1246 TV_DF_LR
, /* Timing variable. */
1247 false /* Reset blocks on dropping out of blocks_to_analyze. */
1251 /* Create a new DATAFLOW instance and add it to an existing instance
1252 of DF. The returned structure is what is used to get at the
1256 df_lr_add_problem (void)
1258 df_add_problem (&problem_LR
);
1259 /* These will be initialized when df_scan_blocks processes each
1261 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1265 /* Verify that all of the lr related info is consistent and
1269 df_lr_verify_transfer_functions (void)
1281 saved_def
= BITMAP_ALLOC (NULL
);
1282 saved_use
= BITMAP_ALLOC (NULL
);
1283 saved_adef
= BITMAP_ALLOC (NULL
);
1284 saved_ause
= BITMAP_ALLOC (NULL
);
1285 all_blocks
= BITMAP_ALLOC (NULL
);
1289 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1290 bitmap_set_bit (all_blocks
, bb
->index
);
1294 /* Make a copy of the transfer functions and then compute
1295 new ones to see if the transfer functions have
1297 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1300 bitmap_copy (saved_def
, bb_info
->def
);
1301 bitmap_copy (saved_use
, bb_info
->use
);
1302 bitmap_clear (bb_info
->def
);
1303 bitmap_clear (bb_info
->use
);
1305 df_lr_bb_local_compute (bb
->index
);
1306 gcc_assert (bitmap_equal_p (saved_def
, bb_info
->def
));
1307 gcc_assert (bitmap_equal_p (saved_use
, bb_info
->use
));
1312 /* If we do not have basic block info, the block must be in
1313 the list of dirty blocks or else some one has added a
1314 block behind our backs. */
1315 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1318 /* Make sure no one created a block without following
1320 gcc_assert (df_scan_get_bb_info (bb
->index
));
1323 /* Make sure there are no dirty bits in blocks that have been deleted. */
1324 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1327 BITMAP_FREE (saved_def
);
1328 BITMAP_FREE (saved_use
);
1329 BITMAP_FREE (saved_adef
);
1330 BITMAP_FREE (saved_ause
);
1331 BITMAP_FREE (all_blocks
);
1336 /*----------------------------------------------------------------------------
1337 LIVE AND MUST-INITIALIZED REGISTERS.
1339 This problem first computes the IN and OUT bitvectors for the
1340 must-initialized registers problems, which is a forward problem.
1341 It gives the set of registers for which we MUST have an available
1342 definition on any path from the entry block to the entry/exit of
1343 a basic block. Sets generate a definition, while clobbers kill
1346 In and out bitvectors are built for each basic block and are indexed by
1347 regnum (see df.h for details). In and out bitvectors in struct
1348 df_live_bb_info actually refers to the must-initialized problem;
1350 Then, the in and out sets for the LIVE problem itself are computed.
1351 These are the logical AND of the IN and OUT sets from the LR problem
1352 and the must-initialized problem.
1353 ----------------------------------------------------------------------------*/
1355 /* Private data used to verify the solution for this problem. */
1356 struct df_live_problem_data
1362 /* Scratch var used by transfer functions. This is used to implement
1363 an optimization to reduce the amount of space used to compute the
1364 combined lr and live analysis. */
1365 static bitmap df_live_scratch
;
1367 /* Set basic block info. */
1370 df_live_set_bb_info (unsigned int index
,
1371 struct df_live_bb_info
*bb_info
)
1373 gcc_assert (df_live
);
1374 gcc_assert (index
< df_live
->block_info_size
);
1375 df_live
->block_info
[index
] = bb_info
;
1379 /* Free basic block info. */
1382 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1385 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1388 BITMAP_FREE (bb_info
->gen
);
1389 BITMAP_FREE (bb_info
->kill
);
1390 BITMAP_FREE (bb_info
->in
);
1391 BITMAP_FREE (bb_info
->out
);
1392 pool_free (df_live
->block_pool
, bb_info
);
1397 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1398 not touched unless the block is new. */
1401 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1403 unsigned int bb_index
;
1406 if (!df_live
->block_pool
)
1407 df_live
->block_pool
= create_alloc_pool ("df_live_block pool",
1408 sizeof (struct df_live_bb_info
), 100);
1409 if (!df_live_scratch
)
1410 df_live_scratch
= BITMAP_ALLOC (NULL
);
1412 df_grow_bb_info (df_live
);
1414 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1416 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1419 bitmap_clear (bb_info
->kill
);
1420 bitmap_clear (bb_info
->gen
);
1424 bb_info
= (struct df_live_bb_info
*) pool_alloc (df_live
->block_pool
);
1425 df_live_set_bb_info (bb_index
, bb_info
);
1426 bb_info
->kill
= BITMAP_ALLOC (NULL
);
1427 bb_info
->gen
= BITMAP_ALLOC (NULL
);
1428 bb_info
->in
= BITMAP_ALLOC (NULL
);
1429 bb_info
->out
= BITMAP_ALLOC (NULL
);
1432 df_live
->optional_p
= (optimize
<= 1);
1436 /* Reset the global solution for recalculation. */
1439 df_live_reset (bitmap all_blocks
)
1441 unsigned int bb_index
;
1444 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1446 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1447 gcc_assert (bb_info
);
1448 bitmap_clear (bb_info
->in
);
1449 bitmap_clear (bb_info
->out
);
1454 /* Compute local uninitialized register info for basic block BB. */
1457 df_live_bb_local_compute (unsigned int bb_index
)
1459 basic_block bb
= BASIC_BLOCK (bb_index
);
1460 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1465 FOR_BB_INSNS (bb
, insn
)
1467 unsigned int uid
= INSN_UID (insn
);
1468 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
1470 /* Inserting labels does not always trigger the incremental
1474 gcc_assert (!INSN_P (insn
));
1475 insn_info
= df_insn_create_insn_record (insn
);
1478 DF_INSN_INFO_LUID (insn_info
) = luid
;
1483 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
1485 df_ref def
= *def_rec
;
1486 unsigned int regno
= DF_REF_REGNO (def
);
1488 if (DF_REF_FLAGS_IS_SET (def
,
1489 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
1490 /* All partial or conditional def
1491 seen are included in the gen set. */
1492 bitmap_set_bit (bb_info
->gen
, regno
);
1493 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
1494 /* Only must clobbers for the entire reg destroy the
1496 bitmap_set_bit (bb_info
->kill
, regno
);
1497 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1498 bitmap_set_bit (bb_info
->gen
, regno
);
1502 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1504 df_ref def
= *def_rec
;
1505 bitmap_set_bit (bb_info
->gen
, DF_REF_REGNO (def
));
1510 /* Compute local uninitialized register info. */
1513 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1515 unsigned int bb_index
;
1518 df_grow_insn_info ();
1520 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
1523 df_live_bb_local_compute (bb_index
);
1526 bitmap_clear (df_live
->out_of_date_transfer_functions
);
1530 /* Initialize the solution vectors. */
1533 df_live_init (bitmap all_blocks
)
1535 unsigned int bb_index
;
1538 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1540 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1541 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1543 /* No register may reach a location where it is not used. Thus
1544 we trim the rr result to the places where it is used. */
1545 bitmap_and (bb_info
->out
, bb_info
->gen
, bb_lr_info
->out
);
1546 bitmap_clear (bb_info
->in
);
1550 /* Forward confluence function that ignores fake edges. */
1553 df_live_confluence_n (edge e
)
1555 bitmap op1
= df_live_get_bb_info (e
->dest
->index
)->in
;
1556 bitmap op2
= df_live_get_bb_info (e
->src
->index
)->out
;
1558 if (e
->flags
& EDGE_FAKE
)
1561 bitmap_ior_into (op1
, op2
);
1565 /* Transfer function for the forwards must-initialized problem. */
1568 df_live_transfer_function (int bb_index
)
1570 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
1571 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1572 bitmap in
= bb_info
->in
;
1573 bitmap out
= bb_info
->out
;
1574 bitmap gen
= bb_info
->gen
;
1575 bitmap kill
= bb_info
->kill
;
1577 /* We need to use a scratch set here so that the value returned from
1578 this function invocation properly reflects if the sets changed in
1579 a significant way; i.e. not just because the lr set was anded
1581 bitmap_and (df_live_scratch
, gen
, bb_lr_info
->out
);
1582 /* No register may reach a location where it is not used. Thus
1583 we trim the rr result to the places where it is used. */
1584 bitmap_and_into (in
, bb_lr_info
->in
);
1586 return bitmap_ior_and_compl (out
, df_live_scratch
, in
, kill
);
1590 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1593 df_live_finalize (bitmap all_blocks
)
1596 if (df_live
->solutions_dirty
)
1599 unsigned int bb_index
;
1601 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1603 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
1604 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
1606 /* No register may reach a location where it is not used. Thus
1607 we trim the rr result to the places where it is used. */
1608 bitmap_and_into (bb_live_info
->in
, bb_lr_info
->in
);
1609 bitmap_and_into (bb_live_info
->out
, bb_lr_info
->out
);
1612 df_live
->solutions_dirty
= false;
1617 /* Free all storage associated with the problem. */
1622 if (df_live
->block_info
)
1626 for (i
= 0; i
< df_live
->block_info_size
; i
++)
1628 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (i
);
1631 BITMAP_FREE (bb_info
->gen
);
1632 BITMAP_FREE (bb_info
->kill
);
1633 BITMAP_FREE (bb_info
->in
);
1634 BITMAP_FREE (bb_info
->out
);
1638 free_alloc_pool (df_live
->block_pool
);
1639 df_live
->block_info_size
= 0;
1640 free (df_live
->block_info
);
1642 if (df_live_scratch
)
1643 BITMAP_FREE (df_live_scratch
);
1645 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
1650 /* Debugging info at top of bb. */
1653 df_live_top_dump (basic_block bb
, FILE *file
)
1655 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1656 struct df_live_problem_data
*problem_data
;
1658 if (!bb_info
|| !bb_info
->in
)
1661 fprintf (file
, ";; live in \t");
1662 df_print_regset (file
, bb_info
->in
);
1663 if (df_live
->problem_data
)
1665 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1666 fprintf (file
, ";; old in \t");
1667 df_print_regset (file
, problem_data
->in
[bb
->index
]);
1669 fprintf (file
, ";; live gen \t");
1670 df_print_regset (file
, bb_info
->gen
);
1671 fprintf (file
, ";; live kill\t");
1672 df_print_regset (file
, bb_info
->kill
);
1676 /* Debugging info at bottom of bb. */
1679 df_live_bottom_dump (basic_block bb
, FILE *file
)
1681 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1682 struct df_live_problem_data
*problem_data
;
1684 if (!bb_info
|| !bb_info
->out
)
1687 fprintf (file
, ";; live out \t");
1688 df_print_regset (file
, bb_info
->out
);
1689 if (df_live
->problem_data
)
1691 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1692 fprintf (file
, ";; old out \t");
1693 df_print_regset (file
, problem_data
->out
[bb
->index
]);
1698 /* Build the datastructure to verify that the solution to the dataflow
1699 equations is not dirty. */
1702 df_live_verify_solution_start (void)
1705 struct df_live_problem_data
*problem_data
;
1706 if (df_live
->solutions_dirty
)
1708 df_live
->problem_data
= NULL
;
1712 /* Set it true so that the solution is recomputed. */
1713 df_live
->solutions_dirty
= true;
1715 problem_data
= XNEW (struct df_live_problem_data
);
1716 df_live
->problem_data
= problem_data
;
1717 problem_data
->in
= XNEWVEC (bitmap
, last_basic_block
);
1718 problem_data
->out
= XNEWVEC (bitmap
, last_basic_block
);
1722 problem_data
->in
[bb
->index
] = BITMAP_ALLOC (NULL
);
1723 problem_data
->out
[bb
->index
] = BITMAP_ALLOC (NULL
);
1724 bitmap_copy (problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
1725 bitmap_copy (problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
1730 /* Compare the saved datastructure and the new solution to the dataflow
1734 df_live_verify_solution_end (void)
1736 struct df_live_problem_data
*problem_data
;
1739 if (df_live
->problem_data
== NULL
)
1742 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
1746 if ((!bitmap_equal_p (problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
1747 || (!bitmap_equal_p (problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
1749 /*df_dump (stderr);*/
1754 /* Cannot delete them immediately because you may want to dump them
1755 if the comparison fails. */
1758 BITMAP_FREE (problem_data
->in
[bb
->index
]);
1759 BITMAP_FREE (problem_data
->out
[bb
->index
]);
1762 free (problem_data
->in
);
1763 free (problem_data
->out
);
1764 free (problem_data
);
1765 df_live
->problem_data
= NULL
;
1769 /* All of the information associated with every instance of the problem. */
1771 static struct df_problem problem_LIVE
=
1773 DF_LIVE
, /* Problem id. */
1774 DF_FORWARD
, /* Direction. */
1775 df_live_alloc
, /* Allocate the problem specific data. */
1776 df_live_reset
, /* Reset global information. */
1777 df_live_free_bb_info
, /* Free basic block info. */
1778 df_live_local_compute
, /* Local compute function. */
1779 df_live_init
, /* Init the solution specific data. */
1780 df_worklist_dataflow
, /* Worklist solver. */
1781 NULL
, /* Confluence operator 0. */
1782 df_live_confluence_n
, /* Confluence operator n. */
1783 df_live_transfer_function
, /* Transfer function. */
1784 df_live_finalize
, /* Finalize function. */
1785 df_live_free
, /* Free all of the problem information. */
1786 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
1787 NULL
, /* Debugging. */
1788 df_live_top_dump
, /* Debugging start block. */
1789 df_live_bottom_dump
, /* Debugging end block. */
1790 df_live_verify_solution_start
,/* Incremental solution verify start. */
1791 df_live_verify_solution_end
, /* Incremental solution verify end. */
1792 &problem_LR
, /* Dependent problem. */
1793 TV_DF_LIVE
, /* Timing variable. */
1794 false /* Reset blocks on dropping out of blocks_to_analyze. */
1798 /* Create a new DATAFLOW instance and add it to an existing instance
1799 of DF. The returned structure is what is used to get at the
1803 df_live_add_problem (void)
1805 df_add_problem (&problem_LIVE
);
1806 /* These will be initialized when df_scan_blocks processes each
1808 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1812 /* Set all of the blocks as dirty. This needs to be done if this
1813 problem is added after all of the insns have been scanned. */
1816 df_live_set_all_dirty (void)
1820 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
1825 /* Verify that all of the lr related info is consistent and
1829 df_live_verify_transfer_functions (void)
1839 saved_gen
= BITMAP_ALLOC (NULL
);
1840 saved_kill
= BITMAP_ALLOC (NULL
);
1841 all_blocks
= BITMAP_ALLOC (NULL
);
1843 df_grow_insn_info ();
1847 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
1848 bitmap_set_bit (all_blocks
, bb
->index
);
1852 /* Make a copy of the transfer functions and then compute
1853 new ones to see if the transfer functions have
1855 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1858 bitmap_copy (saved_gen
, bb_info
->gen
);
1859 bitmap_copy (saved_kill
, bb_info
->kill
);
1860 bitmap_clear (bb_info
->gen
);
1861 bitmap_clear (bb_info
->kill
);
1863 df_live_bb_local_compute (bb
->index
);
1864 gcc_assert (bitmap_equal_p (saved_gen
, bb_info
->gen
));
1865 gcc_assert (bitmap_equal_p (saved_kill
, bb_info
->kill
));
1870 /* If we do not have basic block info, the block must be in
1871 the list of dirty blocks or else some one has added a
1872 block behind our backs. */
1873 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
1876 /* Make sure no one created a block without following
1878 gcc_assert (df_scan_get_bb_info (bb
->index
));
1881 /* Make sure there are no dirty bits in blocks that have been deleted. */
1882 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
1884 BITMAP_FREE (saved_gen
);
1885 BITMAP_FREE (saved_kill
);
1886 BITMAP_FREE (all_blocks
);
1889 /*----------------------------------------------------------------------------
1890 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1892 Link either the defs to the uses and / or the uses to the defs.
1894 These problems are set up like the other dataflow problems so that
1895 they nicely fit into the framework. They are much simpler and only
1896 involve a single traversal of instructions and an examination of
1897 the reaching defs information (the dependent problem).
1898 ----------------------------------------------------------------------------*/
1900 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1902 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1905 df_chain_create (df_ref src
, df_ref dst
)
1907 struct df_link
*head
= DF_REF_CHAIN (src
);
1908 struct df_link
*link
= (struct df_link
*) pool_alloc (df_chain
->block_pool
);
1910 DF_REF_CHAIN (src
) = link
;
1917 /* Delete any du or ud chains that start at REF and point to
1920 df_chain_unlink_1 (df_ref ref
, df_ref target
)
1922 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1923 struct df_link
*prev
= NULL
;
1927 if (chain
->ref
== target
)
1930 prev
->next
= chain
->next
;
1932 DF_REF_CHAIN (ref
) = chain
->next
;
1933 pool_free (df_chain
->block_pool
, chain
);
1937 chain
= chain
->next
;
1942 /* Delete a du or ud chain that leave or point to REF. */
1945 df_chain_unlink (df_ref ref
)
1947 struct df_link
*chain
= DF_REF_CHAIN (ref
);
1950 struct df_link
*next
= chain
->next
;
1951 /* Delete the other side if it exists. */
1952 df_chain_unlink_1 (chain
->ref
, ref
);
1953 pool_free (df_chain
->block_pool
, chain
);
1956 DF_REF_CHAIN (ref
) = NULL
;
1960 /* Copy the du or ud chain starting at FROM_REF and attach it to
1964 df_chain_copy (df_ref to_ref
,
1965 struct df_link
*from_ref
)
1969 df_chain_create (to_ref
, from_ref
->ref
);
1970 from_ref
= from_ref
->next
;
1975 /* Remove this problem from the stack of dataflow problems. */
1978 df_chain_remove_problem (void)
1981 unsigned int bb_index
;
1983 /* Wholesale destruction of the old chains. */
1984 if (df_chain
->block_pool
)
1985 free_alloc_pool (df_chain
->block_pool
);
1987 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1992 basic_block bb
= BASIC_BLOCK (bb_index
);
1994 if (df_chain_problem_p (DF_DU_CHAIN
))
1995 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
1996 DF_REF_CHAIN (*def_rec
) = NULL
;
1997 if (df_chain_problem_p (DF_UD_CHAIN
))
1998 for (use_rec
= df_get_artificial_uses (bb
->index
); *use_rec
; use_rec
++)
1999 DF_REF_CHAIN (*use_rec
) = NULL
;
2001 FOR_BB_INSNS (bb
, insn
)
2003 unsigned int uid
= INSN_UID (insn
);
2007 if (df_chain_problem_p (DF_DU_CHAIN
))
2008 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2009 DF_REF_CHAIN (*def_rec
) = NULL
;
2010 if (df_chain_problem_p (DF_UD_CHAIN
))
2012 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2013 DF_REF_CHAIN (*use_rec
) = NULL
;
2014 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
2015 DF_REF_CHAIN (*use_rec
) = NULL
;
2021 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
2022 df_chain
->block_pool
= NULL
;
2026 /* Remove the chain problem completely. */
2029 df_chain_fully_remove_problem (void)
2031 df_chain_remove_problem ();
2032 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2037 /* Create def-use or use-def chains. */
2040 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2042 df_chain_remove_problem ();
2043 df_chain
->block_pool
= create_alloc_pool ("df_chain_block pool",
2044 sizeof (struct df_link
), 50);
2045 df_chain
->optional_p
= true;
2049 /* Reset all of the chains when the set of basic blocks changes. */
2052 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
2054 df_chain_remove_problem ();
2058 /* Create the chains for a list of USEs. */
2061 df_chain_create_bb_process_use (bitmap local_rd
,
2066 unsigned int def_index
;
2070 df_ref use
= *use_rec
;
2071 unsigned int uregno
= DF_REF_REGNO (use
);
2072 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2073 || (uregno
>= FIRST_PSEUDO_REGISTER
))
2075 /* Do not want to go through this for an uninitialized var. */
2076 int count
= DF_DEFS_COUNT (uregno
);
2079 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
2081 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
2082 unsigned int last_index
= first_index
+ count
- 1;
2084 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
2087 if (def_index
> last_index
)
2090 def
= DF_DEFS_GET (def_index
);
2091 if (df_chain_problem_p (DF_DU_CHAIN
))
2092 df_chain_create (def
, use
);
2093 if (df_chain_problem_p (DF_UD_CHAIN
))
2094 df_chain_create (use
, def
);
2105 /* Create chains from reaching defs bitmaps for basic block BB. */
2108 df_chain_create_bb (unsigned int bb_index
)
2110 basic_block bb
= BASIC_BLOCK (bb_index
);
2111 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
2113 bitmap cpy
= BITMAP_ALLOC (NULL
);
2115 bitmap_copy (cpy
, bb_info
->in
);
2116 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
2118 /* Since we are going forwards, process the artificial uses first
2119 then the artificial defs second. */
2122 /* Create the chains for the artificial uses from the EH_USES at the
2123 beginning of the block. */
2125 /* Artificials are only hard regs. */
2126 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2127 df_chain_create_bb_process_use (cpy
,
2128 df_get_artificial_uses (bb
->index
),
2132 df_rd_simulate_artificial_defs_at_top (bb
, cpy
);
2134 /* Process the regular instructions next. */
2135 FOR_BB_INSNS (bb
, insn
)
2138 unsigned int uid
= INSN_UID (insn
);
2140 /* First scan the uses and link them up with the defs that remain
2141 in the cpy vector. */
2142 df_chain_create_bb_process_use (cpy
, DF_INSN_UID_USES (uid
), 0);
2143 if (df
->changeable_flags
& DF_EQ_NOTES
)
2144 df_chain_create_bb_process_use (cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
2146 /* Since we are going forwards, process the defs second. */
2147 df_rd_simulate_one_insn (bb
, insn
, cpy
);
2150 /* Create the chains for the artificial uses of the hard registers
2151 at the end of the block. */
2152 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
2153 df_chain_create_bb_process_use (cpy
,
2154 df_get_artificial_uses (bb
->index
),
2160 /* Create def-use chains from reaching use bitmaps for basic blocks
2164 df_chain_finalize (bitmap all_blocks
)
2166 unsigned int bb_index
;
2169 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2171 df_chain_create_bb (bb_index
);
2176 /* Free all storage associated with the problem. */
2179 df_chain_free (void)
2181 free_alloc_pool (df_chain
->block_pool
);
2182 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
2187 /* Debugging info. */
2190 df_chain_top_dump (basic_block bb
, FILE *file
)
2192 if (df_chain_problem_p (DF_DU_CHAIN
))
2195 df_ref
*def_rec
= df_get_artificial_defs (bb
->index
);
2199 fprintf (file
, ";; DU chains for artificial defs\n");
2202 df_ref def
= *def_rec
;
2203 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2204 df_chain_dump (DF_REF_CHAIN (def
), file
);
2205 fprintf (file
, "\n");
2210 FOR_BB_INSNS (bb
, insn
)
2214 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2215 def_rec
= DF_INSN_INFO_DEFS (insn_info
);
2218 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
2219 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2223 df_ref def
= *def_rec
;
2224 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
2225 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
2226 fprintf (file
, "read/write ");
2227 df_chain_dump (DF_REF_CHAIN (def
), file
);
2228 fprintf (file
, "\n");
2239 df_chain_bottom_dump (basic_block bb
, FILE *file
)
2241 if (df_chain_problem_p (DF_UD_CHAIN
))
2244 df_ref
*use_rec
= df_get_artificial_uses (bb
->index
);
2248 fprintf (file
, ";; UD chains for artificial uses\n");
2251 df_ref use
= *use_rec
;
2252 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2253 df_chain_dump (DF_REF_CHAIN (use
), file
);
2254 fprintf (file
, "\n");
2259 FOR_BB_INSNS (bb
, insn
)
2263 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2264 df_ref
*eq_use_rec
= DF_INSN_INFO_EQ_USES (insn_info
);
2265 use_rec
= DF_INSN_INFO_USES (insn_info
);
2266 if (*use_rec
|| *eq_use_rec
)
2268 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
2269 DF_INSN_INFO_LUID (insn_info
), INSN_UID (insn
));
2273 df_ref use
= *use_rec
;
2274 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
2275 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
2276 fprintf (file
, "read/write ");
2277 df_chain_dump (DF_REF_CHAIN (use
), file
);
2278 fprintf (file
, "\n");
2283 df_ref use
= *eq_use_rec
;
2284 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
2285 df_chain_dump (DF_REF_CHAIN (use
), file
);
2286 fprintf (file
, "\n");
2296 static struct df_problem problem_CHAIN
=
2298 DF_CHAIN
, /* Problem id. */
2299 DF_NONE
, /* Direction. */
2300 df_chain_alloc
, /* Allocate the problem specific data. */
2301 df_chain_reset
, /* Reset global information. */
2302 NULL
, /* Free basic block info. */
2303 NULL
, /* Local compute function. */
2304 NULL
, /* Init the solution specific data. */
2305 NULL
, /* Iterative solver. */
2306 NULL
, /* Confluence operator 0. */
2307 NULL
, /* Confluence operator n. */
2308 NULL
, /* Transfer function. */
2309 df_chain_finalize
, /* Finalize function. */
2310 df_chain_free
, /* Free all of the problem information. */
2311 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
2312 NULL
, /* Debugging. */
2313 df_chain_top_dump
, /* Debugging start block. */
2314 df_chain_bottom_dump
, /* Debugging end block. */
2315 NULL
, /* Incremental solution verify start. */
2316 NULL
, /* Incremental solution verify end. */
2317 &problem_RD
, /* Dependent problem. */
2318 TV_DF_CHAIN
, /* Timing variable. */
2319 false /* Reset blocks on dropping out of blocks_to_analyze. */
2323 /* Create a new DATAFLOW instance and add it to an existing instance
2324 of DF. The returned structure is what is used to get at the
2328 df_chain_add_problem (unsigned int chain_flags
)
2330 df_add_problem (&problem_CHAIN
);
2331 df_chain
->local_flags
= chain_flags
;
2332 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2335 #undef df_chain_problem_p
2338 /*----------------------------------------------------------------------------
2339 BYTE LEVEL LIVE REGISTERS
2341 Find the locations in the function where any use of a pseudo can
2342 reach in the backwards direction. In and out bitvectors are built
2343 for each basic block. There are two mapping functions,
2344 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2345 used to map regnos into bit vector positions.
2347 This problem differs from the regular df_lr function in the way
2348 that subregs, *_extracts and strict_low_parts are handled. In lr
2349 these are consider partial kills, here, the exact set of bytes is
2350 modeled. Note that any reg that has none of these operations is
2351 only modeled with a single bit since all operations access the
2354 This problem is more brittle that the regular lr. It currently can
2355 be used in dce incrementally, but cannot be used in an environment
2356 where insns are created or modified. The problem is that the
2357 mapping of regnos to bitmap positions is relatively compact, in
2358 that if a pseudo does not do any of the byte wise operations, only
2359 one slot is allocated, rather than a slot for each byte. If insn
2360 are created, where a subreg is used for a reg that had no subregs,
2361 the mapping would be wrong. Likewise, there are no checks to see
2362 that new pseudos have been added. These issues could be addressed
2363 by adding a problem specific flag to not use the compact mapping,
2364 if there was a need to do so.
2366 ----------------------------------------------------------------------------*/
2368 /* Private data used to verify the solution for this problem. */
2369 struct df_byte_lr_problem_data
2371 /* Expanded versions of bitvectors used in lr. */
2372 bitmap invalidated_by_call
;
2373 bitmap hardware_regs_used
;
2375 /* Indexed by regno, this is true if there are subregs, extracts or
2376 strict_low_parts for this regno. */
2377 bitmap needs_expansion
;
2379 /* The start position and len for each regno in the various bit
2381 unsigned int* regno_start
;
2382 unsigned int* regno_len
;
2383 /* An obstack for the bitmaps we need for this problem. */
2384 bitmap_obstack byte_lr_bitmaps
;
2388 /* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2391 df_byte_lr_get_regno_start (unsigned int regno
)
2393 struct df_byte_lr_problem_data
*problem_data
2394 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;;
2395 return problem_data
->regno_start
[regno
];
2399 /* Get the len for REGNO in the df_byte_lr bitmaps. */
2402 df_byte_lr_get_regno_len (unsigned int regno
)
2404 struct df_byte_lr_problem_data
*problem_data
2405 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;;
2406 return problem_data
->regno_len
[regno
];
2410 /* Set basic block info. */
2413 df_byte_lr_set_bb_info (unsigned int index
,
2414 struct df_byte_lr_bb_info
*bb_info
)
2416 gcc_assert (df_byte_lr
);
2417 gcc_assert (index
< df_byte_lr
->block_info_size
);
2418 df_byte_lr
->block_info
[index
] = bb_info
;
2422 /* Free basic block info. */
2425 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2428 struct df_byte_lr_bb_info
*bb_info
= (struct df_byte_lr_bb_info
*) vbb_info
;
2431 BITMAP_FREE (bb_info
->use
);
2432 BITMAP_FREE (bb_info
->def
);
2433 BITMAP_FREE (bb_info
->in
);
2434 BITMAP_FREE (bb_info
->out
);
2435 pool_free (df_byte_lr
->block_pool
, bb_info
);
2440 /* Check all of the refs in REF_REC to see if any of them are
2441 extracts, subregs or strict_low_parts. */
2444 df_byte_lr_check_regs (df_ref
*ref_rec
)
2446 struct df_byte_lr_problem_data
*problem_data
2447 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2449 for (; *ref_rec
; ref_rec
++)
2451 df_ref ref
= *ref_rec
;
2452 if (DF_REF_FLAGS_IS_SET (ref
, DF_REF_SIGN_EXTRACT
2453 | DF_REF_ZERO_EXTRACT
2454 | DF_REF_STRICT_LOW_PART
)
2455 || GET_CODE (DF_REF_REG (ref
)) == SUBREG
)
2456 bitmap_set_bit (problem_data
->needs_expansion
, DF_REF_REGNO (ref
));
2461 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2462 regno_start and regno_len. */
2465 df_byte_lr_expand_bitmap (bitmap dest
, bitmap src
)
2467 struct df_byte_lr_problem_data
*problem_data
2468 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2472 bitmap_clear (dest
);
2473 EXECUTE_IF_SET_IN_BITMAP (src
, 0, i
, bi
)
2475 bitmap_set_range (dest
, problem_data
->regno_start
[i
],
2476 problem_data
->regno_len
[i
]);
2481 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2482 not touched unless the block is new. */
2485 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2487 unsigned int bb_index
;
2491 unsigned int index
= 0;
2492 unsigned int max_reg
= max_reg_num();
2493 struct df_byte_lr_problem_data
*problem_data
2494 = XNEW (struct df_byte_lr_problem_data
);
2496 df_byte_lr
->problem_data
= problem_data
;
2498 if (!df_byte_lr
->block_pool
)
2499 df_byte_lr
->block_pool
= create_alloc_pool ("df_byte_lr_block pool",
2500 sizeof (struct df_byte_lr_bb_info
), 50);
2502 df_grow_bb_info (df_byte_lr
);
2504 /* Create the mapping from regnos to slots. This does not change
2505 unless the problem is destroyed and recreated. In particular, if
2506 we end up deleting the only insn that used a subreg, we do not
2507 want to redo the mapping because this would invalidate everything
2510 bitmap_obstack_initialize (&problem_data
->byte_lr_bitmaps
);
2511 problem_data
->regno_start
= XNEWVEC (unsigned int, max_reg
);
2512 problem_data
->regno_len
= XNEWVEC (unsigned int, max_reg
);
2513 problem_data
->hardware_regs_used
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2514 problem_data
->invalidated_by_call
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2515 problem_data
->needs_expansion
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2517 /* Discover which regno's use subregs, extracts or
2518 strict_low_parts. */
2522 FOR_BB_INSNS (bb
, insn
)
2526 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2527 df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info
));
2528 df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info
));
2531 bitmap_set_bit (df_byte_lr
->out_of_date_transfer_functions
, bb
->index
);
2534 bitmap_set_bit (df_byte_lr
->out_of_date_transfer_functions
, ENTRY_BLOCK
);
2535 bitmap_set_bit (df_byte_lr
->out_of_date_transfer_functions
, EXIT_BLOCK
);
2537 /* Allocate the slots for each regno. */
2538 for (regno
= 0; regno
< max_reg
; regno
++)
2541 problem_data
->regno_start
[regno
] = index
;
2542 if (bitmap_bit_p (problem_data
->needs_expansion
, regno
))
2543 len
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
2547 problem_data
->regno_len
[regno
] = len
;
2551 df_byte_lr_expand_bitmap (problem_data
->hardware_regs_used
,
2552 df
->hardware_regs_used
);
2553 df_byte_lr_expand_bitmap (problem_data
->invalidated_by_call
,
2554 regs_invalidated_by_call_regset
);
2556 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2558 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2561 bitmap_clear (bb_info
->def
);
2562 bitmap_clear (bb_info
->use
);
2566 bb_info
= (struct df_byte_lr_bb_info
*) pool_alloc (df_byte_lr
->block_pool
);
2567 df_byte_lr_set_bb_info (bb_index
, bb_info
);
2568 bb_info
->use
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2569 bb_info
->def
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2570 bb_info
->in
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2571 bb_info
->out
= BITMAP_ALLOC (&problem_data
->byte_lr_bitmaps
);
2575 df_byte_lr
->optional_p
= true;
2579 /* Reset the global solution for recalculation. */
2582 df_byte_lr_reset (bitmap all_blocks
)
2584 unsigned int bb_index
;
2587 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2589 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2590 gcc_assert (bb_info
);
2591 bitmap_clear (bb_info
->in
);
2592 bitmap_clear (bb_info
->out
);
2597 /* Compute local live register info for basic block BB. */
2600 df_byte_lr_bb_local_compute (unsigned int bb_index
)
2602 struct df_byte_lr_problem_data
*problem_data
2603 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2604 basic_block bb
= BASIC_BLOCK (bb_index
);
2605 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2610 /* Process the registers set in an exception handler. */
2611 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2613 df_ref def
= *def_rec
;
2614 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
2616 unsigned int dregno
= DF_REF_REGNO (def
);
2617 unsigned int start
= problem_data
->regno_start
[dregno
];
2618 unsigned int len
= problem_data
->regno_len
[dregno
];
2619 bitmap_set_range (bb_info
->def
, start
, len
);
2620 bitmap_clear_range (bb_info
->use
, start
, len
);
2624 /* Process the hardware registers that are always live. */
2625 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2627 df_ref use
= *use_rec
;
2628 /* Add use to set of uses in this BB. */
2629 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
2631 unsigned int uregno
= DF_REF_REGNO (use
);
2632 unsigned int start
= problem_data
->regno_start
[uregno
];
2633 unsigned int len
= problem_data
->regno_len
[uregno
];
2634 bitmap_set_range (bb_info
->use
, start
, len
);
2638 FOR_BB_INSNS_REVERSE (bb
, insn
)
2640 unsigned int uid
= INSN_UID (insn
);
2645 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2647 df_ref def
= *def_rec
;
2648 /* If the def is to only part of the reg, it does
2649 not kill the other defs that reach here. */
2650 if (!(DF_REF_FLAGS (def
) & (DF_REF_CONDITIONAL
)))
2652 unsigned int dregno
= DF_REF_REGNO (def
);
2653 unsigned int start
= problem_data
->regno_start
[dregno
];
2654 unsigned int len
= problem_data
->regno_len
[dregno
];
2657 if (!df_compute_accessed_bytes (def
, DF_MM_MUST
, &sb
, &lb
))
2664 bitmap_set_range (bb_info
->def
, start
, len
);
2665 bitmap_clear_range (bb_info
->use
, start
, len
);
2670 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2672 df_ref use
= *use_rec
;
2673 unsigned int uregno
= DF_REF_REGNO (use
);
2674 unsigned int start
= problem_data
->regno_start
[uregno
];
2675 unsigned int len
= problem_data
->regno_len
[uregno
];
2678 if (!df_compute_accessed_bytes (use
, DF_MM_MAY
, &sb
, &lb
))
2683 /* Add use to set of uses in this BB. */
2685 bitmap_set_range (bb_info
->use
, start
, len
);
2689 /* Process the registers set in an exception handler or the hard
2690 frame pointer if this block is the target of a non local
2692 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2694 df_ref def
= *def_rec
;
2695 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2697 unsigned int dregno
= DF_REF_REGNO (def
);
2698 unsigned int start
= problem_data
->regno_start
[dregno
];
2699 unsigned int len
= problem_data
->regno_len
[dregno
];
2700 bitmap_set_range (bb_info
->def
, start
, len
);
2701 bitmap_clear_range (bb_info
->use
, start
, len
);
2706 /* Process the uses that are live into an exception handler. */
2707 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
2709 df_ref use
= *use_rec
;
2710 /* Add use to set of uses in this BB. */
2711 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
2713 unsigned int uregno
= DF_REF_REGNO (use
);
2714 unsigned int start
= problem_data
->regno_start
[uregno
];
2715 unsigned int len
= problem_data
->regno_len
[uregno
];
2716 bitmap_set_range (bb_info
->use
, start
, len
);
2723 /* Compute local live register info for each basic block within BLOCKS. */
2726 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2728 unsigned int bb_index
;
2731 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2733 if (bb_index
== EXIT_BLOCK
)
2735 /* The exit block is special for this problem and its bits are
2736 computed from thin air. */
2737 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (EXIT_BLOCK
);
2738 df_byte_lr_expand_bitmap (bb_info
->use
, df
->exit_block_uses
);
2741 df_byte_lr_bb_local_compute (bb_index
);
2744 bitmap_clear (df_byte_lr
->out_of_date_transfer_functions
);
2748 /* Initialize the solution vectors. */
2751 df_byte_lr_init (bitmap all_blocks
)
2753 unsigned int bb_index
;
2756 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2758 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2759 bitmap_copy (bb_info
->in
, bb_info
->use
);
2760 bitmap_clear (bb_info
->out
);
2765 /* Confluence function that processes infinite loops. This might be a
2766 noreturn function that throws. And even if it isn't, getting the
2767 unwind info right helps debugging. */
2769 df_byte_lr_confluence_0 (basic_block bb
)
2771 struct df_byte_lr_problem_data
*problem_data
2772 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2773 bitmap op1
= df_byte_lr_get_bb_info (bb
->index
)->out
;
2774 if (bb
!= EXIT_BLOCK_PTR
)
2775 bitmap_copy (op1
, problem_data
->hardware_regs_used
);
2779 /* Confluence function that ignores fake edges. */
2782 df_byte_lr_confluence_n (edge e
)
2784 struct df_byte_lr_problem_data
*problem_data
2785 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2786 bitmap op1
= df_byte_lr_get_bb_info (e
->src
->index
)->out
;
2787 bitmap op2
= df_byte_lr_get_bb_info (e
->dest
->index
)->in
;
2789 /* Call-clobbered registers die across exception and call edges. */
2790 /* ??? Abnormal call edges ignored for the moment, as this gets
2791 confused by sibling call edges, which crashes reg-stack. */
2792 if (e
->flags
& EDGE_EH
)
2793 bitmap_ior_and_compl_into (op1
, op2
, problem_data
->invalidated_by_call
);
2795 bitmap_ior_into (op1
, op2
);
2797 bitmap_ior_into (op1
, problem_data
->hardware_regs_used
);
2801 /* Transfer function. */
2804 df_byte_lr_transfer_function (int bb_index
)
2806 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb_index
);
2807 bitmap in
= bb_info
->in
;
2808 bitmap out
= bb_info
->out
;
2809 bitmap use
= bb_info
->use
;
2810 bitmap def
= bb_info
->def
;
2812 return bitmap_ior_and_compl (in
, use
, out
, def
);
2816 /* Free all storage associated with the problem. */
2819 df_byte_lr_free (void)
2821 struct df_byte_lr_problem_data
*problem_data
2822 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2825 if (df_byte_lr
->block_info
)
2827 free_alloc_pool (df_byte_lr
->block_pool
);
2828 df_byte_lr
->block_info_size
= 0;
2829 free (df_byte_lr
->block_info
);
2832 BITMAP_FREE (df_byte_lr
->out_of_date_transfer_functions
);
2833 bitmap_obstack_release (&problem_data
->byte_lr_bitmaps
);
2834 free (problem_data
->regno_start
);
2835 free (problem_data
->regno_len
);
2836 free (problem_data
);
2841 /* Debugging info at top of bb. */
2844 df_byte_lr_top_dump (basic_block bb
, FILE *file
)
2846 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb
->index
);
2847 if (!bb_info
|| !bb_info
->in
)
2850 fprintf (file
, ";; blr in \t");
2851 df_print_byte_regset (file
, bb_info
->in
);
2852 fprintf (file
, ";; blr use \t");
2853 df_print_byte_regset (file
, bb_info
->use
);
2854 fprintf (file
, ";; blr def \t");
2855 df_print_byte_regset (file
, bb_info
->def
);
2859 /* Debugging info at bottom of bb. */
2862 df_byte_lr_bottom_dump (basic_block bb
, FILE *file
)
2864 struct df_byte_lr_bb_info
*bb_info
= df_byte_lr_get_bb_info (bb
->index
);
2865 if (!bb_info
|| !bb_info
->out
)
2868 fprintf (file
, ";; blr out \t");
2869 df_print_byte_regset (file
, bb_info
->out
);
2873 /* All of the information associated with every instance of the problem. */
2875 static struct df_problem problem_BYTE_LR
=
2877 DF_BYTE_LR
, /* Problem id. */
2878 DF_BACKWARD
, /* Direction. */
2879 df_byte_lr_alloc
, /* Allocate the problem specific data. */
2880 df_byte_lr_reset
, /* Reset global information. */
2881 df_byte_lr_free_bb_info
, /* Free basic block info. */
2882 df_byte_lr_local_compute
, /* Local compute function. */
2883 df_byte_lr_init
, /* Init the solution specific data. */
2884 df_worklist_dataflow
, /* Worklist solver. */
2885 df_byte_lr_confluence_0
, /* Confluence operator 0. */
2886 df_byte_lr_confluence_n
, /* Confluence operator n. */
2887 df_byte_lr_transfer_function
, /* Transfer function. */
2888 NULL
, /* Finalize function. */
2889 df_byte_lr_free
, /* Free all of the problem information. */
2890 df_byte_lr_free
, /* Remove this problem from the stack of dataflow problems. */
2891 NULL
, /* Debugging. */
2892 df_byte_lr_top_dump
, /* Debugging start block. */
2893 df_byte_lr_bottom_dump
, /* Debugging end block. */
2894 NULL
, /* Incremental solution verify start. */
2895 NULL
, /* Incremental solution verify end. */
2896 NULL
, /* Dependent problem. */
2897 TV_DF_BYTE_LR
, /* Timing variable. */
2898 false /* Reset blocks on dropping out of blocks_to_analyze. */
2902 /* Create a new DATAFLOW instance and add it to an existing instance
2903 of DF. The returned structure is what is used to get at the
2907 df_byte_lr_add_problem (void)
2909 df_add_problem (&problem_BYTE_LR
);
2910 /* These will be initialized when df_scan_blocks processes each
2912 df_byte_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2916 /* Simulate the effects of the defs of INSN on LIVE. */
2919 df_byte_lr_simulate_defs (rtx insn
, bitmap live
)
2921 struct df_byte_lr_problem_data
*problem_data
2922 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2924 unsigned int uid
= INSN_UID (insn
);
2926 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2928 df_ref def
= *def_rec
;
2930 /* If the def is to only part of the reg, it does
2931 not kill the other defs that reach here. */
2932 if (!(DF_REF_FLAGS (def
) & DF_REF_CONDITIONAL
))
2934 unsigned int dregno
= DF_REF_REGNO (def
);
2935 unsigned int start
= problem_data
->regno_start
[dregno
];
2936 unsigned int len
= problem_data
->regno_len
[dregno
];
2939 if (!df_compute_accessed_bytes (def
, DF_MM_MUST
, &sb
, &lb
))
2946 bitmap_clear_range (live
, start
, len
);
2952 /* Simulate the effects of the uses of INSN on LIVE. */
2955 df_byte_lr_simulate_uses (rtx insn
, bitmap live
)
2957 struct df_byte_lr_problem_data
*problem_data
2958 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2960 unsigned int uid
= INSN_UID (insn
);
2962 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2964 df_ref use
= *use_rec
;
2965 unsigned int uregno
= DF_REF_REGNO (use
);
2966 unsigned int start
= problem_data
->regno_start
[uregno
];
2967 unsigned int len
= problem_data
->regno_len
[uregno
];
2971 if (!df_compute_accessed_bytes (use
, DF_MM_MAY
, &sb
, &lb
))
2977 /* Add use to set of uses in this BB. */
2979 bitmap_set_range (live
, start
, len
);
2984 /* Apply the artificial uses and defs at the top of BB in a forwards
2988 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb
, bitmap live
)
2990 struct df_byte_lr_problem_data
*problem_data
2991 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
2996 int bb_index
= bb
->index
;
2999 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3001 df_ref use
= *use_rec
;
3002 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3004 unsigned int uregno
= DF_REF_REGNO (use
);
3005 unsigned int start
= problem_data
->regno_start
[uregno
];
3006 unsigned int len
= problem_data
->regno_len
[uregno
];
3007 bitmap_set_range (live
, start
, len
);
3012 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3014 df_ref def
= *def_rec
;
3015 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3017 unsigned int dregno
= DF_REF_REGNO (def
);
3018 unsigned int start
= problem_data
->regno_start
[dregno
];
3019 unsigned int len
= problem_data
->regno_len
[dregno
];
3020 bitmap_clear_range (live
, start
, len
);
3026 /* Apply the artificial uses and defs at the end of BB in a backwards
3030 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb
, bitmap live
)
3032 struct df_byte_lr_problem_data
*problem_data
3033 = (struct df_byte_lr_problem_data
*)df_byte_lr
->problem_data
;
3036 int bb_index
= bb
->index
;
3038 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3040 df_ref def
= *def_rec
;
3041 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3043 unsigned int dregno
= DF_REF_REGNO (def
);
3044 unsigned int start
= problem_data
->regno_start
[dregno
];
3045 unsigned int len
= problem_data
->regno_len
[dregno
];
3046 bitmap_clear_range (live
, start
, len
);
3050 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3052 df_ref use
= *use_rec
;
3053 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3055 unsigned int uregno
= DF_REF_REGNO (use
);
3056 unsigned int start
= problem_data
->regno_start
[uregno
];
3057 unsigned int len
= problem_data
->regno_len
[uregno
];
3058 bitmap_set_range (live
, start
, len
);
3065 /*----------------------------------------------------------------------------
3066 This problem computes REG_DEAD and REG_UNUSED notes.
3067 ----------------------------------------------------------------------------*/
3070 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
3072 df_note
->optional_p
= true;
3075 #ifdef REG_DEAD_DEBUGGING
3077 df_print_note (const char *prefix
, rtx insn
, rtx note
)
3081 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
3082 print_rtl (dump_file
, note
);
3083 fprintf (dump_file
, "\n");
3089 /* After reg-stack, the x86 floating point stack regs are difficult to
3090 analyze because of all of the pushes, pops and rotations. Thus, we
3091 just leave the notes alone. */
3095 df_ignore_stack_reg (int regno
)
3097 return regstack_completed
3098 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
3102 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
3109 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3110 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3113 df_kill_notes (rtx insn
, rtx
*old_dead_notes
, rtx
*old_unused_notes
)
3115 rtx
*pprev
= ®_NOTES (insn
);
3122 switch (REG_NOTE_KIND (link
))
3125 /* After reg-stack, we need to ignore any unused notes
3126 for the stack registers. */
3127 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3129 pprev
= &XEXP (link
, 1);
3134 rtx next
= XEXP (link
, 1);
3135 #ifdef REG_DEAD_DEBUGGING
3136 df_print_note ("deleting: ", insn
, link
);
3138 XEXP (link
, 1) = dead
;
3140 *pprev
= link
= next
;
3145 /* After reg-stack, we need to ignore any unused notes
3146 for the stack registers. */
3147 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3149 pprev
= &XEXP (link
, 1);
3154 rtx next
= XEXP (link
, 1);
3155 #ifdef REG_DEAD_DEBUGGING
3156 df_print_note ("deleting: ", insn
, link
);
3158 XEXP (link
, 1) = unused
;
3160 *pprev
= link
= next
;
3165 pprev
= &XEXP (link
, 1);
3171 *old_dead_notes
= dead
;
3172 *old_unused_notes
= unused
;
3176 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3177 list, otherwise create a new one. */
3180 df_set_note (enum reg_note note_type
, rtx insn
, rtx old
, rtx reg
)
3185 gcc_assert (!DEBUG_INSN_P (insn
));
3188 if (XEXP (curr
, 0) == reg
)
3191 XEXP (prev
, 1) = XEXP (curr
, 1);
3193 old
= XEXP (curr
, 1);
3194 XEXP (curr
, 1) = REG_NOTES (insn
);
3195 REG_NOTES (insn
) = curr
;
3201 curr
= XEXP (curr
, 1);
3204 /* Did not find the note. */
3205 add_reg_note (insn
, note_type
, reg
);
3209 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3210 arguments. Return true if the register value described by MWS's
3211 mw_reg is known to be completely unused, and if mw_reg can therefore
3212 be used in a REG_UNUSED note. */
3215 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
3216 bitmap live
, bitmap artificial_uses
)
3220 /* If MWS describes a partial reference, create REG_UNUSED notes for
3221 individual hard registers. */
3222 if (mws
->flags
& DF_REF_PARTIAL
)
3225 /* Likewise if some part of the register is used. */
3226 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3227 if (bitmap_bit_p (live
, r
)
3228 || bitmap_bit_p (artificial_uses
, r
))
3231 gcc_assert (REG_P (mws
->mw_reg
));
3235 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3236 based on the bits in LIVE. Do not generate notes for registers in
3237 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3238 not generated if the reg is both read and written by the
3243 df_set_unused_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3244 bitmap live
, bitmap do_not_gen
,
3245 bitmap artificial_uses
)
3249 #ifdef REG_DEAD_DEBUGGING
3251 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
3252 mws
->start_regno
, mws
->end_regno
);
3255 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
3257 unsigned int regno
= mws
->start_regno
;
3258 old
= df_set_note (REG_UNUSED
, insn
, old
, mws
->mw_reg
);
3260 #ifdef REG_DEAD_DEBUGGING
3261 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3263 bitmap_set_bit (do_not_gen
, regno
);
3264 /* Only do this if the value is totally dead. */
3267 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3269 if (!bitmap_bit_p (live
, r
)
3270 && !bitmap_bit_p (artificial_uses
, r
))
3272 old
= df_set_note (REG_UNUSED
, insn
, old
, regno_reg_rtx
[r
]);
3273 #ifdef REG_DEAD_DEBUGGING
3274 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3277 bitmap_set_bit (do_not_gen
, r
);
3283 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3284 arguments. Return true if the register value described by MWS's
3285 mw_reg is known to be completely dead, and if mw_reg can therefore
3286 be used in a REG_DEAD note. */
3289 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
3290 bitmap live
, bitmap artificial_uses
,
3295 /* If MWS describes a partial reference, create REG_DEAD notes for
3296 individual hard registers. */
3297 if (mws
->flags
& DF_REF_PARTIAL
)
3300 /* Likewise if some part of the register is not dead. */
3301 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3302 if (bitmap_bit_p (live
, r
)
3303 || bitmap_bit_p (artificial_uses
, r
)
3304 || bitmap_bit_p (do_not_gen
, r
))
3307 gcc_assert (REG_P (mws
->mw_reg
));
3311 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3312 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3313 from being set if the instruction both reads and writes the
3317 df_set_dead_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3318 bitmap live
, bitmap do_not_gen
,
3319 bitmap artificial_uses
, bool *added_notes_p
)
3322 bool is_debug
= *added_notes_p
;
3324 *added_notes_p
= false;
3326 #ifdef REG_DEAD_DEBUGGING
3329 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3330 mws
->start_regno
, mws
->end_regno
);
3331 df_print_regset (dump_file
, do_not_gen
);
3332 fprintf (dump_file
, " live =");
3333 df_print_regset (dump_file
, live
);
3334 fprintf (dump_file
, " artificial uses =");
3335 df_print_regset (dump_file
, artificial_uses
);
3339 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3341 /* Add a dead note for the entire multi word register. */
3344 *added_notes_p
= true;
3347 old
= df_set_note (REG_DEAD
, insn
, old
, mws
->mw_reg
);
3348 #ifdef REG_DEAD_DEBUGGING
3349 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3354 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3355 if (!bitmap_bit_p (live
, r
)
3356 && !bitmap_bit_p (artificial_uses
, r
)
3357 && !bitmap_bit_p (do_not_gen
, r
))
3361 *added_notes_p
= true;
3364 old
= df_set_note (REG_DEAD
, insn
, old
, regno_reg_rtx
[r
]);
3365 #ifdef REG_DEAD_DEBUGGING
3366 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3374 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3375 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3378 df_create_unused_note (rtx insn
, rtx old
, df_ref def
,
3379 bitmap live
, bitmap artificial_uses
)
3381 unsigned int dregno
= DF_REF_REGNO (def
);
3383 #ifdef REG_DEAD_DEBUGGING
3386 fprintf (dump_file
, " regular looking at def ");
3387 df_ref_debug (def
, dump_file
);
3391 if (!(bitmap_bit_p (live
, dregno
)
3392 || (DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3393 || bitmap_bit_p (artificial_uses
, dregno
)
3394 || df_ignore_stack_reg (dregno
)))
3396 rtx reg
= (DF_REF_LOC (def
))
3397 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3398 old
= df_set_note (REG_UNUSED
, insn
, old
, reg
);
3399 #ifdef REG_DEAD_DEBUGGING
3400 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3408 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3409 info: lifetime, bb, and number of defs and uses for basic block
3410 BB. The three bitvectors are scratch regs used here. */
3413 df_note_bb_compute (unsigned int bb_index
,
3414 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3416 basic_block bb
= BASIC_BLOCK (bb_index
);
3421 bitmap_copy (live
, df_get_live_out (bb
));
3422 bitmap_clear (artificial_uses
);
3424 #ifdef REG_DEAD_DEBUGGING
3427 fprintf (dump_file
, "live at bottom ");
3428 df_print_regset (dump_file
, live
);
3432 /* Process the artificial defs and uses at the bottom of the block
3433 to begin processing. */
3434 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3436 df_ref def
= *def_rec
;
3437 #ifdef REG_DEAD_DEBUGGING
3439 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3442 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3443 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3446 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3448 df_ref use
= *use_rec
;
3449 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3451 unsigned int regno
= DF_REF_REGNO (use
);
3452 bitmap_set_bit (live
, regno
);
3454 /* Notes are not generated for any of the artificial registers
3455 at the bottom of the block. */
3456 bitmap_set_bit (artificial_uses
, regno
);
3460 #ifdef REG_DEAD_DEBUGGING
3463 fprintf (dump_file
, "live before artificials out ");
3464 df_print_regset (dump_file
, live
);
3468 FOR_BB_INSNS_REVERSE (bb
, insn
)
3470 unsigned int uid
= INSN_UID (insn
);
3471 struct df_mw_hardreg
**mws_rec
;
3473 rtx old_unused_notes
;
3479 debug_insn
= DEBUG_INSN_P (insn
);
3481 bitmap_clear (do_not_gen
);
3482 df_kill_notes (insn
, &old_dead_notes
, &old_unused_notes
);
3484 /* Process the defs. */
3487 #ifdef REG_DEAD_DEBUGGING
3490 fprintf (dump_file
, "processing call %d\n live =", INSN_UID (insn
));
3491 df_print_regset (dump_file
, live
);
3494 /* We only care about real sets for calls. Clobbers cannot
3495 be depended on to really die. */
3496 mws_rec
= DF_INSN_UID_MWS (uid
);
3499 struct df_mw_hardreg
*mws
= *mws_rec
;
3500 if ((DF_MWS_REG_DEF_P (mws
))
3501 && !df_ignore_stack_reg (mws
->start_regno
))
3503 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3504 mws
, live
, do_not_gen
,
3509 /* All of the defs except the return value are some sort of
3510 clobber. This code is for the return. */
3511 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3513 df_ref def
= *def_rec
;
3514 unsigned int dregno
= DF_REF_REGNO (def
);
3515 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3518 = df_create_unused_note (insn
, old_unused_notes
,
3519 def
, live
, artificial_uses
);
3520 bitmap_set_bit (do_not_gen
, dregno
);
3523 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3524 bitmap_clear_bit (live
, dregno
);
3530 mws_rec
= DF_INSN_UID_MWS (uid
);
3533 struct df_mw_hardreg
*mws
= *mws_rec
;
3534 if (DF_MWS_REG_DEF_P (mws
))
3536 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3537 mws
, live
, do_not_gen
,
3542 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3544 df_ref def
= *def_rec
;
3545 unsigned int dregno
= DF_REF_REGNO (def
);
3547 = df_create_unused_note (insn
, old_unused_notes
,
3548 def
, live
, artificial_uses
);
3550 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
3551 bitmap_set_bit (do_not_gen
, dregno
);
3553 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
3554 bitmap_clear_bit (live
, dregno
);
3558 /* Process the uses. */
3559 mws_rec
= DF_INSN_UID_MWS (uid
);
3562 struct df_mw_hardreg
*mws
= *mws_rec
;
3563 if ((DF_MWS_REG_DEF_P (mws
))
3564 && !df_ignore_stack_reg (mws
->start_regno
))
3566 bool really_add_notes
= debug_insn
!= 0;
3569 = df_set_dead_notes_for_mw (insn
, old_dead_notes
,
3570 mws
, live
, do_not_gen
,
3574 if (really_add_notes
)
3580 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3582 df_ref use
= *use_rec
;
3583 unsigned int uregno
= DF_REF_REGNO (use
);
3585 #ifdef REG_DEAD_DEBUGGING
3586 if (dump_file
&& !debug_insn
)
3588 fprintf (dump_file
, " regular looking at use ");
3589 df_ref_debug (use
, dump_file
);
3592 if (!bitmap_bit_p (live
, uregno
))
3600 if ( (!(DF_REF_FLAGS (use
) & DF_REF_MW_HARDREG
))
3601 && (!bitmap_bit_p (do_not_gen
, uregno
))
3602 && (!bitmap_bit_p (artificial_uses
, uregno
))
3603 && (!(DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
))
3604 && (!df_ignore_stack_reg (uregno
)))
3606 rtx reg
= (DF_REF_LOC (use
))
3607 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
3608 old_dead_notes
= df_set_note (REG_DEAD
, insn
, old_dead_notes
, reg
);
3610 #ifdef REG_DEAD_DEBUGGING
3611 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
3614 /* This register is now live. */
3615 bitmap_set_bit (live
, uregno
);
3619 while (old_unused_notes
)
3621 rtx next
= XEXP (old_unused_notes
, 1);
3622 free_EXPR_LIST_node (old_unused_notes
);
3623 old_unused_notes
= next
;
3625 while (old_dead_notes
)
3627 rtx next
= XEXP (old_dead_notes
, 1);
3628 free_EXPR_LIST_node (old_dead_notes
);
3629 old_dead_notes
= next
;
3632 if (debug_insn
== -1)
3634 /* ??? We could probably do better here, replacing dead
3635 registers with their definitions. */
3636 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
3637 df_insn_rescan_debug_internal (insn
);
3643 /* Compute register info: lifetime, bb, and number of defs and uses. */
3645 df_note_compute (bitmap all_blocks
)
3647 unsigned int bb_index
;
3649 bitmap live
= BITMAP_ALLOC (&df_bitmap_obstack
);
3650 bitmap do_not_gen
= BITMAP_ALLOC (&df_bitmap_obstack
);
3651 bitmap artificial_uses
= BITMAP_ALLOC (&df_bitmap_obstack
);
3653 #ifdef REG_DEAD_DEBUGGING
3655 print_rtl_with_bb (dump_file
, get_insns());
3658 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3660 df_note_bb_compute (bb_index
, live
, do_not_gen
, artificial_uses
);
3664 BITMAP_FREE (do_not_gen
);
3665 BITMAP_FREE (artificial_uses
);
3669 /* Free all storage associated with the problem. */
3678 /* All of the information associated every instance of the problem. */
3680 static struct df_problem problem_NOTE
=
3682 DF_NOTE
, /* Problem id. */
3683 DF_NONE
, /* Direction. */
3684 df_note_alloc
, /* Allocate the problem specific data. */
3685 NULL
, /* Reset global information. */
3686 NULL
, /* Free basic block info. */
3687 df_note_compute
, /* Local compute function. */
3688 NULL
, /* Init the solution specific data. */
3689 NULL
, /* Iterative solver. */
3690 NULL
, /* Confluence operator 0. */
3691 NULL
, /* Confluence operator n. */
3692 NULL
, /* Transfer function. */
3693 NULL
, /* Finalize function. */
3694 df_note_free
, /* Free all of the problem information. */
3695 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
3696 NULL
, /* Debugging. */
3697 NULL
, /* Debugging start block. */
3698 NULL
, /* Debugging end block. */
3699 NULL
, /* Incremental solution verify start. */
3700 NULL
, /* Incremental solution verify end. */
3701 &problem_LR
, /* Dependent problem. */
3702 TV_DF_NOTE
, /* Timing variable. */
3703 false /* Reset blocks on dropping out of blocks_to_analyze. */
3707 /* Create a new DATAFLOW instance and add it to an existing instance
3708 of DF. The returned structure is what is used to get at the
3712 df_note_add_problem (void)
3714 df_add_problem (&problem_NOTE
);
3720 /*----------------------------------------------------------------------------
3721 Functions for simulating the effects of single insns.
3723 You can either simulate in the forwards direction, starting from
3724 the top of a block or the backwards direction from the end of the
3725 block. The main difference is that if you go forwards, the uses
3726 are examined first then the defs, and if you go backwards, the defs
3727 are examined first then the uses.
3729 If you start at the top of the block, use one of DF_LIVE_IN or
3730 DF_LR_IN. If you start at the bottom of the block use one of
3731 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3732 THEY WILL BE DESTROYED.
3733 ----------------------------------------------------------------------------*/
3736 /* Find the set of DEFs for INSN. */
3739 df_simulate_find_defs (rtx insn
, bitmap defs
)
3742 unsigned int uid
= INSN_UID (insn
);
3744 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3746 df_ref def
= *def_rec
;
3747 /* If the def is to only part of the reg, it does
3748 not kill the other defs that reach here. */
3749 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3750 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
3755 /* Simulate the effects of the defs of INSN on LIVE. */
3758 df_simulate_defs (rtx insn
, bitmap live
)
3761 unsigned int uid
= INSN_UID (insn
);
3763 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3765 df_ref def
= *def_rec
;
3766 unsigned int dregno
= DF_REF_REGNO (def
);
3768 /* If the def is to only part of the reg, it does
3769 not kill the other defs that reach here. */
3770 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3771 bitmap_clear_bit (live
, dregno
);
3776 /* Simulate the effects of the uses of INSN on LIVE. */
3779 df_simulate_uses (rtx insn
, bitmap live
)
3782 unsigned int uid
= INSN_UID (insn
);
3784 if (DEBUG_INSN_P (insn
))
3787 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3789 df_ref use
= *use_rec
;
3790 /* Add use to set of uses in this BB. */
3791 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3796 /* Add back the always live regs in BB to LIVE. */
3799 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
3801 /* These regs are considered always live so if they end up dying
3802 because of some def, we need to bring the back again. */
3803 if (bb_has_eh_pred (bb
))
3804 bitmap_ior_into (live
, df
->eh_block_artificial_uses
);
3806 bitmap_ior_into (live
, df
->regular_block_artificial_uses
);
3810 /*----------------------------------------------------------------------------
3811 The following three functions are used only for BACKWARDS scanning:
3812 i.e. they process the defs before the uses.
3814 df_simulate_initialize_backwards should be called first with a
3815 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3816 df_simulate_one_insn_backwards should be called for each insn in
3817 the block, starting with the last on. Finally,
3818 df_simulate_finalize_backwards can be called to get a new value
3819 of the sets at the top of the block (this is rarely used).
3820 ----------------------------------------------------------------------------*/
3822 /* Apply the artificial uses and defs at the end of BB in a backwards
3826 df_simulate_initialize_backwards (basic_block bb
, bitmap live
)
3830 int bb_index
= bb
->index
;
3832 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3834 df_ref def
= *def_rec
;
3835 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3836 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3839 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3841 df_ref use
= *use_rec
;
3842 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3843 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3848 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3851 df_simulate_one_insn_backwards (basic_block bb
, rtx insn
, bitmap live
)
3853 if (!NONDEBUG_INSN_P (insn
))
3856 df_simulate_defs (insn
, live
);
3857 df_simulate_uses (insn
, live
);
3858 df_simulate_fixup_sets (bb
, live
);
3862 /* Apply the artificial uses and defs at the top of BB in a backwards
3866 df_simulate_finalize_backwards (basic_block bb
, bitmap live
)
3872 int bb_index
= bb
->index
;
3874 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3876 df_ref def
= *def_rec
;
3877 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3878 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3882 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3884 df_ref use
= *use_rec
;
3885 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
3886 bitmap_set_bit (live
, DF_REF_REGNO (use
));
3890 /*----------------------------------------------------------------------------
3891 The following three functions are used only for FORWARDS scanning:
3892 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3893 Thus it is important to add the DF_NOTES problem to the stack of
3894 problems computed before using these functions.
3896 df_simulate_initialize_forwards should be called first with a
3897 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3898 df_simulate_one_insn_forwards should be called for each insn in
3899 the block, starting with the last on. Finally,
3900 df_simulate_finalize_forwards can be called to get a new value
3901 of the sets at the bottom of the block (this is rarely used).
3902 ----------------------------------------------------------------------------*/
3904 /* Apply the artificial uses and defs at the top of BB in a backwards
3908 df_simulate_initialize_forwards (basic_block bb
, bitmap live
)
3911 int bb_index
= bb
->index
;
3913 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3915 df_ref def
= *def_rec
;
3916 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3917 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3921 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3924 df_simulate_one_insn_forwards (basic_block bb
, rtx insn
, bitmap live
)
3927 if (! INSN_P (insn
))
3930 /* Make sure that the DF_NOTES really is an active df problem. */
3931 gcc_assert (df_note
);
3933 df_simulate_defs (insn
, live
);
3935 /* Clear all of the registers that go dead. */
3936 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3938 switch (REG_NOTE_KIND (link
))
3943 rtx reg
= XEXP (link
, 0);
3944 int regno
= REGNO (reg
);
3945 if (regno
< FIRST_PSEUDO_REGISTER
)
3947 int n
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
3949 bitmap_clear_bit (live
, regno
+ n
);
3952 bitmap_clear_bit (live
, regno
);
3959 df_simulate_fixup_sets (bb
, live
);
3963 /* Apply the artificial uses and defs at the end of BB in a backwards
3967 df_simulate_finalize_forwards (basic_block bb
, bitmap live
)
3970 int bb_index
= bb
->index
;
3972 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3974 df_ref def
= *def_rec
;
3975 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3976 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3982 /*----------------------------------------------------------------------------
3983 MULTIPLE DEFINITIONS
3985 Find the locations in the function reached by multiple definition sites
3986 for a pseudo. In and out bitvectors are built for each basic
3989 The gen and kill sets for the problem are obvious. Together they
3990 include all defined registers in a basic block; the gen set includes
3991 registers where a partial or conditional or may-clobber definition is
3992 last in the BB, while the kill set includes registers with a complete
3993 definition coming last. However, the computation of the dataflow
3994 itself is interesting.
3996 The idea behind it comes from SSA form's iterated dominance frontier
3997 criterion for inserting PHI functions. Just like in that case, we can use
3998 the dominance frontier to find places where multiple definitions meet;
3999 a register X defined in a basic block BB1 has multiple definitions in
4000 basic blocks in BB1's dominance frontier.
4002 So, the in-set of a basic block BB2 is not just the union of the
4003 out-sets of BB2's predecessors, but includes some more bits that come
4004 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4005 the previous paragraph). I called this set the init-set of BB2.
4007 (Note: I actually use the kill-set only to build the init-set.
4008 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4010 For example, if you have
4014 if <...> goto BB2 else goto BB3;
4022 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4023 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4024 not need to iterate the dominance frontier, because we do not insert
4025 anything like PHI functions there! Instead, dataflow will take care of
4026 propagating the information to BB3's successors.
4027 ---------------------------------------------------------------------------*/
4029 /* Set basic block info. */
4032 df_md_set_bb_info (unsigned int index
,
4033 struct df_md_bb_info
*bb_info
)
4036 gcc_assert (index
< df_md
->block_info_size
);
4037 df_md
->block_info
[index
] = bb_info
;
4042 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
4045 struct df_md_bb_info
*bb_info
= (struct df_md_bb_info
*) vbb_info
;
4048 BITMAP_FREE (bb_info
->kill
);
4049 BITMAP_FREE (bb_info
->gen
);
4050 BITMAP_FREE (bb_info
->init
);
4051 BITMAP_FREE (bb_info
->in
);
4052 BITMAP_FREE (bb_info
->out
);
4053 pool_free (df_md
->block_pool
, bb_info
);
4058 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4059 not touched unless the block is new. */
4062 df_md_alloc (bitmap all_blocks
)
4064 unsigned int bb_index
;
4067 if (!df_md
->block_pool
)
4068 df_md
->block_pool
= create_alloc_pool ("df_md_block pool",
4069 sizeof (struct df_md_bb_info
), 50);
4071 df_grow_bb_info (df_md
);
4073 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4075 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4078 bitmap_clear (bb_info
->init
);
4079 bitmap_clear (bb_info
->gen
);
4080 bitmap_clear (bb_info
->kill
);
4081 bitmap_clear (bb_info
->in
);
4082 bitmap_clear (bb_info
->out
);
4086 bb_info
= (struct df_md_bb_info
*) pool_alloc (df_md
->block_pool
);
4087 df_md_set_bb_info (bb_index
, bb_info
);
4088 bb_info
->init
= BITMAP_ALLOC (NULL
);
4089 bb_info
->gen
= BITMAP_ALLOC (NULL
);
4090 bb_info
->kill
= BITMAP_ALLOC (NULL
);
4091 bb_info
->in
= BITMAP_ALLOC (NULL
);
4092 bb_info
->out
= BITMAP_ALLOC (NULL
);
4096 df_md
->optional_p
= true;
4099 /* Add the effect of the top artificial defs of BB to the multiple definitions
4103 df_md_simulate_artificial_defs_at_top (basic_block bb
, bitmap local_md
)
4105 int bb_index
= bb
->index
;
4107 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4109 df_ref def
= *def_rec
;
4110 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4112 unsigned int dregno
= DF_REF_REGNO (def
);
4113 if (DF_REF_FLAGS (def
)
4114 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4115 bitmap_set_bit (local_md
, dregno
);
4117 bitmap_clear_bit (local_md
, dregno
);
4123 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4127 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
4130 unsigned uid
= INSN_UID (insn
);
4133 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4135 df_ref def
= *def_rec
;
4136 unsigned int dregno
= DF_REF_REGNO (def
);
4137 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4138 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4140 if (DF_REF_FLAGS (def
)
4141 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4142 bitmap_set_bit (local_md
, DF_REF_ID (def
));
4144 bitmap_clear_bit (local_md
, DF_REF_ID (def
));
4150 df_md_bb_local_compute_process_def (struct df_md_bb_info
*bb_info
,
4155 bitmap_clear (seen_in_insn
);
4157 while ((def
= *def_rec
++) != NULL
)
4159 unsigned int dregno
= DF_REF_REGNO (def
);
4160 if (((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4161 || (dregno
>= FIRST_PSEUDO_REGISTER
))
4162 && top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
4164 if (!bitmap_bit_p (seen_in_insn
, dregno
))
4166 if (DF_REF_FLAGS (def
)
4167 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))
4169 bitmap_set_bit (bb_info
->gen
, dregno
);
4170 bitmap_clear_bit (bb_info
->kill
, dregno
);
4174 /* When we find a clobber and a regular def,
4175 make sure the regular def wins. */
4176 bitmap_set_bit (seen_in_insn
, dregno
);
4177 bitmap_set_bit (bb_info
->kill
, dregno
);
4178 bitmap_clear_bit (bb_info
->gen
, dregno
);
4186 /* Compute local multiple def info for basic block BB. */
4189 df_md_bb_local_compute (unsigned int bb_index
)
4191 basic_block bb
= BASIC_BLOCK (bb_index
);
4192 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4195 /* Artificials are only hard regs. */
4196 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4197 df_md_bb_local_compute_process_def (bb_info
,
4198 df_get_artificial_defs (bb_index
),
4201 FOR_BB_INSNS (bb
, insn
)
4203 unsigned int uid
= INSN_UID (insn
);
4207 df_md_bb_local_compute_process_def (bb_info
, DF_INSN_UID_DEFS (uid
), 0);
4210 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
4211 df_md_bb_local_compute_process_def (bb_info
,
4212 df_get_artificial_defs (bb_index
),
4216 /* Compute local reaching def info for each basic block within BLOCKS. */
4219 df_md_local_compute (bitmap all_blocks
)
4221 unsigned int bb_index
, df_bb_index
;
4222 bitmap_iterator bi1
, bi2
;
4226 seen_in_insn
= BITMAP_ALLOC (NULL
);
4228 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4230 df_md_bb_local_compute (bb_index
);
4233 BITMAP_FREE (seen_in_insn
);
4235 frontiers
= XNEWVEC (bitmap
, last_basic_block
);
4237 frontiers
[bb
->index
] = BITMAP_ALLOC (NULL
);
4239 compute_dominance_frontiers (frontiers
);
4241 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4242 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi1
)
4244 bitmap kill
= df_md_get_bb_info (bb_index
)->kill
;
4245 EXECUTE_IF_SET_IN_BITMAP (frontiers
[bb_index
], 0, df_bb_index
, bi2
)
4247 if (bitmap_bit_p (all_blocks
, df_bb_index
))
4248 bitmap_ior_into (df_md_get_bb_info (df_bb_index
)->init
, kill
);
4253 BITMAP_FREE (frontiers
[bb
->index
]);
4258 /* Reset the global solution for recalculation. */
4261 df_md_reset (bitmap all_blocks
)
4263 unsigned int bb_index
;
4266 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4268 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4269 gcc_assert (bb_info
);
4270 bitmap_clear (bb_info
->in
);
4271 bitmap_clear (bb_info
->out
);
4276 df_md_transfer_function (int bb_index
)
4278 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4279 bitmap in
= bb_info
->in
;
4280 bitmap out
= bb_info
->out
;
4281 bitmap gen
= bb_info
->gen
;
4282 bitmap kill
= bb_info
->kill
;
4284 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
4287 /* Initialize the solution bit vectors for problem. */
4290 df_md_init (bitmap all_blocks
)
4292 unsigned int bb_index
;
4295 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4297 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb_index
);
4299 bitmap_copy (bb_info
->in
, bb_info
->init
);
4300 df_md_transfer_function (bb_index
);
4305 df_md_confluence_0 (basic_block bb
)
4307 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4308 bitmap_copy (bb_info
->in
, bb_info
->init
);
4311 /* In of target gets or of out of source. */
4314 df_md_confluence_n (edge e
)
4316 bitmap op1
= df_md_get_bb_info (e
->dest
->index
)->in
;
4317 bitmap op2
= df_md_get_bb_info (e
->src
->index
)->out
;
4319 if (e
->flags
& EDGE_FAKE
)
4322 if (e
->flags
& EDGE_EH
)
4323 bitmap_ior_and_compl_into (op1
, op2
, regs_invalidated_by_call_regset
);
4325 bitmap_ior_into (op1
, op2
);
4328 /* Free all storage associated with the problem. */
4334 for (i
= 0; i
< df_md
->block_info_size
; i
++)
4336 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (i
);
4339 BITMAP_FREE (bb_info
->kill
);
4340 BITMAP_FREE (bb_info
->gen
);
4341 BITMAP_FREE (bb_info
->init
);
4342 BITMAP_FREE (bb_info
->in
);
4343 BITMAP_FREE (bb_info
->out
);
4347 free_alloc_pool (df_md
->block_pool
);
4349 df_md
->block_info_size
= 0;
4350 free (df_md
->block_info
);
4355 /* Debugging info at top of bb. */
4358 df_md_top_dump (basic_block bb
, FILE *file
)
4360 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4361 if (!bb_info
|| !bb_info
->in
)
4364 fprintf (file
, ";; md in \t");
4365 df_print_regset (file
, bb_info
->in
);
4366 fprintf (file
, ";; md init \t");
4367 df_print_regset (file
, bb_info
->init
);
4368 fprintf (file
, ";; md gen \t");
4369 df_print_regset (file
, bb_info
->gen
);
4370 fprintf (file
, ";; md kill \t");
4371 df_print_regset (file
, bb_info
->kill
);
4374 /* Debugging info at bottom of bb. */
4377 df_md_bottom_dump (basic_block bb
, FILE *file
)
4379 struct df_md_bb_info
*bb_info
= df_md_get_bb_info (bb
->index
);
4380 if (!bb_info
|| !bb_info
->out
)
4383 fprintf (file
, ";; md out \t");
4384 df_print_regset (file
, bb_info
->out
);
4387 static struct df_problem problem_MD
=
4389 DF_MD
, /* Problem id. */
4390 DF_FORWARD
, /* Direction. */
4391 df_md_alloc
, /* Allocate the problem specific data. */
4392 df_md_reset
, /* Reset global information. */
4393 df_md_free_bb_info
, /* Free basic block info. */
4394 df_md_local_compute
, /* Local compute function. */
4395 df_md_init
, /* Init the solution specific data. */
4396 df_worklist_dataflow
, /* Worklist solver. */
4397 df_md_confluence_0
, /* Confluence operator 0. */
4398 df_md_confluence_n
, /* Confluence operator n. */
4399 df_md_transfer_function
, /* Transfer function. */
4400 NULL
, /* Finalize function. */
4401 df_md_free
, /* Free all of the problem information. */
4402 df_md_free
, /* Remove this problem from the stack of dataflow problems. */
4403 NULL
, /* Debugging. */
4404 df_md_top_dump
, /* Debugging start block. */
4405 df_md_bottom_dump
, /* Debugging end block. */
4406 NULL
, /* Incremental solution verify start. */
4407 NULL
, /* Incremental solution verify end. */
4408 NULL
, /* Dependent problem. */
4409 TV_DF_MD
, /* Timing variable. */
4410 false /* Reset blocks on dropping out of blocks_to_analyze. */
4413 /* Create a new MD instance and add it to the existing instance
4417 df_md_add_problem (void)
4419 df_add_problem (&problem_MD
);