1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "alloc-pool.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
48 /* Note that turning REG_DEAD_DEBUGGING on will cause
49 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50 addresses in the dumps. */
52 #define REG_DEAD_DEBUGGING
55 #define DF_SPARSE_THRESHOLD 32
57 static bitmap seen_in_block
= NULL
;
58 static bitmap seen_in_insn
= NULL
;
61 /*----------------------------------------------------------------------------
62 Public functions access functions for the dataflow problems.
63 ----------------------------------------------------------------------------*/
64 /* Get the live at out set for BB no matter what problem happens to be
65 defined. This function is used by the register allocators who
66 choose different dataflow problems depending on the optimization
70 df_get_live_out (basic_block bb
)
75 return DF_RA_LIVE_OUT (bb
);
77 return DF_LIVE_OUT (bb
);
79 return DF_LR_OUT (bb
);
82 /* Get the live at in set for BB no matter what problem happens to be
83 defined. This function is used by the register allocators who
84 choose different dataflow problems depending on the optimization
88 df_get_live_in (basic_block bb
)
93 return DF_RA_LIVE_IN (bb
);
95 return DF_LIVE_IN (bb
);
100 /* Get the live at top set for BB no matter what problem happens to be
101 defined. This function is used by the register allocators who
102 choose different dataflow problems depending on the optimization
106 df_get_live_top (basic_block bb
)
111 return DF_RA_LIVE_TOP (bb
);
113 return DF_LR_TOP (bb
);
117 /*----------------------------------------------------------------------------
119 ----------------------------------------------------------------------------*/
121 /* Generic versions to get the void* version of the block info. Only
122 used inside the problem instance vectors. */
124 /* Grow the bb_info array. */
127 df_grow_bb_info (struct dataflow
*dflow
)
129 unsigned int new_size
= last_basic_block
+ 1;
130 if (dflow
->block_info_size
< new_size
)
132 new_size
+= new_size
/ 4;
133 dflow
->block_info
= xrealloc (dflow
->block_info
,
134 new_size
*sizeof (void*));
135 memset (dflow
->block_info
+ dflow
->block_info_size
, 0,
136 (new_size
- dflow
->block_info_size
) *sizeof (void *));
137 dflow
->block_info_size
= new_size
;
141 /* Dump a def-use or use-def chain for REF to FILE. */
144 df_chain_dump (struct df_link
*link
, FILE *file
)
146 fprintf (file
, "{ ");
147 for (; link
; link
= link
->next
)
149 fprintf (file
, "%c%d(bb %d insn %d) ",
150 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
151 DF_REF_ID (link
->ref
),
152 DF_REF_BBNO (link
->ref
),
153 DF_REF_INSN (link
->ref
) ? DF_REF_INSN_UID (link
->ref
) : -1);
159 /* Print some basic block info as part of df_dump. */
162 df_print_bb_index (basic_block bb
, FILE *file
)
167 fprintf (file
, "\n( ");
168 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
170 basic_block pred
= e
->src
;
171 fprintf (file
, "%d%s ", pred
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
173 fprintf (file
, ")->[%d]->( ", bb
->index
);
174 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
176 basic_block succ
= e
->dest
;
177 fprintf (file
, "%d%s ", succ
->index
, e
->flags
& EDGE_EH
? "(EH)" : "");
179 fprintf (file
, ")\n");
184 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
190 seen_in_block
= BITMAP_ALLOC (&df_bitmap_obstack
);
191 seen_in_insn
= BITMAP_ALLOC (&df_bitmap_obstack
);
198 BITMAP_FREE (seen_in_block
);
199 BITMAP_FREE (seen_in_insn
);
204 /*----------------------------------------------------------------------------
207 Find the locations in the function where each use site for a pseudo
208 can reach backwards. In and out bitvectors are built for each basic
209 block. The id field in the ref is used to index into these sets.
210 See df.h for details.
212 ----------------------------------------------------------------------------*/
214 /* This problem plays a large number of games for the sake of
217 1) The order of the bits in the bitvectors. After the scanning
218 phase, all of the uses are sorted. All of the uses for the reg 0
219 are first, followed by all uses for reg 1 and so on.
221 2) There are two kill sets, one if the number of uses is less or
222 equal to DF_SPARSE_THRESHOLD and another if it is greater.
224 <= : Data is built directly in the kill set.
226 > : One level of indirection is used to keep from generating long
227 strings of 1 bits in the kill sets. Bitvectors that are indexed
228 by the regnum are used to represent that there is a killing def
229 for the register. The confluence and transfer functions use
230 these along with the bitmap_clear_range call to remove ranges of
231 bits without actually generating a knockout vector.
233 The kill and sparse_kill and the dense_invalidated_by_call and
234 sparse_invalidated_by_call both play this game. */
236 /* Private data used to compute the solution for this problem. These
237 data structures are not accessible outside of this module. */
238 struct df_ru_problem_data
240 /* The set of defs to regs invalidated by call. */
241 bitmap sparse_invalidated_by_call
;
242 /* The set of defs to regs invalidated by call for ru. */
243 bitmap dense_invalidated_by_call
;
244 /* An obstack for the bitmaps we need for this problem. */
245 bitmap_obstack ru_bitmaps
;
248 /* Set basic block info. */
251 df_ru_set_bb_info (unsigned int index
, struct df_ru_bb_info
*bb_info
)
254 gcc_assert (index
< df_ru
->block_info_size
);
255 df_ru
->block_info
[index
] = bb_info
;
259 /* Free basic block info. */
262 df_ru_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
265 struct df_ru_bb_info
*bb_info
= (struct df_ru_bb_info
*) vbb_info
;
268 BITMAP_FREE (bb_info
->kill
);
269 BITMAP_FREE (bb_info
->sparse_kill
);
270 BITMAP_FREE (bb_info
->gen
);
271 BITMAP_FREE (bb_info
->in
);
272 BITMAP_FREE (bb_info
->out
);
273 pool_free (df_ru
->block_pool
, bb_info
);
278 /* Allocate or reset bitmaps for DF_RU blocks. The solution bits are
279 not touched unless the block is new. */
282 df_ru_alloc (bitmap all_blocks
)
284 unsigned int bb_index
;
286 struct df_ru_problem_data
*problem_data
;
288 if (!df_ru
->block_pool
)
289 df_ru
->block_pool
= create_alloc_pool ("df_ru_block pool",
290 sizeof (struct df_ru_bb_info
), 50);
292 if (df_ru
->problem_data
)
294 problem_data
= (struct df_ru_problem_data
*) df_ru
->problem_data
;
295 bitmap_clear (problem_data
->sparse_invalidated_by_call
);
296 bitmap_clear (problem_data
->dense_invalidated_by_call
);
300 problem_data
= XNEW (struct df_ru_problem_data
);
301 df_ru
->problem_data
= problem_data
;
303 bitmap_obstack_initialize (&problem_data
->ru_bitmaps
);
304 problem_data
->sparse_invalidated_by_call
305 = BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
306 problem_data
->dense_invalidated_by_call
307 = BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
310 df_grow_bb_info (df_ru
);
312 /* Because of the clustering of all def sites for the same pseudo,
313 we have to process all of the blocks before doing the
316 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
318 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (bb_index
);
321 bitmap_clear (bb_info
->kill
);
322 bitmap_clear (bb_info
->sparse_kill
);
323 bitmap_clear (bb_info
->gen
);
327 bb_info
= (struct df_ru_bb_info
*) pool_alloc (df_ru
->block_pool
);
328 df_ru_set_bb_info (bb_index
, bb_info
);
329 bb_info
->kill
= BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
330 bb_info
->sparse_kill
= BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
331 bb_info
->gen
= BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
332 bb_info
->in
= BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
333 bb_info
->out
= BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
336 df_ru
->optional_p
= true;
340 /* Process a list of DEFs for df_ru_bb_local_compute. */
343 df_ru_bb_local_compute_process_def (struct df_ru_bb_info
*bb_info
,
344 struct df_ref
**def_rec
,
345 enum df_ref_flags top_flag
)
349 struct df_ref
*def
= *def_rec
;
350 if ((top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
351 /* If the def is to only part of the reg, it is as if it did
352 not happen, since some of the bits may get thru. */
353 && (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))))
355 unsigned int regno
= DF_REF_REGNO (def
);
356 unsigned int begin
= DF_USES_BEGIN (regno
);
357 unsigned int n_uses
= DF_USES_COUNT (regno
);
359 if (!bitmap_bit_p (seen_in_block
, regno
))
361 /* The first def for regno in the insn, causes the kill
362 info to be generated. Do not modify the gen set
363 because the only values in it are the uses from here
364 to the top of the block and this def does not effect
366 if (!bitmap_bit_p (seen_in_insn
, regno
))
368 if (n_uses
> DF_SPARSE_THRESHOLD
)
369 bitmap_set_bit (bb_info
->sparse_kill
, regno
);
371 bitmap_set_range (bb_info
->kill
, begin
, n_uses
);
373 bitmap_set_bit (seen_in_insn
, regno
);
381 /* Process a list of USEs for df_ru_bb_local_compute. */
384 df_ru_bb_local_compute_process_use (struct df_ru_bb_info
*bb_info
,
385 struct df_ref
**use_rec
,
386 enum df_ref_flags top_flag
)
390 struct df_ref
*use
= *use_rec
;
391 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
393 /* Add use to set of gens in this BB unless we have seen a
394 def in a previous instruction. */
395 unsigned int regno
= DF_REF_REGNO (use
);
396 if (!bitmap_bit_p (seen_in_block
, regno
))
397 bitmap_set_bit (bb_info
->gen
, DF_REF_ID (use
));
403 /* Compute local reaching use (upward exposed use) info for basic
404 block BB. USE_INFO->REGS[R] caches the set of uses for register R. */
406 df_ru_bb_local_compute (unsigned int bb_index
)
408 basic_block bb
= BASIC_BLOCK (bb_index
);
409 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (bb_index
);
412 /* Set when a def for regno is seen. */
413 bitmap_clear (seen_in_block
);
414 bitmap_clear (seen_in_insn
);
417 /* Variables defined in the prolog that are used by the exception
419 df_ru_bb_local_compute_process_use (bb_info
,
420 df_get_artificial_uses (bb_index
),
423 df_ru_bb_local_compute_process_def (bb_info
,
424 df_get_artificial_defs (bb_index
),
427 FOR_BB_INSNS (bb
, insn
)
429 unsigned int uid
= INSN_UID (insn
);
433 df_ru_bb_local_compute_process_use (bb_info
,
434 DF_INSN_UID_USES (uid
), 0);
436 if (df
->changeable_flags
& DF_EQ_NOTES
)
437 df_ru_bb_local_compute_process_use (bb_info
,
438 DF_INSN_UID_EQ_USES (uid
), 0);
440 df_ru_bb_local_compute_process_def (bb_info
,
441 DF_INSN_UID_DEFS (uid
), 0);
443 bitmap_ior_into (seen_in_block
, seen_in_insn
);
444 bitmap_clear (seen_in_insn
);
447 /* Process the hardware registers that are always live. */
448 df_ru_bb_local_compute_process_use (bb_info
,
449 df_get_artificial_uses (bb_index
), 0);
451 df_ru_bb_local_compute_process_def (bb_info
,
452 df_get_artificial_defs (bb_index
), 0);
456 /* Compute local reaching use (upward exposed use) info for each basic
457 block within BLOCKS. */
459 df_ru_local_compute (bitmap all_blocks
)
461 unsigned int bb_index
;
464 struct df_ru_problem_data
*problem_data
465 = (struct df_ru_problem_data
*) df_ru
->problem_data
;
466 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
467 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
471 df_maybe_reorganize_use_refs (df
->changeable_flags
& DF_EQ_NOTES
?
472 DF_REF_ORDER_BY_REG_WITH_NOTES
: DF_REF_ORDER_BY_REG
);
474 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
476 df_ru_bb_local_compute (bb_index
);
479 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
480 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call
, 0, regno
, bi
)
482 if (DF_USES_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
483 bitmap_set_bit (sparse_invalidated
, regno
);
485 bitmap_set_range (dense_invalidated
,
486 DF_USES_BEGIN (regno
),
487 DF_USES_COUNT (regno
));
494 /* Initialize the solution bit vectors for problem. */
497 df_ru_init_solution (bitmap all_blocks
)
499 unsigned int bb_index
;
502 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
504 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (bb_index
);
505 bitmap_copy (bb_info
->in
, bb_info
->gen
);
506 bitmap_clear (bb_info
->out
);
511 /* Out of target gets or of in of source. */
514 df_ru_confluence_n (edge e
)
516 bitmap op1
= df_ru_get_bb_info (e
->src
->index
)->out
;
517 bitmap op2
= df_ru_get_bb_info (e
->dest
->index
)->in
;
519 if (e
->flags
& EDGE_EH
)
521 struct df_ru_problem_data
*problem_data
522 = (struct df_ru_problem_data
*) df_ru
->problem_data
;
523 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
524 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
527 bitmap tmp
= BITMAP_ALLOC (&df_bitmap_obstack
);
529 bitmap_copy (tmp
, op2
);
530 bitmap_and_compl_into (tmp
, dense_invalidated
);
532 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
534 bitmap_clear_range (tmp
,
535 DF_USES_BEGIN (regno
),
536 DF_USES_COUNT (regno
));
538 bitmap_ior_into (op1
, tmp
);
542 bitmap_ior_into (op1
, op2
);
546 /* Transfer function. */
549 df_ru_transfer_function (int bb_index
)
551 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (bb_index
);
554 bitmap in
= bb_info
->in
;
555 bitmap out
= bb_info
->out
;
556 bitmap gen
= bb_info
->gen
;
557 bitmap kill
= bb_info
->kill
;
558 bitmap sparse_kill
= bb_info
->sparse_kill
;
560 if (bitmap_empty_p (sparse_kill
))
561 return bitmap_ior_and_compl (in
, gen
, out
, kill
);
564 struct df_ru_problem_data
*problem_data
;
566 bool changed
= false;
568 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
569 IN with TMP. Therefore, allocate TMP in the RU bitmaps obstack. */
570 problem_data
= (struct df_ru_problem_data
*) df_ru
->problem_data
;
571 tmp
= BITMAP_ALLOC (&problem_data
->ru_bitmaps
);
573 bitmap_copy (tmp
, out
);
574 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
576 bitmap_clear_range (tmp
,
577 DF_USES_BEGIN (regno
),
578 DF_USES_COUNT (regno
));
580 bitmap_and_compl_into (tmp
, kill
);
581 bitmap_ior_into (tmp
, gen
);
582 changed
= !bitmap_equal_p (tmp
, in
);
595 /* Free all storage associated with the problem. */
601 struct df_ru_problem_data
*problem_data
602 = (struct df_ru_problem_data
*) df_ru
->problem_data
;
606 for (i
= 0; i
< df_ru
->block_info_size
; i
++)
608 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (i
);
611 BITMAP_FREE (bb_info
->kill
);
612 BITMAP_FREE (bb_info
->sparse_kill
);
613 BITMAP_FREE (bb_info
->gen
);
614 BITMAP_FREE (bb_info
->in
);
615 BITMAP_FREE (bb_info
->out
);
619 free_alloc_pool (df_ru
->block_pool
);
620 BITMAP_FREE (problem_data
->sparse_invalidated_by_call
);
621 BITMAP_FREE (problem_data
->dense_invalidated_by_call
);
622 bitmap_obstack_release (&problem_data
->ru_bitmaps
);
624 df_ru
->block_info_size
= 0;
625 free (df_ru
->block_info
);
626 free (df_ru
->problem_data
);
632 /* Debugging info. */
635 df_ru_start_dump (FILE *file
)
637 struct df_ru_problem_data
*problem_data
638 = (struct df_ru_problem_data
*) df_ru
->problem_data
;
639 unsigned int m
= DF_REG_SIZE(df
);
642 if (!df_ru
->block_info
)
645 fprintf (file
, ";; Reaching uses:\n");
647 fprintf (file
, ";; sparse invalidated \t");
648 dump_bitmap (file
, problem_data
->sparse_invalidated_by_call
);
649 fprintf (file
, " dense invalidated \t");
650 dump_bitmap (file
, problem_data
->dense_invalidated_by_call
);
652 for (regno
= 0; regno
< m
; regno
++)
653 if (DF_USES_COUNT (regno
))
654 fprintf (file
, "%d[%d,%d] ", regno
,
655 DF_USES_BEGIN (regno
),
656 DF_USES_COUNT (regno
));
657 fprintf (file
, "\n");
661 /* Debugging info at top of bb. */
664 df_ru_top_dump (basic_block bb
, FILE *file
)
666 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (bb
->index
);
667 if (!bb_info
|| !bb_info
->in
)
670 fprintf (file
, ";; ru in \t(%d)\n", (int) bitmap_count_bits (bb_info
->in
));
671 dump_bitmap (file
, bb_info
->in
);
672 fprintf (file
, ";; ru gen \t(%d)\n", (int) bitmap_count_bits (bb_info
->gen
));
673 dump_bitmap (file
, bb_info
->gen
);
674 fprintf (file
, ";; ru kill\t(%d)\n", (int) bitmap_count_bits (bb_info
->kill
));
675 dump_bitmap (file
, bb_info
->kill
);
679 /* Debugging info at bottom of bb. */
682 df_ru_bottom_dump (basic_block bb
, FILE *file
)
684 struct df_ru_bb_info
*bb_info
= df_ru_get_bb_info (bb
->index
);
685 if (!bb_info
|| !bb_info
->out
)
688 fprintf (file
, ";; ru out \t(%d)\n", (int) bitmap_count_bits (bb_info
->out
));
689 dump_bitmap (file
, bb_info
->out
);
693 /* All of the information associated with every instance of the problem. */
695 static struct df_problem problem_RU
=
697 DF_RU
, /* Problem id. */
698 DF_BACKWARD
, /* Direction. */
699 df_ru_alloc
, /* Allocate the problem specific data. */
700 NULL
, /* Reset global information. */
701 df_ru_free_bb_info
, /* Free basic block info. */
702 df_ru_local_compute
, /* Local compute function. */
703 df_ru_init_solution
, /* Init the solution specific data. */
704 df_worklist_dataflow
, /* Worklist solver. */
705 NULL
, /* Confluence operator 0. */
706 df_ru_confluence_n
, /* Confluence operator n. */
707 df_ru_transfer_function
, /* Transfer function. */
708 NULL
, /* Finalize function. */
709 df_ru_free
, /* Free all of the problem information. */
710 df_ru_free
, /* Remove this problem from the stack of dataflow problems. */
711 df_ru_start_dump
, /* Debugging. */
712 df_ru_top_dump
, /* Debugging start block. */
713 df_ru_bottom_dump
, /* Debugging end block. */
714 NULL
, /* Incremental solution verify start. */
715 NULL
, /* Incremental solution verify end. */
716 NULL
, /* Dependent problem. */
717 TV_DF_RU
, /* Timing variable. */
718 true /* Reset blocks on dropping out of blocks_to_analyze. */
723 /* Create a new DATAFLOW instance and add it to an existing instance
724 of DF. The returned structure is what is used to get at the
728 df_ru_add_problem (void)
730 df_add_problem (&problem_RU
);
734 /*----------------------------------------------------------------------------
737 Find the locations in the function where each definition site for a
738 pseudo reaches. In and out bitvectors are built for each basic
739 block. The id field in the ref is used to index into these sets.
740 See df.h for details.
741 ----------------------------------------------------------------------------*/
743 /* See the comment at the top of the Reaching Uses problem for how the
744 uses are represented in the kill sets. The same games are played
745 here for the defs. */
747 /* Private data used to compute the solution for this problem. These
748 data structures are not accessible outside of this module. */
749 struct df_rd_problem_data
751 /* The set of defs to regs invalidated by call. */
752 bitmap sparse_invalidated_by_call
;
753 /* The set of defs to regs invalidate by call for rd. */
754 bitmap dense_invalidated_by_call
;
755 /* An obstack for the bitmaps we need for this problem. */
756 bitmap_obstack rd_bitmaps
;
759 /* Set basic block info. */
762 df_rd_set_bb_info (unsigned int index
,
763 struct df_rd_bb_info
*bb_info
)
766 gcc_assert (index
< df_rd
->block_info_size
);
767 df_rd
->block_info
[index
] = bb_info
;
771 /* Free basic block info. */
774 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
777 struct df_rd_bb_info
*bb_info
= (struct df_rd_bb_info
*) vbb_info
;
780 BITMAP_FREE (bb_info
->kill
);
781 BITMAP_FREE (bb_info
->sparse_kill
);
782 BITMAP_FREE (bb_info
->gen
);
783 BITMAP_FREE (bb_info
->in
);
784 BITMAP_FREE (bb_info
->out
);
785 pool_free (df_rd
->block_pool
, bb_info
);
790 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
791 not touched unless the block is new. */
794 df_rd_alloc (bitmap all_blocks
)
796 unsigned int bb_index
;
798 struct df_rd_problem_data
*problem_data
;
800 if (!df_rd
->block_pool
)
801 df_rd
->block_pool
= create_alloc_pool ("df_rd_block pool",
802 sizeof (struct df_rd_bb_info
), 50);
804 if (df_rd
->problem_data
)
806 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
807 bitmap_clear (problem_data
->sparse_invalidated_by_call
);
808 bitmap_clear (problem_data
->dense_invalidated_by_call
);
812 problem_data
= XNEW (struct df_rd_problem_data
);
813 df_rd
->problem_data
= problem_data
;
815 bitmap_obstack_initialize (&problem_data
->rd_bitmaps
);
816 problem_data
->sparse_invalidated_by_call
817 = BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
818 problem_data
->dense_invalidated_by_call
819 = BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
822 df_grow_bb_info (df_rd
);
824 /* Because of the clustering of all use sites for the same pseudo,
825 we have to process all of the blocks before doing the
828 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
830 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
833 bitmap_clear (bb_info
->kill
);
834 bitmap_clear (bb_info
->sparse_kill
);
835 bitmap_clear (bb_info
->gen
);
839 bb_info
= (struct df_rd_bb_info
*) pool_alloc (df_rd
->block_pool
);
840 df_rd_set_bb_info (bb_index
, bb_info
);
841 bb_info
->kill
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
842 bb_info
->sparse_kill
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
843 bb_info
->gen
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
844 bb_info
->in
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
845 bb_info
->out
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
848 df_rd
->optional_p
= true;
852 /* Process a list of DEFs for df_rd_bb_local_compute. */
855 df_rd_bb_local_compute_process_def (struct df_rd_bb_info
*bb_info
,
856 struct df_ref
**def_rec
,
857 enum df_ref_flags top_flag
)
861 struct df_ref
*def
= *def_rec
;
862 if (top_flag
== (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
))
864 unsigned int regno
= DF_REF_REGNO (def
);
865 unsigned int begin
= DF_DEFS_BEGIN (regno
);
866 unsigned int n_defs
= DF_DEFS_COUNT (regno
);
868 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
869 || (regno
>= FIRST_PSEUDO_REGISTER
))
871 /* Only the last def(s) for a regno in the block has any
873 if (!bitmap_bit_p (seen_in_block
, regno
))
875 /* The first def for regno in insn gets to knock out the
876 defs from other instructions. */
877 if ((!bitmap_bit_p (seen_in_insn
, regno
))
878 /* If the def is to only part of the reg, it does
879 not kill the other defs that reach here. */
880 && (!(DF_REF_FLAGS (def
) &
881 (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
| DF_REF_MAY_CLOBBER
))))
883 if (n_defs
> DF_SPARSE_THRESHOLD
)
885 bitmap_set_bit (bb_info
->sparse_kill
, regno
);
886 bitmap_clear_range(bb_info
->gen
, begin
, n_defs
);
890 bitmap_set_range (bb_info
->kill
, begin
, n_defs
);
891 bitmap_clear_range (bb_info
->gen
, begin
, n_defs
);
895 bitmap_set_bit (seen_in_insn
, regno
);
896 /* All defs for regno in the instruction may be put into
898 if (!(DF_REF_FLAGS (def
)
899 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
900 bitmap_set_bit (bb_info
->gen
, DF_REF_ID (def
));
908 /* Compute local reaching def info for basic block BB. */
911 df_rd_bb_local_compute (unsigned int bb_index
)
913 basic_block bb
= BASIC_BLOCK (bb_index
);
914 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
917 bitmap_clear (seen_in_block
);
918 bitmap_clear (seen_in_insn
);
920 /* Artificials are only hard regs. */
921 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
922 df_rd_bb_local_compute_process_def (bb_info
,
923 df_get_artificial_defs (bb_index
),
926 FOR_BB_INSNS_REVERSE (bb
, insn
)
928 unsigned int uid
= INSN_UID (insn
);
933 df_rd_bb_local_compute_process_def (bb_info
,
934 DF_INSN_UID_DEFS (uid
), 0);
936 /* This complex dance with the two bitmaps is required because
937 instructions can assign twice to the same pseudo. This
938 generally happens with calls that will have one def for the
939 result and another def for the clobber. If only one vector
940 is used and the clobber goes first, the result will be
942 bitmap_ior_into (seen_in_block
, seen_in_insn
);
943 bitmap_clear (seen_in_insn
);
946 /* Process the artificial defs at the top of the block last since we
947 are going backwards through the block and these are logically at
949 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
950 df_rd_bb_local_compute_process_def (bb_info
,
951 df_get_artificial_defs (bb_index
),
956 /* Compute local reaching def info for each basic block within BLOCKS. */
959 df_rd_local_compute (bitmap all_blocks
)
961 unsigned int bb_index
;
964 struct df_rd_problem_data
*problem_data
965 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
966 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
967 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
971 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG
);
973 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
975 df_rd_bb_local_compute (bb_index
);
978 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
979 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call
, 0, regno
, bi
)
981 if (DF_DEFS_COUNT (regno
) > DF_SPARSE_THRESHOLD
)
982 bitmap_set_bit (sparse_invalidated
, regno
);
984 bitmap_set_range (dense_invalidated
,
985 DF_DEFS_BEGIN (regno
),
986 DF_DEFS_COUNT (regno
));
992 /* Initialize the solution bit vectors for problem. */
995 df_rd_init_solution (bitmap all_blocks
)
997 unsigned int bb_index
;
1000 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1002 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
1004 bitmap_copy (bb_info
->out
, bb_info
->gen
);
1005 bitmap_clear (bb_info
->in
);
1009 /* In of target gets or of out of source. */
1012 df_rd_confluence_n (edge e
)
1014 bitmap op1
= df_rd_get_bb_info (e
->dest
->index
)->in
;
1015 bitmap op2
= df_rd_get_bb_info (e
->src
->index
)->out
;
1017 if (e
->flags
& EDGE_EH
)
1019 struct df_rd_problem_data
*problem_data
1020 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
1021 bitmap sparse_invalidated
= problem_data
->sparse_invalidated_by_call
;
1022 bitmap dense_invalidated
= problem_data
->dense_invalidated_by_call
;
1025 bitmap tmp
= BITMAP_ALLOC (&df_bitmap_obstack
);
1027 bitmap_copy (tmp
, op2
);
1028 bitmap_and_compl_into (tmp
, dense_invalidated
);
1030 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated
, 0, regno
, bi
)
1032 bitmap_clear_range (tmp
,
1033 DF_DEFS_BEGIN (regno
),
1034 DF_DEFS_COUNT (regno
));
1036 bitmap_ior_into (op1
, tmp
);
1040 bitmap_ior_into (op1
, op2
);
1044 /* Transfer function. */
1047 df_rd_transfer_function (int bb_index
)
1049 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
1052 bitmap in
= bb_info
->in
;
1053 bitmap out
= bb_info
->out
;
1054 bitmap gen
= bb_info
->gen
;
1055 bitmap kill
= bb_info
->kill
;
1056 bitmap sparse_kill
= bb_info
->sparse_kill
;
1058 if (bitmap_empty_p (sparse_kill
))
1059 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
1062 struct df_rd_problem_data
*problem_data
;
1063 bool changed
= false;
1066 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
1067 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
1068 problem_data
= (struct df_rd_problem_data
*) df_rd
->problem_data
;
1069 tmp
= BITMAP_ALLOC (&problem_data
->rd_bitmaps
);
1071 bitmap_copy (tmp
, in
);
1072 EXECUTE_IF_SET_IN_BITMAP (sparse_kill
, 0, regno
, bi
)
1074 bitmap_clear_range (tmp
,
1075 DF_DEFS_BEGIN (regno
),
1076 DF_DEFS_COUNT (regno
));
1078 bitmap_and_compl_into (tmp
, kill
);
1079 bitmap_ior_into (tmp
, gen
);
1080 changed
= !bitmap_equal_p (tmp
, out
);
1093 /* Free all storage associated with the problem. */
1099 struct df_rd_problem_data
*problem_data
1100 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
1104 for (i
= 0; i
< df_rd
->block_info_size
; i
++)
1106 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (i
);
1109 BITMAP_FREE (bb_info
->kill
);
1110 BITMAP_FREE (bb_info
->sparse_kill
);
1111 BITMAP_FREE (bb_info
->gen
);
1112 BITMAP_FREE (bb_info
->in
);
1113 BITMAP_FREE (bb_info
->out
);
1117 free_alloc_pool (df_rd
->block_pool
);
1118 BITMAP_FREE (problem_data
->sparse_invalidated_by_call
);
1119 BITMAP_FREE (problem_data
->dense_invalidated_by_call
);
1120 bitmap_obstack_release (&problem_data
->rd_bitmaps
);
1122 df_rd
->block_info_size
= 0;
1123 free (df_rd
->block_info
);
1124 free (df_rd
->problem_data
);
1130 /* Debugging info. */
1133 df_rd_start_dump (FILE *file
)
1135 struct df_rd_problem_data
*problem_data
1136 = (struct df_rd_problem_data
*) df_rd
->problem_data
;
1137 unsigned int m
= DF_REG_SIZE(df
);
1140 if (!df_rd
->block_info
)
1143 fprintf (file
, ";; Reaching defs:\n\n");
1145 fprintf (file
, " sparse invalidated \t");
1146 dump_bitmap (file
, problem_data
->sparse_invalidated_by_call
);
1147 fprintf (file
, " dense invalidated \t");
1148 dump_bitmap (file
, problem_data
->dense_invalidated_by_call
);
1150 for (regno
= 0; regno
< m
; regno
++)
1151 if (DF_DEFS_COUNT (regno
))
1152 fprintf (file
, "%d[%d,%d] ", regno
,
1153 DF_DEFS_BEGIN (regno
),
1154 DF_DEFS_COUNT (regno
));
1155 fprintf (file
, "\n");
1160 /* Debugging info at top of bb. */
1163 df_rd_top_dump (basic_block bb
, FILE *file
)
1165 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
1166 if (!bb_info
|| !bb_info
->in
)
1169 fprintf (file
, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info
->in
));
1170 dump_bitmap (file
, bb_info
->in
);
1171 fprintf (file
, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info
->gen
));
1172 dump_bitmap (file
, bb_info
->gen
);
1173 fprintf (file
, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info
->kill
));
1174 dump_bitmap (file
, bb_info
->kill
);
1178 /* Debugging info at top of bb. */
1181 df_rd_bottom_dump (basic_block bb
, FILE *file
)
1183 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb
->index
);
1184 if (!bb_info
|| !bb_info
->out
)
1187 fprintf (file
, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info
->out
));
1188 dump_bitmap (file
, bb_info
->out
);
1191 /* All of the information associated with every instance of the problem. */
1193 static struct df_problem problem_RD
=
1195 DF_RD
, /* Problem id. */
1196 DF_FORWARD
, /* Direction. */
1197 df_rd_alloc
, /* Allocate the problem specific data. */
1198 NULL
, /* Reset global information. */
1199 df_rd_free_bb_info
, /* Free basic block info. */
1200 df_rd_local_compute
, /* Local compute function. */
1201 df_rd_init_solution
, /* Init the solution specific data. */
1202 df_worklist_dataflow
, /* Worklist solver. */
1203 NULL
, /* Confluence operator 0. */
1204 df_rd_confluence_n
, /* Confluence operator n. */
1205 df_rd_transfer_function
, /* Transfer function. */
1206 NULL
, /* Finalize function. */
1207 df_rd_free
, /* Free all of the problem information. */
1208 df_rd_free
, /* Remove this problem from the stack of dataflow problems. */
1209 df_rd_start_dump
, /* Debugging. */
1210 df_rd_top_dump
, /* Debugging start block. */
1211 df_rd_bottom_dump
, /* Debugging end block. */
1212 NULL
, /* Incremental solution verify start. */
1213 NULL
, /* Incremental solution verify end. */
1214 NULL
, /* Dependent problem. */
1215 TV_DF_RD
, /* Timing variable. */
1216 true /* Reset blocks on dropping out of blocks_to_analyze. */
1221 /* Create a new DATAFLOW instance and add it to an existing instance
1222 of DF. The returned structure is what is used to get at the
1226 df_rd_add_problem (void)
1228 df_add_problem (&problem_RD
);
1233 /*----------------------------------------------------------------------------
1236 Find the locations in the function where any use of a pseudo can
1237 reach in the backwards direction. In and out bitvectors are built
1238 for each basic block. The regnum is used to index into these sets.
1239 See df.h for details.
1240 ----------------------------------------------------------------------------*/
1242 /* Private data used to verify the solution for this problem. */
1243 struct df_lr_problem_data
1250 /* Set basic block info. */
1253 df_lr_set_bb_info (unsigned int index
,
1254 struct df_lr_bb_info
*bb_info
)
1257 gcc_assert (index
< df_lr
->block_info_size
);
1258 df_lr
->block_info
[index
] = bb_info
;
1262 /* Free basic block info. */
1265 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1268 struct df_lr_bb_info
*bb_info
= (struct df_lr_bb_info
*) vbb_info
;
1271 BITMAP_FREE (bb_info
->use
);
1272 BITMAP_FREE (bb_info
->def
);
1273 if (bb_info
->in
== bb_info
->top
)
1274 bb_info
->top
= NULL
;
1277 BITMAP_FREE (bb_info
->top
);
1278 BITMAP_FREE (bb_info
->ause
);
1279 BITMAP_FREE (bb_info
->adef
);
1281 BITMAP_FREE (bb_info
->in
);
1282 BITMAP_FREE (bb_info
->out
);
1283 pool_free (df_lr
->block_pool
, bb_info
);
1288 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
1289 not touched unless the block is new. */
1292 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
1294 unsigned int bb_index
;
1297 if (!df_lr
->block_pool
)
1298 df_lr
->block_pool
= create_alloc_pool ("df_lr_block pool",
1299 sizeof (struct df_lr_bb_info
), 50);
1301 df_grow_bb_info (df_lr
);
1303 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1305 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1308 bitmap_clear (bb_info
->def
);
1309 bitmap_clear (bb_info
->use
);
1312 bitmap_clear (bb_info
->adef
);
1313 bitmap_clear (bb_info
->ause
);
1318 bb_info
= (struct df_lr_bb_info
*) pool_alloc (df_lr
->block_pool
);
1319 df_lr_set_bb_info (bb_index
, bb_info
);
1320 bb_info
->use
= BITMAP_ALLOC (NULL
);
1321 bb_info
->def
= BITMAP_ALLOC (NULL
);
1322 bb_info
->in
= BITMAP_ALLOC (NULL
);
1323 bb_info
->out
= BITMAP_ALLOC (NULL
);
1324 bb_info
->top
= bb_info
->in
;
1325 bb_info
->adef
= NULL
;
1326 bb_info
->ause
= NULL
;
1330 df_lr
->optional_p
= false;
1334 /* Reset the global solution for recalculation. */
1337 df_lr_reset (bitmap all_blocks
)
1339 unsigned int bb_index
;
1342 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1344 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1345 gcc_assert (bb_info
);
1346 bitmap_clear (bb_info
->in
);
1347 bitmap_clear (bb_info
->out
);
1348 bitmap_clear (bb_info
->top
);
1353 /* Compute local live register info for basic block BB. */
1356 df_lr_bb_local_compute (unsigned int bb_index
)
1358 basic_block bb
= BASIC_BLOCK (bb_index
);
1359 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1361 struct df_ref
**def_rec
;
1362 struct df_ref
**use_rec
;
1364 /* Process the registers set in an exception handler. */
1365 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1367 struct df_ref
*def
= *def_rec
;
1368 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
1370 unsigned int dregno
= DF_REF_REGNO (def
);
1371 bitmap_set_bit (bb_info
->def
, dregno
);
1372 bitmap_clear_bit (bb_info
->use
, dregno
);
1376 /* Process the hardware registers that are always live. */
1377 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
1379 struct df_ref
*use
= *use_rec
;
1380 /* Add use to set of uses in this BB. */
1381 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
1382 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
1385 FOR_BB_INSNS_REVERSE (bb
, insn
)
1387 unsigned int uid
= INSN_UID (insn
);
1394 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1396 struct df_ref
*def
= *def_rec
;
1397 unsigned int dregno
= DF_REF_REGNO (def
);
1399 if (DF_REF_FLAGS (def
) & DF_REF_MUST_CLOBBER
)
1401 if (dregno
>= FIRST_PSEUDO_REGISTER
1402 || !(SIBLING_CALL_P (insn
)
1403 && bitmap_bit_p (df
->exit_block_uses
, dregno
)
1404 && !refers_to_regno_p (dregno
, dregno
+1,
1405 current_function_return_rtx
,
1408 /* If the def is to only part of the reg, it does
1409 not kill the other defs that reach here. */
1410 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
1412 bitmap_set_bit (bb_info
->def
, dregno
);
1413 bitmap_clear_bit (bb_info
->use
, dregno
);
1418 /* This is the return value. */
1419 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
1421 bitmap_set_bit (bb_info
->def
, dregno
);
1422 bitmap_clear_bit (bb_info
->use
, dregno
);
1428 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1430 struct df_ref
*def
= *def_rec
;
1431 /* If the def is to only part of the reg, it does
1432 not kill the other defs that reach here. */
1433 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
1435 unsigned int dregno
= DF_REF_REGNO (def
);
1436 bitmap_set_bit (bb_info
->def
, dregno
);
1437 bitmap_clear_bit (bb_info
->use
, dregno
);
1442 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1444 struct df_ref
*use
= *use_rec
;
1445 /* Add use to set of uses in this BB. */
1446 bitmap_set_bit (bb_info
->use
, DF_REF_REGNO (use
));
1449 /* Process the registers set in an exception handler. */
1450 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
1452 struct df_ref
*def
= *def_rec
;
1453 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
1454 && (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))))
1456 unsigned int dregno
= DF_REF_REGNO (def
);
1457 if (bb_info
->adef
== NULL
)
1459 gcc_assert (bb_info
->ause
== NULL
);
1460 gcc_assert (bb_info
->top
== bb_info
->in
);
1461 bb_info
->adef
= BITMAP_ALLOC (NULL
);
1462 bb_info
->ause
= BITMAP_ALLOC (NULL
);
1463 bb_info
->top
= BITMAP_ALLOC (NULL
);
1465 bitmap_set_bit (bb_info
->adef
, dregno
);
1470 /* Process the uses that are live into an exception handler. */
1471 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
1473 struct df_ref
*use
= *use_rec
;
1474 /* Add use to set of uses in this BB. */
1475 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
1477 if (bb_info
->adef
== NULL
)
1479 gcc_assert (bb_info
->ause
== NULL
);
1480 gcc_assert (bb_info
->top
== bb_info
->in
);
1481 bb_info
->adef
= BITMAP_ALLOC (NULL
);
1482 bb_info
->ause
= BITMAP_ALLOC (NULL
);
1483 bb_info
->top
= BITMAP_ALLOC (NULL
);
1485 bitmap_set_bit (bb_info
->ause
, DF_REF_REGNO (use
));
1490 /* If the df_live problem is not defined, such as at -O0 and -O1, we
1491 still need to keep the luids up to date. This is normally done
1492 in the df_live problem since this problem has a forwards
1495 df_recompute_luids (bb
);
1499 /* Compute local live register info for each basic block within BLOCKS. */
1502 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
1504 unsigned int bb_index
;
1507 bitmap_clear (df
->hardware_regs_used
);
1509 /* The all-important stack pointer must always be live. */
1510 bitmap_set_bit (df
->hardware_regs_used
, STACK_POINTER_REGNUM
);
1512 /* Before reload, there are a few registers that must be forced
1513 live everywhere -- which might not already be the case for
1514 blocks within infinite loops. */
1515 if (!reload_completed
)
1517 /* Any reference to any pseudo before reload is a potential
1518 reference of the frame pointer. */
1519 bitmap_set_bit (df
->hardware_regs_used
, FRAME_POINTER_REGNUM
);
1521 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1522 /* Pseudos with argument area equivalences may require
1523 reloading via the argument pointer. */
1524 if (fixed_regs
[ARG_POINTER_REGNUM
])
1525 bitmap_set_bit (df
->hardware_regs_used
, ARG_POINTER_REGNUM
);
1528 /* Any constant, or pseudo with constant equivalences, may
1529 require reloading from memory using the pic register. */
1530 if ((unsigned) PIC_OFFSET_TABLE_REGNUM
!= INVALID_REGNUM
1531 && fixed_regs
[PIC_OFFSET_TABLE_REGNUM
])
1532 bitmap_set_bit (df
->hardware_regs_used
, PIC_OFFSET_TABLE_REGNUM
);
1535 EXECUTE_IF_SET_IN_BITMAP (df_lr
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
1537 if (bb_index
== EXIT_BLOCK
)
1539 /* The exit block is special for this problem and its bits are
1540 computed from thin air. */
1541 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (EXIT_BLOCK
);
1542 bitmap_copy (bb_info
->use
, df
->exit_block_uses
);
1545 df_lr_bb_local_compute (bb_index
);
1548 bitmap_clear (df_lr
->out_of_date_transfer_functions
);
1552 /* Initialize the solution vectors. */
1555 df_lr_init (bitmap all_blocks
)
1557 unsigned int bb_index
;
1560 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
1562 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1563 bitmap_copy (bb_info
->in
, bb_info
->use
);
1564 bitmap_clear (bb_info
->out
);
1569 /* Confluence function that processes infinite loops. This might be a
1570 noreturn function that throws. And even if it isn't, getting the
1571 unwind info right helps debugging. */
1573 df_lr_confluence_0 (basic_block bb
)
1575 bitmap op1
= df_lr_get_bb_info (bb
->index
)->out
;
1576 if (bb
!= EXIT_BLOCK_PTR
)
1577 bitmap_copy (op1
, df
->hardware_regs_used
);
1581 /* Confluence function that ignores fake edges. */
1584 df_lr_confluence_n (edge e
)
1586 bitmap op1
= df_lr_get_bb_info (e
->src
->index
)->out
;
1587 bitmap op2
= df_lr_get_bb_info (e
->dest
->index
)->in
;
1589 /* Call-clobbered registers die across exception and call edges. */
1590 /* ??? Abnormal call edges ignored for the moment, as this gets
1591 confused by sibling call edges, which crashes reg-stack. */
1592 if (e
->flags
& EDGE_EH
)
1593 bitmap_ior_and_compl_into (op1
, op2
, df_invalidated_by_call
);
1595 bitmap_ior_into (op1
, op2
);
1597 bitmap_ior_into (op1
, df
->hardware_regs_used
);
1601 /* Transfer function. */
1604 df_lr_transfer_function (int bb_index
)
1606 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
1607 bitmap in
= bb_info
->in
;
1608 bitmap out
= bb_info
->out
;
1609 bitmap use
= bb_info
->use
;
1610 bitmap def
= bb_info
->def
;
1611 bitmap top
= bb_info
->top
;
1612 bitmap ause
= bb_info
->ause
;
1613 bitmap adef
= bb_info
->adef
;
1616 changed
= bitmap_ior_and_compl (top
, use
, out
, def
);
1619 gcc_assert (ause
&& adef
);
1620 changed
|= bitmap_ior_and_compl (in
, ause
, top
, adef
);
1627 /* Run the fast dce as a side effect of building LR. */
1630 df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED
)
1632 if (df
->changeable_flags
& DF_LR_RUN_DCE
)
1635 if (df_lr
->problem_data
&& df_lr
->solutions_dirty
)
1637 /* If we are here, then it is because we are both verifying
1638 the solution and the dce changed the function. In that case
1639 the verification info built will be wrong. So we leave the
1640 dirty flag true so that the verifier will skip the checking
1641 part and just clean up.*/
1642 df_lr
->solutions_dirty
= true;
1645 df_lr
->solutions_dirty
= false;
1648 df_lr
->solutions_dirty
= false;
1652 /* Free all storage associated with the problem. */
1657 if (df_lr
->block_info
)
1660 for (i
= 0; i
< df_lr
->block_info_size
; i
++)
1662 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (i
);
1665 BITMAP_FREE (bb_info
->use
);
1666 BITMAP_FREE (bb_info
->def
);
1667 if (bb_info
->in
== bb_info
->top
)
1668 bb_info
->top
= NULL
;
1671 BITMAP_FREE (bb_info
->top
);
1672 BITMAP_FREE (bb_info
->ause
);
1673 BITMAP_FREE (bb_info
->adef
);
1675 BITMAP_FREE (bb_info
->in
);
1676 BITMAP_FREE (bb_info
->out
);
1679 free_alloc_pool (df_lr
->block_pool
);
1681 df_lr
->block_info_size
= 0;
1682 free (df_lr
->block_info
);
1685 BITMAP_FREE (df_lr
->out_of_date_transfer_functions
);
1690 /* Debugging info at top of bb. */
1693 df_lr_top_dump (basic_block bb
, FILE *file
)
1695 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1696 struct df_lr_problem_data
*problem_data
;
1697 if (!bb_info
|| !bb_info
->in
)
1700 fprintf (file
, ";; lr in \t");
1701 df_print_regset (file
, bb_info
->in
);
1702 if (df_lr
->problem_data
)
1704 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1705 fprintf (file
, ";; old in \t");
1706 df_print_regset (file
, problem_data
->in
[bb
->index
]);
1708 fprintf (file
, ";; lr use \t");
1709 df_print_regset (file
, bb_info
->use
);
1710 fprintf (file
, ";; lr def \t");
1711 df_print_regset (file
, bb_info
->def
);
1715 /* Debugging info at bottom of bb. */
1718 df_lr_bottom_dump (basic_block bb
, FILE *file
)
1720 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1721 struct df_lr_problem_data
*problem_data
;
1722 if (!bb_info
|| !bb_info
->out
)
1725 fprintf (file
, ";; lr out \t");
1726 df_print_regset (file
, bb_info
->out
);
1727 if (df_lr
->problem_data
)
1729 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1730 fprintf (file
, ";; old out \t");
1731 df_print_regset (file
, problem_data
->out
[bb
->index
]);
1736 /* Build the datastructure to verify that the solution to the dataflow
1737 equations is not dirty. */
1740 df_lr_verify_solution_start (void)
1743 struct df_lr_problem_data
*problem_data
;
1744 if (df_lr
->solutions_dirty
)
1746 df_lr
->problem_data
= NULL
;
1750 /* Set it true so that the solution is recomputed. */
1751 df_lr
->solutions_dirty
= true;
1753 problem_data
= XNEW (struct df_lr_problem_data
);
1754 df_lr
->problem_data
= problem_data
;
1755 problem_data
->in
= XNEWVEC (bitmap
, last_basic_block
);
1756 problem_data
->out
= XNEWVEC (bitmap
, last_basic_block
);
1760 problem_data
->in
[bb
->index
] = BITMAP_ALLOC (NULL
);
1761 problem_data
->out
[bb
->index
] = BITMAP_ALLOC (NULL
);
1762 bitmap_copy (problem_data
->in
[bb
->index
], DF_LR_IN (bb
));
1763 bitmap_copy (problem_data
->out
[bb
->index
], DF_LR_OUT (bb
));
1768 /* Compare the saved datastructure and the new solution to the dataflow
1772 df_lr_verify_solution_end (void)
1774 struct df_lr_problem_data
*problem_data
;
1777 if (df_lr
->problem_data
== NULL
)
1780 problem_data
= (struct df_lr_problem_data
*)df_lr
->problem_data
;
1782 if (df_lr
->solutions_dirty
)
1783 /* Do not check if the solution is still dirty. See the comment
1784 in df_lr_local_finalize for details. */
1785 df_lr
->solutions_dirty
= false;
1789 if ((!bitmap_equal_p (problem_data
->in
[bb
->index
], DF_LR_IN (bb
)))
1790 || (!bitmap_equal_p (problem_data
->out
[bb
->index
], DF_LR_OUT (bb
))))
1792 /*df_dump (stderr);*/
1797 /* Cannot delete them immediately because you may want to dump them
1798 if the comparison fails. */
1801 BITMAP_FREE (problem_data
->in
[bb
->index
]);
1802 BITMAP_FREE (problem_data
->out
[bb
->index
]);
1805 free (problem_data
->in
);
1806 free (problem_data
->out
);
1807 free (problem_data
);
1808 df_lr
->problem_data
= NULL
;
1812 /* All of the information associated with every instance of the problem. */
1814 static struct df_problem problem_LR
=
1816 DF_LR
, /* Problem id. */
1817 DF_BACKWARD
, /* Direction. */
1818 df_lr_alloc
, /* Allocate the problem specific data. */
1819 df_lr_reset
, /* Reset global information. */
1820 df_lr_free_bb_info
, /* Free basic block info. */
1821 df_lr_local_compute
, /* Local compute function. */
1822 df_lr_init
, /* Init the solution specific data. */
1823 df_worklist_dataflow
, /* Worklist solver. */
1824 df_lr_confluence_0
, /* Confluence operator 0. */
1825 df_lr_confluence_n
, /* Confluence operator n. */
1826 df_lr_transfer_function
, /* Transfer function. */
1827 df_lr_local_finalize
, /* Finalize function. */
1828 df_lr_free
, /* Free all of the problem information. */
1829 NULL
, /* Remove this problem from the stack of dataflow problems. */
1830 NULL
, /* Debugging. */
1831 df_lr_top_dump
, /* Debugging start block. */
1832 df_lr_bottom_dump
, /* Debugging end block. */
1833 df_lr_verify_solution_start
,/* Incremental solution verify start. */
1834 df_lr_verify_solution_end
, /* Incremental solution verify end. */
1835 NULL
, /* Dependent problem. */
1836 TV_DF_LR
, /* Timing variable. */
1837 false /* Reset blocks on dropping out of blocks_to_analyze. */
1841 /* Create a new DATAFLOW instance and add it to an existing instance
1842 of DF. The returned structure is what is used to get at the
1846 df_lr_add_problem (void)
1848 df_add_problem (&problem_LR
);
1849 /* These will be initialized when df_scan_blocks processes each
1851 df_lr
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
1855 /* Verify that all of the lr related info is consistent and
1859 df_lr_verify_transfer_functions (void)
1872 saved_def
= BITMAP_ALLOC (NULL
);
1873 saved_use
= BITMAP_ALLOC (NULL
);
1874 saved_adef
= BITMAP_ALLOC (NULL
);
1875 saved_ause
= BITMAP_ALLOC (NULL
);
1876 all_blocks
= BITMAP_ALLOC (NULL
);
1880 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb
->index
);
1881 bitmap_set_bit (all_blocks
, bb
->index
);
1885 /* Make a copy of the transfer functions and then compute
1886 new ones to see if the transfer functions have
1888 if (!bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1891 bitmap_copy (saved_def
, bb_info
->def
);
1892 bitmap_copy (saved_use
, bb_info
->use
);
1893 bitmap_clear (bb_info
->def
);
1894 bitmap_clear (bb_info
->use
);
1899 bitmap_copy (saved_adef
, bb_info
->adef
);
1900 bitmap_copy (saved_ause
, bb_info
->ause
);
1901 bitmap_clear (bb_info
->adef
);
1902 bitmap_clear (bb_info
->ause
);
1907 df_lr_bb_local_compute (bb
->index
);
1908 gcc_assert (bitmap_equal_p (saved_def
, bb_info
->def
));
1909 gcc_assert (bitmap_equal_p (saved_use
, bb_info
->use
));
1913 gcc_assert (bb_info
->adef
);
1914 gcc_assert (bb_info
->ause
);
1915 gcc_assert (bitmap_equal_p (saved_adef
, bb_info
->adef
));
1916 gcc_assert (bitmap_equal_p (saved_ause
, bb_info
->ause
));
1920 gcc_assert (!bb_info
->adef
);
1921 gcc_assert (!bb_info
->ause
);
1927 /* If we do not have basic block info, the block must be in
1928 the list of dirty blocks or else some one has added a
1929 block behind our backs. */
1930 gcc_assert (bitmap_bit_p (df_lr
->out_of_date_transfer_functions
,
1933 /* Make sure no one created a block without following
1935 gcc_assert (df_scan_get_bb_info (bb
->index
));
1938 /* Make sure there are no dirty bits in blocks that have been deleted. */
1939 gcc_assert (!bitmap_intersect_compl_p (df_lr
->out_of_date_transfer_functions
,
1942 BITMAP_FREE (saved_def
);
1943 BITMAP_FREE (saved_use
);
1944 BITMAP_FREE (saved_adef
);
1945 BITMAP_FREE (saved_ause
);
1946 BITMAP_FREE (all_blocks
);
1951 /*----------------------------------------------------------------------------
1952 COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
1954 First find the set of uses for registers that are reachable from
1955 the entry block without passing thru a definition. In and out
1956 bitvectors are built for each basic block. The regnum is used to
1957 index into these sets. See df.h for details.
1959 Then the in and out sets here are the anded results of the in and
1960 out sets from the lr and ur
1962 ----------------------------------------------------------------------------*/
1964 /* Private data used to verify the solution for this problem. */
1965 struct df_live_problem_data
1972 /* Set basic block info. */
1975 df_live_set_bb_info (unsigned int index
,
1976 struct df_live_bb_info
*bb_info
)
1978 gcc_assert (df_live
);
1979 gcc_assert (index
< df_live
->block_info_size
);
1980 df_live
->block_info
[index
] = bb_info
;
1984 /* Free basic block info. */
1987 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
1990 struct df_live_bb_info
*bb_info
= (struct df_live_bb_info
*) vbb_info
;
1993 BITMAP_FREE (bb_info
->gen
);
1994 BITMAP_FREE (bb_info
->kill
);
1995 BITMAP_FREE (bb_info
->in
);
1996 BITMAP_FREE (bb_info
->out
);
1997 pool_free (df_live
->block_pool
, bb_info
);
2002 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
2003 not touched unless the block is new. */
2006 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
2008 unsigned int bb_index
;
2011 if (!df_live
->block_pool
)
2012 df_live
->block_pool
= create_alloc_pool ("df_live_block pool",
2013 sizeof (struct df_live_bb_info
), 100);
2015 df_grow_bb_info (df_live
);
2017 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
2019 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
2022 bitmap_clear (bb_info
->kill
);
2023 bitmap_clear (bb_info
->gen
);
2027 bb_info
= (struct df_live_bb_info
*) pool_alloc (df_live
->block_pool
);
2028 df_live_set_bb_info (bb_index
, bb_info
);
2029 bb_info
->kill
= BITMAP_ALLOC (NULL
);
2030 bb_info
->gen
= BITMAP_ALLOC (NULL
);
2031 bb_info
->in
= BITMAP_ALLOC (NULL
);
2032 bb_info
->out
= BITMAP_ALLOC (NULL
);
2035 df_live
->optional_p
= (optimize
<= 1);
2039 /* Reset the global solution for recalculation. */
2042 df_live_reset (bitmap all_blocks
)
2044 unsigned int bb_index
;
2047 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2049 struct df_lr_bb_info
*bb_info
= df_lr_get_bb_info (bb_index
);
2050 gcc_assert (bb_info
);
2051 bitmap_clear (bb_info
->in
);
2052 bitmap_clear (bb_info
->out
);
2057 /* Compute local uninitialized register info for basic block BB. */
2060 df_live_bb_local_compute (unsigned int bb_index
)
2062 basic_block bb
= BASIC_BLOCK (bb_index
);
2063 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
2065 struct df_ref
**def_rec
;
2068 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2070 struct df_ref
*def
= *def_rec
;
2071 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2072 bitmap_set_bit (bb_info
->gen
, DF_REF_REGNO (def
));
2075 FOR_BB_INSNS (bb
, insn
)
2077 unsigned int uid
= INSN_UID (insn
);
2078 struct df_insn_info
*insn_info
= DF_INSN_UID_GET (uid
);
2080 /* Inserting labels does not always trigger the incremental
2084 gcc_assert (!INSN_P (insn
));
2085 df_insn_create_insn_record (insn
);
2088 DF_INSN_LUID (insn
) = luid
;
2093 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2095 struct df_ref
*def
= *def_rec
;
2096 unsigned int regno
= DF_REF_REGNO (def
);
2098 if (DF_REF_FLAGS_IS_SET (def
,
2099 DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
2100 /* All partial or conditional def
2101 seen are included in the gen set. */
2102 bitmap_set_bit (bb_info
->gen
, regno
);
2103 else if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
2104 /* Only must clobbers for the entire reg destroy the
2106 bitmap_set_bit (bb_info
->kill
, regno
);
2107 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2108 bitmap_set_bit (bb_info
->gen
, regno
);
2112 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2114 struct df_ref
*def
= *def_rec
;
2115 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
2116 bitmap_set_bit (bb_info
->gen
, DF_REF_REGNO (def
));
2121 /* Compute local uninitialized register info. */
2124 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED
)
2126 unsigned int bb_index
;
2129 df_grow_insn_info ();
2131 EXECUTE_IF_SET_IN_BITMAP (df_live
->out_of_date_transfer_functions
,
2134 df_live_bb_local_compute (bb_index
);
2137 bitmap_clear (df_live
->out_of_date_transfer_functions
);
2141 /* Initialize the solution vectors. */
2144 df_live_init (bitmap all_blocks
)
2146 unsigned int bb_index
;
2149 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2151 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
2153 bitmap_copy (bb_info
->out
, bb_info
->gen
);
2154 bitmap_clear (bb_info
->in
);
2158 /* Confluence function that ignores fake edges. */
2161 df_live_confluence_n (edge e
)
2163 bitmap op1
= df_live_get_bb_info (e
->dest
->index
)->in
;
2164 bitmap op2
= df_live_get_bb_info (e
->src
->index
)->out
;
2166 if (e
->flags
& EDGE_FAKE
)
2169 bitmap_ior_into (op1
, op2
);
2173 /* Transfer function. */
2176 df_live_transfer_function (int bb_index
)
2178 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb_index
);
2179 bitmap in
= bb_info
->in
;
2180 bitmap out
= bb_info
->out
;
2181 bitmap gen
= bb_info
->gen
;
2182 bitmap kill
= bb_info
->kill
;
2184 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
2188 /* And the LR and UR info to produce the LIVE info. */
2191 df_live_local_finalize (bitmap all_blocks
)
2194 if (df_live
->solutions_dirty
)
2197 unsigned int bb_index
;
2199 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2201 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
2202 struct df_live_bb_info
*bb_live_info
= df_live_get_bb_info (bb_index
);
2204 /* No register may reach a location where it is not used. Thus
2205 we trim the rr result to the places where it is used. */
2206 bitmap_and_into (bb_live_info
->in
, bb_lr_info
->in
);
2207 bitmap_and_into (bb_live_info
->out
, bb_lr_info
->out
);
2210 df_live
->solutions_dirty
= false;
2215 /* Free all storage associated with the problem. */
2220 if (df_live
->block_info
)
2224 for (i
= 0; i
< df_live
->block_info_size
; i
++)
2226 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (i
);
2229 BITMAP_FREE (bb_info
->gen
);
2230 BITMAP_FREE (bb_info
->kill
);
2231 BITMAP_FREE (bb_info
->in
);
2232 BITMAP_FREE (bb_info
->out
);
2236 free_alloc_pool (df_live
->block_pool
);
2237 df_live
->block_info_size
= 0;
2238 free (df_live
->block_info
);
2240 BITMAP_FREE (df_live
->out_of_date_transfer_functions
);
2245 /* Debugging info at top of bb. */
2248 df_live_top_dump (basic_block bb
, FILE *file
)
2250 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
2251 struct df_live_problem_data
*problem_data
;
2253 if (!bb_info
|| !bb_info
->in
)
2256 fprintf (file
, ";; live in \t");
2257 df_print_regset (file
, bb_info
->in
);
2258 if (df_live
->problem_data
)
2260 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
2261 fprintf (file
, ";; old in \t");
2262 df_print_regset (file
, problem_data
->in
[bb
->index
]);
2264 fprintf (file
, ";; live gen \t");
2265 df_print_regset (file
, bb_info
->gen
);
2266 fprintf (file
, ";; live kill\t");
2267 df_print_regset (file
, bb_info
->kill
);
2271 /* Debugging info at bottom of bb. */
2274 df_live_bottom_dump (basic_block bb
, FILE *file
)
2276 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
2277 struct df_live_problem_data
*problem_data
;
2279 if (!bb_info
|| !bb_info
->out
)
2282 fprintf (file
, ";; live out \t");
2283 df_print_regset (file
, bb_info
->out
);
2284 if (df_live
->problem_data
)
2286 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
2287 fprintf (file
, ";; old out \t");
2288 df_print_regset (file
, problem_data
->out
[bb
->index
]);
2293 /* Build the datastructure to verify that the solution to the dataflow
2294 equations is not dirty. */
2297 df_live_verify_solution_start (void)
2300 struct df_live_problem_data
*problem_data
;
2301 if (df_live
->solutions_dirty
)
2303 df_live
->problem_data
= NULL
;
2307 /* Set it true so that the solution is recomputed. */
2308 df_live
->solutions_dirty
= true;
2310 problem_data
= XNEW (struct df_live_problem_data
);
2311 df_live
->problem_data
= problem_data
;
2312 problem_data
->in
= XNEWVEC (bitmap
, last_basic_block
);
2313 problem_data
->out
= XNEWVEC (bitmap
, last_basic_block
);
2317 problem_data
->in
[bb
->index
] = BITMAP_ALLOC (NULL
);
2318 problem_data
->out
[bb
->index
] = BITMAP_ALLOC (NULL
);
2319 bitmap_copy (problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
));
2320 bitmap_copy (problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
));
2325 /* Compare the saved datastructure and the new solution to the dataflow
2329 df_live_verify_solution_end (void)
2331 struct df_live_problem_data
*problem_data
;
2334 if (df_live
->problem_data
== NULL
)
2337 problem_data
= (struct df_live_problem_data
*)df_live
->problem_data
;
2341 if ((!bitmap_equal_p (problem_data
->in
[bb
->index
], DF_LIVE_IN (bb
)))
2342 || (!bitmap_equal_p (problem_data
->out
[bb
->index
], DF_LIVE_OUT (bb
))))
2344 /*df_dump (stderr);*/
2349 /* Cannot delete them immediately because you may want to dump them
2350 if the comparison fails. */
2353 BITMAP_FREE (problem_data
->in
[bb
->index
]);
2354 BITMAP_FREE (problem_data
->out
[bb
->index
]);
2357 free (problem_data
->in
);
2358 free (problem_data
->out
);
2359 free (problem_data
);
2360 df_live
->problem_data
= NULL
;
2364 /* All of the information associated with every instance of the problem. */
2366 static struct df_problem problem_LIVE
=
2368 DF_LIVE
, /* Problem id. */
2369 DF_FORWARD
, /* Direction. */
2370 df_live_alloc
, /* Allocate the problem specific data. */
2371 df_live_reset
, /* Reset global information. */
2372 df_live_free_bb_info
, /* Free basic block info. */
2373 df_live_local_compute
, /* Local compute function. */
2374 df_live_init
, /* Init the solution specific data. */
2375 df_worklist_dataflow
, /* Worklist solver. */
2376 NULL
, /* Confluence operator 0. */
2377 df_live_confluence_n
, /* Confluence operator n. */
2378 df_live_transfer_function
, /* Transfer function. */
2379 df_live_local_finalize
, /* Finalize function. */
2380 df_live_free
, /* Free all of the problem information. */
2381 df_live_free
, /* Remove this problem from the stack of dataflow problems. */
2382 NULL
, /* Debugging. */
2383 df_live_top_dump
, /* Debugging start block. */
2384 df_live_bottom_dump
, /* Debugging end block. */
2385 df_live_verify_solution_start
,/* Incremental solution verify start. */
2386 df_live_verify_solution_end
, /* Incremental solution verify end. */
2387 &problem_LR
, /* Dependent problem. */
2388 TV_DF_LIVE
, /* Timing variable. */
2389 false /* Reset blocks on dropping out of blocks_to_analyze. */
2393 /* Create a new DATAFLOW instance and add it to an existing instance
2394 of DF. The returned structure is what is used to get at the
2398 df_live_add_problem (void)
2400 df_add_problem (&problem_LIVE
);
2401 /* These will be initialized when df_scan_blocks processes each
2403 df_live
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
2407 /* Set all of the blocks as dirty. This needs to be done if this
2408 problem is added after all of the insns have been scanned. */
2411 df_live_set_all_dirty (void)
2415 bitmap_set_bit (df_live
->out_of_date_transfer_functions
,
2420 /* Verify that all of the lr related info is consistent and
2424 df_live_verify_transfer_functions (void)
2434 saved_gen
= BITMAP_ALLOC (NULL
);
2435 saved_kill
= BITMAP_ALLOC (NULL
);
2436 all_blocks
= BITMAP_ALLOC (NULL
);
2438 df_grow_insn_info ();
2442 struct df_live_bb_info
*bb_info
= df_live_get_bb_info (bb
->index
);
2443 bitmap_set_bit (all_blocks
, bb
->index
);
2447 /* Make a copy of the transfer functions and then compute
2448 new ones to see if the transfer functions have
2450 if (!bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
2453 bitmap_copy (saved_gen
, bb_info
->gen
);
2454 bitmap_copy (saved_kill
, bb_info
->kill
);
2455 bitmap_clear (bb_info
->gen
);
2456 bitmap_clear (bb_info
->kill
);
2458 df_live_bb_local_compute (bb
->index
);
2459 gcc_assert (bitmap_equal_p (saved_gen
, bb_info
->gen
));
2460 gcc_assert (bitmap_equal_p (saved_kill
, bb_info
->kill
));
2465 /* If we do not have basic block info, the block must be in
2466 the list of dirty blocks or else some one has added a
2467 block behind our backs. */
2468 gcc_assert (bitmap_bit_p (df_live
->out_of_date_transfer_functions
,
2471 /* Make sure no one created a block without following
2473 gcc_assert (df_scan_get_bb_info (bb
->index
));
2476 /* Make sure there are no dirty bits in blocks that have been deleted. */
2477 gcc_assert (!bitmap_intersect_compl_p (df_live
->out_of_date_transfer_functions
,
2479 BITMAP_FREE (saved_gen
);
2480 BITMAP_FREE (saved_kill
);
2481 BITMAP_FREE (all_blocks
);
2486 /*----------------------------------------------------------------------------
2487 UNINITIALIZED REGISTERS WITH EARLYCLOBBER
2489 Find the set of uses for registers that are reachable from the entry
2490 block without passing thru a definition. In and out bitvectors are built
2491 for each basic block. The regnum is used to index into these sets.
2492 See df.h for details.
2494 This is a variant of the UR problem above that has a lot of special
2495 features just for the register allocation phase. This problem
2496 should go away if someone would fix the interference graph.
2498 ----------------------------------------------------------------------------*/
2500 /* Private data used to compute the solution for this problem. These
2501 data structures are not accessible outside of this module. */
2502 struct df_urec_problem_data
2504 bool earlyclobbers_found
; /* True if any instruction contains an
2507 bitmap stack_regs
; /* Registers that may be allocated to a STACK_REGS. */
2512 /* Set basic block info. */
2515 df_urec_set_bb_info (unsigned int index
,
2516 struct df_urec_bb_info
*bb_info
)
2518 gcc_assert (df_urec
);
2519 gcc_assert (index
< df_urec
->block_info_size
);
2520 df_urec
->block_info
[index
] = bb_info
;
2524 /* Free basic block info. */
2527 df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED
,
2530 struct df_urec_bb_info
*bb_info
= (struct df_urec_bb_info
*) vbb_info
;
2533 BITMAP_FREE (bb_info
->gen
);
2534 BITMAP_FREE (bb_info
->kill
);
2535 BITMAP_FREE (bb_info
->in
);
2536 BITMAP_FREE (bb_info
->out
);
2537 BITMAP_FREE (bb_info
->earlyclobber
);
2538 pool_free (df_urec
->block_pool
, bb_info
);
2543 /* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
2544 not touched unless the block is new. */
2547 df_urec_alloc (bitmap all_blocks
)
2550 unsigned int bb_index
;
2552 struct df_urec_problem_data
*problem_data
2553 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2555 if (!df_urec
->block_pool
)
2556 df_urec
->block_pool
= create_alloc_pool ("df_urec_block pool",
2557 sizeof (struct df_urec_bb_info
), 50);
2559 if (!df_urec
->problem_data
)
2561 problem_data
= XNEW (struct df_urec_problem_data
);
2562 df_urec
->problem_data
= problem_data
;
2564 problem_data
->earlyclobbers_found
= false;
2566 df_grow_bb_info (df_urec
);
2568 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2570 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2573 bitmap_clear (bb_info
->kill
);
2574 bitmap_clear (bb_info
->gen
);
2575 bitmap_clear (bb_info
->earlyclobber
);
2579 bb_info
= (struct df_urec_bb_info
*) pool_alloc (df_urec
->block_pool
);
2580 df_urec_set_bb_info (bb_index
, bb_info
);
2581 bb_info
->kill
= BITMAP_ALLOC (NULL
);
2582 bb_info
->gen
= BITMAP_ALLOC (NULL
);
2583 bb_info
->in
= BITMAP_ALLOC (NULL
);
2584 bb_info
->out
= BITMAP_ALLOC (NULL
);
2585 bb_info
->top
= BITMAP_ALLOC (NULL
);
2586 bb_info
->earlyclobber
= BITMAP_ALLOC (NULL
);
2589 df_urec
->optional_p
= true;
2593 /* The function modifies local info for register REG being changed in
2594 SETTER. DATA is used to pass the current basic block info. */
2597 df_urec_mark_reg_change (rtx reg
, const_rtx setter
, void *data
)
2602 struct df_urec_bb_info
*bb_info
= (struct df_urec_bb_info
*) data
;
2604 if (GET_CODE (reg
) == SUBREG
)
2605 reg
= SUBREG_REG (reg
);
2610 regno
= REGNO (reg
);
2611 if (regno
< FIRST_PSEUDO_REGISTER
)
2613 endregno
= END_HARD_REGNO (reg
);
2614 for (i
= regno
; i
< endregno
; i
++)
2616 bitmap_set_bit (bb_info
->kill
, i
);
2618 if (GET_CODE (setter
) != CLOBBER
)
2619 bitmap_set_bit (bb_info
->gen
, i
);
2621 bitmap_clear_bit (bb_info
->gen
, i
);
2626 bitmap_set_bit (bb_info
->kill
, regno
);
2628 if (GET_CODE (setter
) != CLOBBER
)
2629 bitmap_set_bit (bb_info
->gen
, regno
);
2631 bitmap_clear_bit (bb_info
->gen
, regno
);
2634 /* Classes of registers which could be early clobbered in the current
2637 static VEC(int,heap
) *earlyclobber_regclass
;
2639 /* This function finds and stores register classes that could be early
2640 clobbered in INSN. If any earlyclobber classes are found, the function
2641 returns TRUE, in all other cases it returns FALSE. */
2644 df_urec_check_earlyclobber (rtx insn
)
2649 extract_insn (insn
);
2651 VEC_truncate (int, earlyclobber_regclass
, 0);
2652 for (opno
= 0; opno
< recog_data
.n_operands
; opno
++)
2657 enum reg_class
class;
2658 const char *p
= recog_data
.constraints
[opno
];
2667 case '=': case '+': case '?':
2670 case 'm': case '<': case '>': case 'V': case 'o':
2671 case 'E': case 'F': case 'G': case 'H':
2672 case 's': case 'i': case 'n':
2673 case 'I': case 'J': case 'K': case 'L':
2674 case 'M': case 'N': case 'O': case 'P':
2676 case '0': case '1': case '2': case '3': case '4':
2677 case '5': case '6': case '7': case '8': case '9':
2678 /* These don't say anything we care about. */
2686 if (amp_p
&& class != NO_REGS
)
2692 VEC_iterate (int, earlyclobber_regclass
, i
, rc
);
2695 if (rc
== (int) class)
2699 /* We use VEC_quick_push here because
2700 earlyclobber_regclass holds no more than
2701 N_REG_CLASSES elements. */
2702 VEC_quick_push (int, earlyclobber_regclass
, (int) class);
2712 class = GENERAL_REGS
;
2716 class = REG_CLASS_FROM_CONSTRAINT (c
, p
);
2721 p
+= CONSTRAINT_LEN (c
, p
);
2728 /* The function checks that pseudo-register *X has a class
2729 intersecting with the class of pseudo-register could be early
2730 clobbered in the same insn.
2732 This function is a no-op if earlyclobber_regclass is empty.
2734 Reload can assign the same hard register to uninitialized
2735 pseudo-register and early clobbered pseudo-register in an insn if
2736 the pseudo-register is used first time in given BB and not lived at
2737 the BB start. To prevent this we don't change life information for
2738 such pseudo-registers. */
2741 df_urec_mark_reg_use_for_earlyclobber (rtx
*x
, void *data
)
2743 enum reg_class pref_class
, alt_class
;
2745 struct df_urec_bb_info
*bb_info
= (struct df_urec_bb_info
*) data
;
2747 if (REG_P (*x
) && REGNO (*x
) >= FIRST_PSEUDO_REGISTER
)
2752 if (bitmap_bit_p (bb_info
->kill
, regno
)
2753 || bitmap_bit_p (bb_info
->gen
, regno
))
2755 pref_class
= reg_preferred_class (regno
);
2756 alt_class
= reg_alternate_class (regno
);
2757 for (i
= 0; VEC_iterate (int, earlyclobber_regclass
, i
, rc
); i
++)
2759 if (reg_classes_intersect_p (rc
, pref_class
)
2761 && reg_classes_intersect_p (rc
, alt_class
)))
2763 bitmap_set_bit (bb_info
->earlyclobber
, regno
);
2771 /* The function processes all pseudo-registers in *X with the aid of
2772 previous function. */
2775 df_urec_mark_reg_use_for_earlyclobber_1 (rtx
*x
, void *data
)
2777 for_each_rtx (x
, df_urec_mark_reg_use_for_earlyclobber
, data
);
2781 /* Compute local uninitialized register info for basic block BB. */
2784 df_urec_bb_local_compute (unsigned int bb_index
)
2786 basic_block bb
= BASIC_BLOCK (bb_index
);
2787 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2789 struct df_ref
**def_rec
;
2791 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2793 struct df_ref
*def
= *def_rec
;
2794 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
2796 unsigned int regno
= DF_REF_REGNO (def
);
2797 bitmap_set_bit (bb_info
->gen
, regno
);
2801 FOR_BB_INSNS (bb
, insn
)
2805 note_stores (PATTERN (insn
), df_urec_mark_reg_change
, bb_info
);
2806 if (df_urec_check_earlyclobber (insn
))
2808 struct df_urec_problem_data
*problem_data
2809 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2810 problem_data
->earlyclobbers_found
= true;
2811 note_uses (&PATTERN (insn
),
2812 df_urec_mark_reg_use_for_earlyclobber_1
, bb_info
);
2817 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
2819 struct df_ref
*def
= *def_rec
;
2820 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
2822 unsigned int regno
= DF_REF_REGNO (def
);
2823 bitmap_set_bit (bb_info
->gen
, regno
);
2829 /* Compute local uninitialized register info. */
2832 df_urec_local_compute (bitmap all_blocks
)
2834 unsigned int bb_index
;
2838 HARD_REG_SET stack_hard_regs
, used
;
2839 struct df_urec_problem_data
*problem_data
2840 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2842 /* Any register that MAY be allocated to a register stack (like the
2843 387) is treated poorly. Each such register is marked as being
2844 live everywhere. This keeps the register allocator and the
2845 subsequent passes from doing anything useful with these values.
2847 FIXME: This seems like an incredibly poor idea. */
2849 CLEAR_HARD_REG_SET (stack_hard_regs
);
2850 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
2851 SET_HARD_REG_BIT (stack_hard_regs
, i
);
2852 problem_data
->stack_regs
= BITMAP_ALLOC (NULL
);
2853 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
2855 COPY_HARD_REG_SET (used
, reg_class_contents
[reg_preferred_class (i
)]);
2856 IOR_HARD_REG_SET (used
, reg_class_contents
[reg_alternate_class (i
)]);
2857 AND_HARD_REG_SET (used
, stack_hard_regs
);
2858 if (!hard_reg_set_empty_p (used
))
2859 bitmap_set_bit (problem_data
->stack_regs
, i
);
2863 /* We know that earlyclobber_regclass holds no more than
2864 N_REG_CLASSES elements. See df_urec_check_earlyclobber. */
2865 earlyclobber_regclass
= VEC_alloc (int, heap
, N_REG_CLASSES
);
2867 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2869 df_urec_bb_local_compute (bb_index
);
2872 VEC_free (int, heap
, earlyclobber_regclass
);
2876 /* Initialize the solution vectors. */
2879 df_urec_init (bitmap all_blocks
)
2881 unsigned int bb_index
;
2884 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2886 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2888 bitmap_copy (bb_info
->out
, bb_info
->gen
);
2889 bitmap_clear (bb_info
->in
);
2894 /* Or in the stack regs, hard regs and early clobber regs into the
2895 urec_in sets of all of the blocks. */
2899 df_urec_local_finalize (bitmap all_blocks
)
2901 bitmap tmp
= BITMAP_ALLOC (NULL
);
2903 unsigned int bb_index
;
2904 struct df_urec_problem_data
*problem_data
2905 = (struct df_urec_problem_data
*) df_urec
->problem_data
;
2907 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
2909 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2910 struct df_lr_bb_info
*bb_lr_info
= df_lr_get_bb_info (bb_index
);
2912 if (bb_index
!= ENTRY_BLOCK
&& bb_index
!= EXIT_BLOCK
)
2914 if (problem_data
->earlyclobbers_found
)
2915 bitmap_ior_into (bb_info
->in
, bb_info
->earlyclobber
);
2918 /* We can not use the same stack register for uninitialized
2919 pseudo-register and another living pseudo-register
2920 because if the uninitialized pseudo-register dies,
2921 subsequent pass reg-stack will be confused (it will
2922 believe that the other register dies). */
2923 bitmap_ior_into (bb_info
->in
, problem_data
->stack_regs
);
2924 bitmap_ior_into (bb_info
->out
, problem_data
->stack_regs
);
2928 /* No register may reach a location where it is not used. Thus
2929 we trim the rr result to the places where it is used. */
2930 bitmap_and_into (bb_info
->in
, bb_lr_info
->in
);
2931 bitmap_and_into (bb_info
->out
, bb_lr_info
->out
);
2932 bitmap_copy (bb_info
->top
, bb_info
->in
);
2933 if (bb_lr_info
->adef
)
2934 bitmap_ior_into (bb_info
->top
, bb_lr_info
->adef
);
2935 bitmap_and_into (bb_info
->top
, bb_lr_info
->top
);
2937 /* Hard registers may still stick in the ur_out set, but not
2938 be in the ur_in set, if their only mention was in a call
2939 in this block. This is because a call kills in the lr
2940 problem but does not kill in the rr problem. To clean
2941 this up, we execute the transfer function on the lr_in
2942 set and then use that to knock bits out of ur_out. */
2943 bitmap_ior_and_compl (tmp
, bb_info
->gen
, bb_lr_info
->in
,
2945 bitmap_and_into (bb_info
->out
, tmp
);
2950 BITMAP_FREE (problem_data
->stack_regs
);
2956 /* Confluence function that ignores fake edges. */
2959 df_urec_confluence_n (edge e
)
2961 bitmap op1
= df_urec_get_bb_info (e
->dest
->index
)->in
;
2962 bitmap op2
= df_urec_get_bb_info (e
->src
->index
)->out
;
2964 if (e
->flags
& EDGE_FAKE
)
2967 bitmap_ior_into (op1
, op2
);
2971 /* Transfer function. */
2974 df_urec_transfer_function (int bb_index
)
2976 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb_index
);
2977 bitmap in
= bb_info
->in
;
2978 bitmap out
= bb_info
->out
;
2979 bitmap gen
= bb_info
->gen
;
2980 bitmap kill
= bb_info
->kill
;
2982 return bitmap_ior_and_compl (out
, gen
, in
, kill
);
2986 /* Free all storage associated with the problem. */
2991 if (df_urec
->block_info
)
2995 for (i
= 0; i
< df_urec
->block_info_size
; i
++)
2997 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (i
);
3000 BITMAP_FREE (bb_info
->gen
);
3001 BITMAP_FREE (bb_info
->kill
);
3002 BITMAP_FREE (bb_info
->in
);
3003 BITMAP_FREE (bb_info
->out
);
3004 BITMAP_FREE (bb_info
->earlyclobber
);
3005 BITMAP_FREE (bb_info
->top
);
3009 free_alloc_pool (df_urec
->block_pool
);
3011 df_urec
->block_info_size
= 0;
3012 free (df_urec
->block_info
);
3013 free (df_urec
->problem_data
);
3019 /* Debugging info at top of bb. */
3022 df_urec_top_dump (basic_block bb
, FILE *file
)
3024 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb
->index
);
3025 if (!bb_info
|| !bb_info
->in
)
3028 fprintf (file
, ";; urec in \t");
3029 df_print_regset (file
, bb_info
->in
);
3030 fprintf (file
, ";; urec gen \t");
3031 df_print_regset (file
, bb_info
->gen
);
3032 fprintf (file
, ";; urec kill\t");
3033 df_print_regset (file
, bb_info
->kill
);
3034 fprintf (file
, ";; urec ec\t");
3035 df_print_regset (file
, bb_info
->earlyclobber
);
3039 /* Debugging info at bottom of bb. */
3042 df_urec_bottom_dump (basic_block bb
, FILE *file
)
3044 struct df_urec_bb_info
*bb_info
= df_urec_get_bb_info (bb
->index
);
3045 if (!bb_info
|| !bb_info
->out
)
3047 fprintf (file
, ";; urec out \t");
3048 df_print_regset (file
, bb_info
->out
);
3052 /* All of the information associated with every instance of the problem. */
3054 static struct df_problem problem_UREC
=
3056 DF_UREC
, /* Problem id. */
3057 DF_FORWARD
, /* Direction. */
3058 df_urec_alloc
, /* Allocate the problem specific data. */
3059 NULL
, /* Reset global information. */
3060 df_urec_free_bb_info
, /* Free basic block info. */
3061 df_urec_local_compute
, /* Local compute function. */
3062 df_urec_init
, /* Init the solution specific data. */
3063 df_worklist_dataflow
, /* Worklist solver. */
3064 NULL
, /* Confluence operator 0. */
3065 df_urec_confluence_n
, /* Confluence operator n. */
3066 df_urec_transfer_function
, /* Transfer function. */
3067 df_urec_local_finalize
, /* Finalize function. */
3068 df_urec_free
, /* Free all of the problem information. */
3069 df_urec_free
, /* Remove this problem from the stack of dataflow problems. */
3070 NULL
, /* Debugging. */
3071 df_urec_top_dump
, /* Debugging start block. */
3072 df_urec_bottom_dump
, /* Debugging end block. */
3073 NULL
, /* Incremental solution verify start. */
3074 NULL
, /* Incremental solution verify end. */
3075 &problem_LR
, /* Dependent problem. */
3076 TV_DF_UREC
, /* Timing variable. */
3077 false /* Reset blocks on dropping out of blocks_to_analyze. */
3081 /* Create a new DATAFLOW instance and add it to an existing instance
3082 of DF. The returned structure is what is used to get at the
3086 df_urec_add_problem (void)
3088 df_add_problem (&problem_UREC
);
3093 /*----------------------------------------------------------------------------
3094 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
3096 Link either the defs to the uses and / or the uses to the defs.
3098 These problems are set up like the other dataflow problems so that
3099 they nicely fit into the framework. They are much simpler and only
3100 involve a single traversal of instructions and an examination of
3101 the reaching defs information (the dependent problem).
3102 ----------------------------------------------------------------------------*/
3104 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
3106 /* Create a du or ud chain from SRC to DST and link it into SRC. */
3109 df_chain_create (struct df_ref
*src
, struct df_ref
*dst
)
3111 struct df_link
*head
= DF_REF_CHAIN (src
);
3112 struct df_link
*link
= pool_alloc (df_chain
->block_pool
);;
3114 DF_REF_CHAIN (src
) = link
;
3121 /* Delete any du or ud chains that start at REF and point to
3124 df_chain_unlink_1 (struct df_ref
*ref
, struct df_ref
*target
)
3126 struct df_link
*chain
= DF_REF_CHAIN (ref
);
3127 struct df_link
*prev
= NULL
;
3131 if (chain
->ref
== target
)
3134 prev
->next
= chain
->next
;
3136 DF_REF_CHAIN (ref
) = chain
->next
;
3137 pool_free (df_chain
->block_pool
, chain
);
3141 chain
= chain
->next
;
3146 /* Delete a du or ud chain that leave or point to REF. */
3149 df_chain_unlink (struct df_ref
*ref
)
3151 struct df_link
*chain
= DF_REF_CHAIN (ref
);
3154 struct df_link
*next
= chain
->next
;
3155 /* Delete the other side if it exists. */
3156 df_chain_unlink_1 (chain
->ref
, ref
);
3157 pool_free (df_chain
->block_pool
, chain
);
3160 DF_REF_CHAIN (ref
) = NULL
;
3164 /* Copy the du or ud chain starting at FROM_REF and attach it to
3168 df_chain_copy (struct df_ref
*to_ref
,
3169 struct df_link
*from_ref
)
3173 df_chain_create (to_ref
, from_ref
->ref
);
3174 from_ref
= from_ref
->next
;
3179 /* Remove this problem from the stack of dataflow problems. */
3182 df_chain_remove_problem (void)
3185 unsigned int bb_index
;
3187 /* Wholesale destruction of the old chains. */
3188 if (df_chain
->block_pool
)
3189 free_alloc_pool (df_chain
->block_pool
);
3191 EXECUTE_IF_SET_IN_BITMAP (df_chain
->out_of_date_transfer_functions
, 0, bb_index
, bi
)
3194 struct df_ref
**def_rec
;
3195 struct df_ref
**use_rec
;
3196 basic_block bb
= BASIC_BLOCK (bb_index
);
3198 if (df_chain_problem_p (DF_DU_CHAIN
))
3199 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
3200 DF_REF_CHAIN (*def_rec
) = NULL
;
3201 if (df_chain_problem_p (DF_UD_CHAIN
))
3202 for (use_rec
= df_get_artificial_uses (bb
->index
); *use_rec
; use_rec
++)
3203 DF_REF_CHAIN (*use_rec
) = NULL
;
3205 FOR_BB_INSNS (bb
, insn
)
3207 unsigned int uid
= INSN_UID (insn
);
3211 if (df_chain_problem_p (DF_DU_CHAIN
))
3212 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3213 DF_REF_CHAIN (*def_rec
) = NULL
;
3214 if (df_chain_problem_p (DF_UD_CHAIN
))
3216 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3217 DF_REF_CHAIN (*use_rec
) = NULL
;
3218 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
3219 DF_REF_CHAIN (*use_rec
) = NULL
;
3225 bitmap_clear (df_chain
->out_of_date_transfer_functions
);
3226 df_chain
->block_pool
= NULL
;
3230 /* Remove the chain problem completely. */
3233 df_chain_fully_remove_problem (void)
3235 df_chain_remove_problem ();
3236 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
3241 /* Create def-use or use-def chains. */
3244 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
3246 df_chain_remove_problem ();
3247 df_chain
->block_pool
= create_alloc_pool ("df_chain_block pool",
3248 sizeof (struct df_link
), 50);
3249 df_chain
->optional_p
= true;
3253 /* Reset all of the chains when the set of basic blocks changes. */
3256 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED
)
3258 df_chain_remove_problem ();
3262 /* Create the chains for a list of USEs. */
3265 df_chain_create_bb_process_use (bitmap local_rd
,
3266 struct df_ref
**use_rec
,
3267 enum df_ref_flags top_flag
)
3270 unsigned int def_index
;
3274 struct df_ref
*use
= *use_rec
;
3275 unsigned int uregno
= DF_REF_REGNO (use
);
3276 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
3277 || (uregno
>= FIRST_PSEUDO_REGISTER
))
3279 /* Do not want to go through this for an uninitialized var. */
3280 int count
= DF_DEFS_COUNT (uregno
);
3283 if (top_flag
== (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
))
3285 unsigned int first_index
= DF_DEFS_BEGIN (uregno
);
3286 unsigned int last_index
= first_index
+ count
- 1;
3288 EXECUTE_IF_SET_IN_BITMAP (local_rd
, first_index
, def_index
, bi
)
3291 if (def_index
> last_index
)
3294 def
= DF_DEFS_GET (def_index
);
3295 if (df_chain_problem_p (DF_DU_CHAIN
))
3296 df_chain_create (def
, use
);
3297 if (df_chain_problem_p (DF_UD_CHAIN
))
3298 df_chain_create (use
, def
);
3309 /* Create chains from reaching defs bitmaps for basic block BB. */
3312 df_chain_create_bb (unsigned int bb_index
)
3314 basic_block bb
= BASIC_BLOCK (bb_index
);
3315 struct df_rd_bb_info
*bb_info
= df_rd_get_bb_info (bb_index
);
3317 bitmap cpy
= BITMAP_ALLOC (NULL
);
3318 struct df_ref
**def_rec
;
3320 bitmap_copy (cpy
, bb_info
->in
);
3321 bitmap_set_bit (df_chain
->out_of_date_transfer_functions
, bb_index
);
3323 /* Since we are going forwards, process the artificial uses first
3324 then the artificial defs second. */
3327 /* Create the chains for the artificial uses from the EH_USES at the
3328 beginning of the block. */
3330 /* Artificials are only hard regs. */
3331 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
3332 df_chain_create_bb_process_use (cpy
,
3333 df_get_artificial_uses (bb
->index
),
3337 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3339 struct df_ref
*def
= *def_rec
;
3340 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
3342 unsigned int dregno
= DF_REF_REGNO (def
);
3343 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3344 bitmap_clear_range (cpy
,
3345 DF_DEFS_BEGIN (dregno
),
3346 DF_DEFS_COUNT (dregno
));
3347 bitmap_set_bit (cpy
, DF_REF_ID (def
));
3351 /* Process the regular instructions next. */
3352 FOR_BB_INSNS (bb
, insn
)
3354 struct df_ref
**def_rec
;
3355 unsigned int uid
= INSN_UID (insn
);
3360 /* Now scan the uses and link them up with the defs that remain
3361 in the cpy vector. */
3363 df_chain_create_bb_process_use (cpy
, DF_INSN_UID_USES (uid
), 0);
3365 if (df
->changeable_flags
& DF_EQ_NOTES
)
3366 df_chain_create_bb_process_use (cpy
, DF_INSN_UID_EQ_USES (uid
), 0);
3369 /* Since we are going forwards, process the defs second. This
3370 pass only changes the bits in cpy. */
3371 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3373 struct df_ref
*def
= *def_rec
;
3374 unsigned int dregno
= DF_REF_REGNO (def
);
3375 if ((!(df
->changeable_flags
& DF_NO_HARD_REGS
))
3376 || (dregno
>= FIRST_PSEUDO_REGISTER
))
3378 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3379 bitmap_clear_range (cpy
,
3380 DF_DEFS_BEGIN (dregno
),
3381 DF_DEFS_COUNT (dregno
));
3382 if (!(DF_REF_FLAGS (def
)
3383 & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
)))
3384 bitmap_set_bit (cpy
, DF_REF_ID (def
));
3389 /* Create the chains for the artificial uses of the hard registers
3390 at the end of the block. */
3391 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
))
3392 df_chain_create_bb_process_use (cpy
,
3393 df_get_artificial_uses (bb
->index
),
3399 /* Create def-use chains from reaching use bitmaps for basic blocks
3403 df_chain_finalize (bitmap all_blocks
)
3405 unsigned int bb_index
;
3408 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
3410 df_chain_create_bb (bb_index
);
3415 /* Free all storage associated with the problem. */
3418 df_chain_free (void)
3420 free_alloc_pool (df_chain
->block_pool
);
3421 BITMAP_FREE (df_chain
->out_of_date_transfer_functions
);
3426 /* Debugging info. */
3429 df_chain_top_dump (basic_block bb
, FILE *file
)
3431 if (df_chain_problem_p (DF_DU_CHAIN
))
3434 struct df_ref
**def_rec
= df_get_artificial_defs (bb
->index
);
3438 fprintf (file
, ";; DU chains for artificial defs\n");
3441 struct df_ref
*def
= *def_rec
;
3442 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
3443 df_chain_dump (DF_REF_CHAIN (def
), file
);
3444 fprintf (file
, "\n");
3449 FOR_BB_INSNS (bb
, insn
)
3451 unsigned int uid
= INSN_UID (insn
);
3454 def_rec
= DF_INSN_UID_DEFS (uid
);
3457 fprintf (file
, ";; DU chains for insn luid %d uid %d\n",
3458 DF_INSN_LUID (insn
), uid
);
3462 struct df_ref
*def
= *def_rec
;
3463 fprintf (file
, ";; reg %d ", DF_REF_REGNO (def
));
3464 if (def
->flags
& DF_REF_READ_WRITE
)
3465 fprintf (file
, "read/write ");
3466 df_chain_dump (DF_REF_CHAIN (def
), file
);
3467 fprintf (file
, "\n");
3478 df_chain_bottom_dump (basic_block bb
, FILE *file
)
3480 if (df_chain_problem_p (DF_UD_CHAIN
))
3483 struct df_ref
**use_rec
= df_get_artificial_uses (bb
->index
);
3487 fprintf (file
, ";; UD chains for artificial uses\n");
3490 struct df_ref
*use
= *use_rec
;
3491 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
3492 df_chain_dump (DF_REF_CHAIN (use
), file
);
3493 fprintf (file
, "\n");
3498 FOR_BB_INSNS (bb
, insn
)
3500 unsigned int uid
= INSN_UID (insn
);
3503 struct df_ref
**eq_use_rec
= DF_INSN_UID_EQ_USES (uid
);
3504 use_rec
= DF_INSN_UID_USES (uid
);
3505 if (*use_rec
|| *eq_use_rec
)
3507 fprintf (file
, ";; UD chains for insn luid %d uid %d\n",
3508 DF_INSN_LUID (insn
), uid
);
3512 struct df_ref
*use
= *use_rec
;
3513 fprintf (file
, ";; reg %d ", DF_REF_REGNO (use
));
3514 if (use
->flags
& DF_REF_READ_WRITE
)
3515 fprintf (file
, "read/write ");
3516 df_chain_dump (DF_REF_CHAIN (use
), file
);
3517 fprintf (file
, "\n");
3522 struct df_ref
*use
= *eq_use_rec
;
3523 fprintf (file
, ";; eq_note reg %d ", DF_REF_REGNO (use
));
3524 df_chain_dump (DF_REF_CHAIN (use
), file
);
3525 fprintf (file
, "\n");
3535 static struct df_problem problem_CHAIN
=
3537 DF_CHAIN
, /* Problem id. */
3538 DF_NONE
, /* Direction. */
3539 df_chain_alloc
, /* Allocate the problem specific data. */
3540 df_chain_reset
, /* Reset global information. */
3541 NULL
, /* Free basic block info. */
3542 NULL
, /* Local compute function. */
3543 NULL
, /* Init the solution specific data. */
3544 NULL
, /* Iterative solver. */
3545 NULL
, /* Confluence operator 0. */
3546 NULL
, /* Confluence operator n. */
3547 NULL
, /* Transfer function. */
3548 df_chain_finalize
, /* Finalize function. */
3549 df_chain_free
, /* Free all of the problem information. */
3550 df_chain_fully_remove_problem
,/* Remove this problem from the stack of dataflow problems. */
3551 NULL
, /* Debugging. */
3552 df_chain_top_dump
, /* Debugging start block. */
3553 df_chain_bottom_dump
, /* Debugging end block. */
3554 NULL
, /* Incremental solution verify start. */
3555 NULL
, /* Incremental solution verify end. */
3556 &problem_RD
, /* Dependent problem. */
3557 TV_DF_CHAIN
, /* Timing variable. */
3558 false /* Reset blocks on dropping out of blocks_to_analyze. */
3562 /* Create a new DATAFLOW instance and add it to an existing instance
3563 of DF. The returned structure is what is used to get at the
3567 df_chain_add_problem (enum df_chain_flags chain_flags
)
3569 df_add_problem (&problem_CHAIN
);
3570 df_chain
->local_flags
= (unsigned int)chain_flags
;
3571 df_chain
->out_of_date_transfer_functions
= BITMAP_ALLOC (NULL
);
3574 #undef df_chain_problem_p
3577 /*----------------------------------------------------------------------------
3578 This pass computes REG_DEAD and REG_UNUSED notes.
3579 ----------------------------------------------------------------------------*/
3582 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
3584 df_note
->optional_p
= true;
3587 #ifdef REG_DEAD_DEBUGGING
3589 df_print_note (const char *prefix
, rtx insn
, rtx note
)
3593 fprintf (dump_file
, "%s %d ", prefix
, INSN_UID (insn
));
3594 print_rtl (dump_file
, note
);
3595 fprintf (dump_file
, "\n");
3601 /* After reg-stack, the x86 floating point stack regs are difficult to
3602 analyze because of all of the pushes, pops and rotations. Thus, we
3603 just leave the notes alone. */
3607 df_ignore_stack_reg (int regno
)
3609 return regstack_completed
3610 && IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
);
3614 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED
)
3621 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3622 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3625 df_kill_notes (rtx insn
, rtx
*old_dead_notes
, rtx
*old_unused_notes
)
3627 rtx
*pprev
= ®_NOTES (insn
);
3634 switch (REG_NOTE_KIND (link
))
3637 /* After reg-stack, we need to ignore any unused notes
3638 for the stack registers. */
3639 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3641 pprev
= &XEXP (link
, 1);
3646 rtx next
= XEXP (link
, 1);
3647 #ifdef REG_DEAD_DEBUGGING
3648 df_print_note ("deleting: ", insn
, link
);
3650 XEXP (link
, 1) = dead
;
3652 *pprev
= link
= next
;
3657 /* After reg-stack, we need to ignore any unused notes
3658 for the stack registers. */
3659 if (df_ignore_stack_reg (REGNO (XEXP (link
, 0))))
3661 pprev
= &XEXP (link
, 1);
3666 rtx next
= XEXP (link
, 1);
3667 #ifdef REG_DEAD_DEBUGGING
3668 df_print_note ("deleting: ", insn
, link
);
3670 XEXP (link
, 1) = unused
;
3672 *pprev
= link
= next
;
3677 pprev
= &XEXP (link
, 1);
3683 *old_dead_notes
= dead
;
3684 *old_unused_notes
= unused
;
3688 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3689 list, otherwise create a new one. */
3692 df_set_note (enum reg_note note_type
, rtx insn
, rtx old
, rtx reg
)
3698 if (XEXP (this, 0) == reg
)
3701 XEXP (prev
, 1) = XEXP (this, 1);
3703 old
= XEXP (this, 1);
3704 XEXP (this, 1) = REG_NOTES (insn
);
3705 REG_NOTES (insn
) = this;
3711 this = XEXP (this, 1);
3714 /* Did not find the note. */
3715 REG_NOTES (insn
) = alloc_EXPR_LIST (note_type
, reg
, REG_NOTES (insn
));
3719 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3720 arguments. Return true if the register value described by MWS's
3721 mw_reg is known to be completely unused, and if mw_reg can therefore
3722 be used in a REG_UNUSED note. */
3725 df_whole_mw_reg_unused_p (struct df_mw_hardreg
*mws
,
3726 bitmap live
, bitmap artificial_uses
)
3730 /* If MWS describes a partial reference, create REG_UNUSED notes for
3731 individual hard registers. */
3732 if (mws
->flags
& DF_REF_PARTIAL
)
3735 /* Likewise if some part of the register is used. */
3736 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3737 if (bitmap_bit_p (live
, r
)
3738 || bitmap_bit_p (artificial_uses
, r
))
3741 gcc_assert (REG_P (mws
->mw_reg
));
3745 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3746 based on the bits in LIVE. Do not generate notes for registers in
3747 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3748 not generated if the reg is both read and written by the
3753 df_set_unused_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3754 bitmap live
, bitmap do_not_gen
,
3755 bitmap artificial_uses
)
3759 #ifdef REG_DEAD_DEBUGGING
3761 fprintf (dump_file
, "mw_set_unused looking at mws[%d..%d]\n",
3762 mws
->start_regno
, mws
->end_regno
);
3765 if (df_whole_mw_reg_unused_p (mws
, live
, artificial_uses
))
3767 unsigned int regno
= mws
->start_regno
;
3768 old
= df_set_note (REG_UNUSED
, insn
, old
, mws
->mw_reg
);
3770 #ifdef REG_DEAD_DEBUGGING
3771 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3773 bitmap_set_bit (do_not_gen
, regno
);
3774 /* Only do this if the value is totally dead. */
3777 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3779 if (!bitmap_bit_p (live
, r
)
3780 && !bitmap_bit_p (artificial_uses
, r
))
3782 old
= df_set_note (REG_UNUSED
, insn
, old
, regno_reg_rtx
[r
]);
3783 #ifdef REG_DEAD_DEBUGGING
3784 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3787 bitmap_set_bit (do_not_gen
, r
);
3793 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3794 arguments. Return true if the register value described by MWS's
3795 mw_reg is known to be completely dead, and if mw_reg can therefore
3796 be used in a REG_DEAD note. */
3799 df_whole_mw_reg_dead_p (struct df_mw_hardreg
*mws
,
3800 bitmap live
, bitmap artificial_uses
,
3805 /* If MWS describes a partial reference, create REG_DEAD notes for
3806 individual hard registers. */
3807 if (mws
->flags
& DF_REF_PARTIAL
)
3810 /* Likewise if some part of the register is not dead. */
3811 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3812 if (bitmap_bit_p (live
, r
)
3813 || bitmap_bit_p (artificial_uses
, r
)
3814 || bitmap_bit_p (do_not_gen
, r
))
3817 gcc_assert (REG_P (mws
->mw_reg
));
3821 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3822 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3823 from being set if the instruction both reads and writes the
3827 df_set_dead_notes_for_mw (rtx insn
, rtx old
, struct df_mw_hardreg
*mws
,
3828 bitmap live
, bitmap do_not_gen
,
3829 bitmap artificial_uses
)
3833 #ifdef REG_DEAD_DEBUGGING
3836 fprintf (dump_file
, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3837 mws
->start_regno
, mws
->end_regno
);
3838 df_print_regset (dump_file
, do_not_gen
);
3839 fprintf (dump_file
, " live =");
3840 df_print_regset (dump_file
, live
);
3841 fprintf (dump_file
, " artificial uses =");
3842 df_print_regset (dump_file
, artificial_uses
);
3846 if (df_whole_mw_reg_dead_p (mws
, live
, artificial_uses
, do_not_gen
))
3848 /* Add a dead note for the entire multi word register. */
3849 old
= df_set_note (REG_DEAD
, insn
, old
, mws
->mw_reg
);
3850 #ifdef REG_DEAD_DEBUGGING
3851 df_print_note ("adding 1: ", insn
, REG_NOTES (insn
));
3856 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
3857 if (!bitmap_bit_p (live
, r
)
3858 && !bitmap_bit_p (artificial_uses
, r
)
3859 && !bitmap_bit_p (do_not_gen
, r
))
3861 old
= df_set_note (REG_DEAD
, insn
, old
, regno_reg_rtx
[r
]);
3862 #ifdef REG_DEAD_DEBUGGING
3863 df_print_note ("adding 2: ", insn
, REG_NOTES (insn
));
3871 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3872 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3875 df_create_unused_note (rtx insn
, rtx old
, struct df_ref
*def
,
3876 bitmap live
, bitmap artificial_uses
)
3878 unsigned int dregno
= DF_REF_REGNO (def
);
3880 #ifdef REG_DEAD_DEBUGGING
3883 fprintf (dump_file
, " regular looking at def ");
3884 df_ref_debug (def
, dump_file
);
3888 if (!(bitmap_bit_p (live
, dregno
)
3889 || (DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
)
3890 || bitmap_bit_p (artificial_uses
, dregno
)
3891 || df_ignore_stack_reg (dregno
)))
3893 rtx reg
= (DF_REF_LOC (def
))
3894 ? *DF_REF_REAL_LOC (def
): DF_REF_REG (def
);
3895 old
= df_set_note (REG_UNUSED
, insn
, old
, reg
);
3896 #ifdef REG_DEAD_DEBUGGING
3897 df_print_note ("adding 3: ", insn
, REG_NOTES (insn
));
3905 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3906 info: lifetime, bb, and number of defs and uses for basic block
3907 BB. The three bitvectors are scratch regs used here. */
3910 df_note_bb_compute (unsigned int bb_index
,
3911 bitmap live
, bitmap do_not_gen
, bitmap artificial_uses
)
3913 basic_block bb
= BASIC_BLOCK (bb_index
);
3915 struct df_ref
**def_rec
;
3916 struct df_ref
**use_rec
;
3918 bitmap_copy (live
, df_get_live_out (bb
));
3919 bitmap_clear (artificial_uses
);
3921 #ifdef REG_DEAD_DEBUGGING
3924 fprintf (dump_file
, "live at bottom ");
3925 df_print_regset (dump_file
, live
);
3929 /* Process the artificial defs and uses at the bottom of the block
3930 to begin processing. */
3931 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
3933 struct df_ref
*def
= *def_rec
;
3934 #ifdef REG_DEAD_DEBUGGING
3936 fprintf (dump_file
, "artificial def %d\n", DF_REF_REGNO (def
));
3939 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
3940 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
3943 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
3945 struct df_ref
*use
= *use_rec
;
3946 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
3948 unsigned int regno
= DF_REF_REGNO (use
);
3949 bitmap_set_bit (live
, regno
);
3951 /* Notes are not generated for any of the artificial registers
3952 at the bottom of the block. */
3953 bitmap_set_bit (artificial_uses
, regno
);
3957 #ifdef REG_DEAD_DEBUGGING
3960 fprintf (dump_file
, "live before artificials out ");
3961 df_print_regset (dump_file
, live
);
3965 FOR_BB_INSNS_REVERSE (bb
, insn
)
3967 unsigned int uid
= INSN_UID (insn
);
3968 struct df_mw_hardreg
**mws_rec
;
3970 rtx old_unused_notes
;
3975 bitmap_clear (do_not_gen
);
3976 df_kill_notes (insn
, &old_dead_notes
, &old_unused_notes
);
3978 /* Process the defs. */
3981 #ifdef REG_DEAD_DEBUGGING
3984 fprintf (dump_file
, "processing call %d\n live =", INSN_UID (insn
));
3985 df_print_regset (dump_file
, live
);
3988 /* We only care about real sets for calls. Clobbers cannot
3989 be depended on to really die. */
3990 mws_rec
= DF_INSN_UID_MWS (uid
);
3993 struct df_mw_hardreg
*mws
= *mws_rec
;
3994 if ((mws
->type
== DF_REF_REG_DEF
)
3995 && !df_ignore_stack_reg (REGNO (mws
->mw_reg
)))
3997 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
3998 mws
, live
, do_not_gen
,
4003 /* All of the defs except the return value are some sort of
4004 clobber. This code is for the return. */
4005 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4007 struct df_ref
*def
= *def_rec
;
4008 unsigned int dregno
= DF_REF_REGNO (def
);
4009 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
4012 = df_create_unused_note (insn
, old_unused_notes
,
4013 def
, live
, artificial_uses
);
4014 bitmap_set_bit (do_not_gen
, dregno
);
4017 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
4018 bitmap_clear_bit (live
, dregno
);
4024 mws_rec
= DF_INSN_UID_MWS (uid
);
4027 struct df_mw_hardreg
*mws
= *mws_rec
;
4028 if (mws
->type
== DF_REF_REG_DEF
)
4030 = df_set_unused_notes_for_mw (insn
, old_unused_notes
,
4031 mws
, live
, do_not_gen
,
4036 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4038 struct df_ref
*def
= *def_rec
;
4039 unsigned int dregno
= DF_REF_REGNO (def
);
4041 = df_create_unused_note (insn
, old_unused_notes
,
4042 def
, live
, artificial_uses
);
4044 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))
4045 bitmap_set_bit (do_not_gen
, dregno
);
4047 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
| DF_REF_CONDITIONAL
))
4048 bitmap_clear_bit (live
, dregno
);
4052 /* Process the uses. */
4053 mws_rec
= DF_INSN_UID_MWS (uid
);
4056 struct df_mw_hardreg
*mws
= *mws_rec
;
4057 if ((mws
->type
!= DF_REF_REG_DEF
)
4058 && !df_ignore_stack_reg (REGNO (mws
->mw_reg
)))
4060 = df_set_dead_notes_for_mw (insn
, old_dead_notes
,
4061 mws
, live
, do_not_gen
,
4066 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
4068 struct df_ref
*use
= *use_rec
;
4069 unsigned int uregno
= DF_REF_REGNO (use
);
4071 #ifdef REG_DEAD_DEBUGGING
4074 fprintf (dump_file
, " regular looking at use ");
4075 df_ref_debug (use
, dump_file
);
4078 if (!bitmap_bit_p (live
, uregno
))
4080 if ( (!(DF_REF_FLAGS (use
) & DF_REF_MW_HARDREG
))
4081 && (!bitmap_bit_p (do_not_gen
, uregno
))
4082 && (!bitmap_bit_p (artificial_uses
, uregno
))
4083 && (!(DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
))
4084 && (!df_ignore_stack_reg (uregno
)))
4086 rtx reg
= (DF_REF_LOC (use
))
4087 ? *DF_REF_REAL_LOC (use
) : DF_REF_REG (use
);
4088 old_dead_notes
= df_set_note (REG_DEAD
, insn
, old_dead_notes
, reg
);
4090 #ifdef REG_DEAD_DEBUGGING
4091 df_print_note ("adding 4: ", insn
, REG_NOTES (insn
));
4094 /* This register is now live. */
4095 bitmap_set_bit (live
, uregno
);
4099 while (old_unused_notes
)
4101 rtx next
= XEXP (old_unused_notes
, 1);
4102 free_EXPR_LIST_node (old_unused_notes
);
4103 old_unused_notes
= next
;
4105 while (old_dead_notes
)
4107 rtx next
= XEXP (old_dead_notes
, 1);
4108 free_EXPR_LIST_node (old_dead_notes
);
4109 old_dead_notes
= next
;
4115 /* Compute register info: lifetime, bb, and number of defs and uses. */
4117 df_note_compute (bitmap all_blocks
)
4119 unsigned int bb_index
;
4121 bitmap live
= BITMAP_ALLOC (&df_bitmap_obstack
);
4122 bitmap do_not_gen
= BITMAP_ALLOC (&df_bitmap_obstack
);
4123 bitmap artificial_uses
= BITMAP_ALLOC (&df_bitmap_obstack
);
4125 #ifdef REG_DEAD_DEBUGGING
4127 print_rtl_with_bb (dump_file
, get_insns());
4130 EXECUTE_IF_SET_IN_BITMAP (all_blocks
, 0, bb_index
, bi
)
4132 df_note_bb_compute (bb_index
, live
, do_not_gen
, artificial_uses
);
4136 BITMAP_FREE (do_not_gen
);
4137 BITMAP_FREE (artificial_uses
);
4141 /* Free all storage associated with the problem. */
4150 /* All of the information associated every instance of the problem. */
4152 static struct df_problem problem_NOTE
=
4154 DF_NOTE
, /* Problem id. */
4155 DF_NONE
, /* Direction. */
4156 df_note_alloc
, /* Allocate the problem specific data. */
4157 NULL
, /* Reset global information. */
4158 NULL
, /* Free basic block info. */
4159 df_note_compute
, /* Local compute function. */
4160 NULL
, /* Init the solution specific data. */
4161 NULL
, /* Iterative solver. */
4162 NULL
, /* Confluence operator 0. */
4163 NULL
, /* Confluence operator n. */
4164 NULL
, /* Transfer function. */
4165 NULL
, /* Finalize function. */
4166 df_note_free
, /* Free all of the problem information. */
4167 df_note_free
, /* Remove this problem from the stack of dataflow problems. */
4168 NULL
, /* Debugging. */
4169 NULL
, /* Debugging start block. */
4170 NULL
, /* Debugging end block. */
4171 NULL
, /* Incremental solution verify start. */
4172 NULL
, /* Incremental solution verify end. */
4174 /* Technically this is only dependent on the live registers problem
4175 but it will produce information if built one of uninitialized
4176 register problems (UR, UREC) is also run. */
4177 &problem_LR
, /* Dependent problem. */
4178 TV_DF_NOTE
, /* Timing variable. */
4179 false /* Reset blocks on dropping out of blocks_to_analyze. */
4183 /* Create a new DATAFLOW instance and add it to an existing instance
4184 of DF. The returned structure is what is used to get at the
4188 df_note_add_problem (void)
4190 df_add_problem (&problem_NOTE
);
4196 /*----------------------------------------------------------------------------
4197 Functions for simulating the effects of single insns.
4199 You can either simulate in the forwards direction, starting from
4200 the top of a block or the backwards direction from the end of the
4201 block. The main difference is that if you go forwards, the uses
4202 are examined first then the defs, and if you go backwards, the defs
4203 are examined first then the uses.
4205 If you start at the top of the block, use one of DF_LIVE_IN or
4206 DF_LR_IN. If you start at the bottom of the block use one of
4207 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
4208 THEY WILL BE DESTROYED.
4210 ----------------------------------------------------------------------------*/
4213 /* Find the set of DEFs for INSN. */
4216 df_simulate_find_defs (rtx insn
, bitmap defs
)
4218 struct df_ref
**def_rec
;
4219 unsigned int uid
= INSN_UID (insn
);
4223 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4225 struct df_ref
*def
= *def_rec
;
4226 unsigned int dregno
= DF_REF_REGNO (def
);
4228 if (DF_REF_FLAGS (def
) & DF_REF_MUST_CLOBBER
)
4230 if (dregno
>= FIRST_PSEUDO_REGISTER
4231 || !(SIBLING_CALL_P (insn
)
4232 && bitmap_bit_p (df
->exit_block_uses
, dregno
)
4233 && !refers_to_regno_p (dregno
, dregno
+1,
4234 current_function_return_rtx
,
4237 /* If the def is to only part of the reg, it does
4238 not kill the other defs that reach here. */
4239 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
4240 bitmap_set_bit (defs
, dregno
);
4244 /* This is the return value. */
4245 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
4246 bitmap_set_bit (defs
, dregno
);
4251 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4253 struct df_ref
*def
= *def_rec
;
4254 /* If the def is to only part of the reg, it does
4255 not kill the other defs that reach here. */
4256 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
4257 bitmap_set_bit (defs
, DF_REF_REGNO (def
));
4263 /* Simulate the effects of the defs of INSN on LIVE. */
4266 df_simulate_defs (rtx insn
, bitmap live
)
4268 struct df_ref
**def_rec
;
4269 unsigned int uid
= INSN_UID (insn
);
4273 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4275 struct df_ref
*def
= *def_rec
;
4276 unsigned int dregno
= DF_REF_REGNO (def
);
4278 if (DF_REF_FLAGS (def
) & DF_REF_MUST_CLOBBER
)
4280 if (dregno
>= FIRST_PSEUDO_REGISTER
4281 || !(SIBLING_CALL_P (insn
)
4282 && bitmap_bit_p (df
->exit_block_uses
, dregno
)
4283 && !refers_to_regno_p (dregno
, dregno
+1,
4284 current_function_return_rtx
,
4287 /* If the def is to only part of the reg, it does
4288 not kill the other defs that reach here. */
4289 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
4290 bitmap_clear_bit (live
, dregno
);
4294 /* This is the return value. */
4295 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
4296 bitmap_clear_bit (live
, dregno
);
4301 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4303 struct df_ref
*def
= *def_rec
;
4304 unsigned int dregno
= DF_REF_REGNO (def
);
4306 /* If the def is to only part of the reg, it does
4307 not kill the other defs that reach here. */
4308 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
4309 bitmap_clear_bit (live
, dregno
);
4315 /* Simulate the effects of the uses of INSN on LIVE. */
4318 df_simulate_uses (rtx insn
, bitmap live
)
4320 struct df_ref
**use_rec
;
4321 unsigned int uid
= INSN_UID (insn
);
4323 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
4325 struct df_ref
*use
= *use_rec
;
4326 /* Add use to set of uses in this BB. */
4327 bitmap_set_bit (live
, DF_REF_REGNO (use
));
4332 /* Add back the always live regs in BB to LIVE. */
4335 df_simulate_fixup_sets (basic_block bb
, bitmap live
)
4337 /* These regs are considered always live so if they end up dying
4338 because of some def, we need to bring the back again. */
4339 if (df_has_eh_preds (bb
))
4340 bitmap_ior_into (live
, df
->eh_block_artificial_uses
);
4342 bitmap_ior_into (live
, df
->regular_block_artificial_uses
);
4346 /* Apply the artificial uses and defs at the top of BB in a forwards
4350 df_simulate_artificial_refs_at_top (basic_block bb
, bitmap live
)
4352 struct df_ref
**def_rec
;
4353 struct df_ref
**use_rec
;
4354 int bb_index
= bb
->index
;
4356 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
4358 struct df_ref
*use
= *use_rec
;
4359 if (DF_REF_FLAGS (use
) & DF_REF_AT_TOP
)
4360 bitmap_set_bit (live
, DF_REF_REGNO (use
));
4363 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4365 struct df_ref
*def
= *def_rec
;
4366 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
4367 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
4372 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4375 df_simulate_one_insn_forwards (basic_block bb
, rtx insn
, bitmap live
)
4377 if (! INSN_P (insn
))
4380 df_simulate_uses (insn
, live
);
4381 df_simulate_defs (insn
, live
);
4382 df_simulate_fixup_sets (bb
, live
);
4386 /* Apply the artificial uses and defs at the end of BB in a backwards
4390 df_simulate_artificial_refs_at_end (basic_block bb
, bitmap live
)
4392 struct df_ref
**def_rec
;
4393 struct df_ref
**use_rec
;
4394 int bb_index
= bb
->index
;
4396 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
4398 struct df_ref
*def
= *def_rec
;
4399 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
4400 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
4403 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
4405 struct df_ref
*use
= *use_rec
;
4406 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
4407 bitmap_set_bit (live
, DF_REF_REGNO (use
));
4412 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
4415 df_simulate_one_insn_backwards (basic_block bb
, rtx insn
, bitmap live
)
4417 if (! INSN_P (insn
))
4420 df_simulate_defs (insn
, live
);
4421 df_simulate_uses (insn
, live
);
4422 df_simulate_fixup_sets (bb
, live
);