1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 2, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
29 #include "coretypes.h"
33 #include "insn-config.h"
38 #include "alloc-pool.h"
40 #include "hard-reg-set.h"
41 #include "basic-block.h"
47 #include "target-def.h"
49 #include "tree-pass.h"
52 #define HAVE_epilogue 0
55 #define HAVE_prologue 0
57 #ifndef HAVE_sibcall_epilogue
58 #define HAVE_sibcall_epilogue 0
62 #define EPILOGUE_USES(REGNO) 0
65 /* The bitmap_obstack is used to hold some static variables that
66 should not be reset after each function is compiled. */
68 static bitmap_obstack persistent_obstack;
70 /* The set of hard registers in eliminables[i].from. */
72 static HARD_REG_SET elim_reg_set;
74 /* This is a bitmap copy of regs_invalidated_by_call so that we can
75 easily add it into bitmaps, etc. */
77 bitmap df_invalidated_by_call = NULL;
79 /* Initialize ur_in and ur_out as if all hard registers were partially
82 struct df_collection_rec
84 struct df_ref ** def_vec;
85 unsigned int next_def;
86 struct df_ref ** use_vec;
87 unsigned int next_use;
88 struct df_ref ** eq_use_vec;
89 unsigned int next_eq_use;
90 struct df_mw_hardreg **mw_vec;
94 static struct df_ref * df_null_ref_rec[1];
95 static struct df_mw_hardreg * df_null_mw_rec[1];
97 static void df_ref_record (struct df_collection_rec *,
99 basic_block, rtx, enum df_ref_type,
101 static void df_def_record_1 (struct df_collection_rec *,
102 rtx, basic_block, rtx,
104 static void df_defs_record (struct df_collection_rec *,
105 rtx, basic_block, rtx,
107 static void df_uses_record (struct df_collection_rec *,
108 rtx *, enum df_ref_type,
109 basic_block, rtx, enum df_ref_flags);
111 static struct df_ref *df_ref_create_structure (struct df_collection_rec *, rtx, rtx *,
112 basic_block, rtx, enum df_ref_type,
115 static void df_insn_refs_collect (struct df_collection_rec*,
117 static void df_canonize_collection_rec (struct df_collection_rec *);
119 static void df_get_regular_block_artificial_uses (bitmap);
120 static void df_get_eh_block_artificial_uses (bitmap);
122 static void df_record_entry_block_defs (bitmap);
123 static void df_record_exit_block_uses (bitmap);
124 static void df_get_exit_block_use_set (bitmap);
125 static void df_get_entry_block_def_set (bitmap);
126 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
127 static void df_ref_chain_delete_du_chain (struct df_ref **);
128 static void df_ref_chain_delete (struct df_ref **);
130 static void df_refs_add_to_chains (struct df_collection_rec *,
133 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block, rtx, bool);
134 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
135 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
136 static void df_install_ref (struct df_ref *, struct df_reg_info *,
137 struct df_ref_info *, bool);
139 static int df_ref_compare (const void *, const void *);
140 static int df_mw_compare (const void *, const void *);
142 /* Indexed by hardware reg number, is true if that register is ever
143 used in the current function.
145 In df-scan.c, this is set up to record the hard regs used
146 explicitly. Reload adds in the hard regs used for holding pseudo
147 regs. Final uses it to generate the code in the function prologue
148 and epilogue to save and restore registers as needed. */
150 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
152 /*----------------------------------------------------------------------------
153 SCANNING DATAFLOW PROBLEM
155 There are several ways in which scanning looks just like the other
156 dataflow problems. It shares the all the mechanisms for local info
157 as well as basic block info. Where it differs is when and how often
158 it gets run. It also has no need for the iterative solver.
159 ----------------------------------------------------------------------------*/
161 /* Problem data for the scanning dataflow function. */
162 struct df_scan_problem_data
165 alloc_pool insn_pool;
167 alloc_pool mw_reg_pool;
168 alloc_pool mw_link_pool;
169 bitmap_obstack reg_bitmaps;
170 bitmap_obstack insn_bitmaps;
173 typedef struct df_scan_bb_info *df_scan_bb_info_t;
176 df_scan_free_internal (void)
178 struct df_scan_problem_data *problem_data
179 = (struct df_scan_problem_data *) df_scan->problem_data;
181 free (df->def_info.refs);
182 free (df->def_info.begin);
183 free (df->def_info.count);
184 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
186 free (df->use_info.refs);
187 free (df->use_info.begin);
188 free (df->use_info.count);
189 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
195 free (df->eq_use_regs);
196 df->eq_use_regs = NULL;
204 free (df_scan->block_info);
205 df_scan->block_info = NULL;
206 df_scan->block_info_size = 0;
208 BITMAP_FREE (df->hardware_regs_used);
209 BITMAP_FREE (df->regular_block_artificial_uses);
210 BITMAP_FREE (df->eh_block_artificial_uses);
211 BITMAP_FREE (df->entry_block_defs);
212 BITMAP_FREE (df->exit_block_uses);
213 BITMAP_FREE (df->insns_to_delete);
214 BITMAP_FREE (df->insns_to_rescan);
215 BITMAP_FREE (df->insns_to_notes_rescan);
217 free_alloc_pool (df_scan->block_pool);
218 free_alloc_pool (problem_data->ref_pool);
219 free_alloc_pool (problem_data->insn_pool);
220 free_alloc_pool (problem_data->reg_pool);
221 free_alloc_pool (problem_data->mw_reg_pool);
222 free_alloc_pool (problem_data->mw_link_pool);
223 bitmap_obstack_release (&problem_data->reg_bitmaps);
224 bitmap_obstack_release (&problem_data->insn_bitmaps);
225 free (df_scan->problem_data);
229 /* Set basic block info. */
232 df_scan_set_bb_info (unsigned int index,
233 struct df_scan_bb_info *bb_info)
235 gcc_assert (df_scan);
236 df_grow_bb_info (df_scan);
237 df_scan->block_info[index] = (void *) bb_info;
241 /* Free basic block info. */
244 df_scan_free_bb_info (basic_block bb, void *vbb_info)
246 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
247 unsigned int bb_index = bb->index;
251 FOR_BB_INSNS (bb, insn)
254 /* Record defs within INSN. */
255 df_insn_delete (bb, INSN_UID (insn));
258 if (bb_index < df_scan->block_info_size)
259 bb_info = df_scan_get_bb_info (bb_index);
261 /* Get rid of any artificial uses or defs. */
262 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
263 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
264 df_ref_chain_delete (bb_info->artificial_defs);
265 df_ref_chain_delete (bb_info->artificial_uses);
266 bb_info->artificial_defs = NULL;
267 bb_info->artificial_uses = NULL;
268 pool_free (df_scan->block_pool, bb_info);
273 /* Allocate the problem data for the scanning problem. This should be
274 called when the problem is created or when the entire function is to
277 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
279 struct df_scan_problem_data *problem_data;
280 unsigned int insn_num = get_max_uid () + 1;
281 unsigned int block_size = 400;
284 /* Given the number of pools, this is really faster than tearing
286 if (df_scan->problem_data)
287 df_scan_free_internal ();
290 = create_alloc_pool ("df_scan_block pool",
291 sizeof (struct df_scan_bb_info),
294 problem_data = XNEW (struct df_scan_problem_data);
295 df_scan->problem_data = problem_data;
296 df_scan->computed = true;
298 problem_data->ref_pool
299 = create_alloc_pool ("df_scan_ref pool",
300 sizeof (struct df_ref), block_size);
301 problem_data->insn_pool
302 = create_alloc_pool ("df_scan_insn pool",
303 sizeof (struct df_insn_info), block_size);
304 problem_data->reg_pool
305 = create_alloc_pool ("df_scan_reg pool",
306 sizeof (struct df_reg_info), block_size);
307 problem_data->mw_reg_pool
308 = create_alloc_pool ("df_scan_mw_reg pool",
309 sizeof (struct df_mw_hardreg), block_size);
310 problem_data->mw_link_pool
311 = create_alloc_pool ("df_scan_mw_link pool",
312 sizeof (struct df_link), block_size);
314 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
315 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
317 insn_num += insn_num / 4;
320 df_grow_insn_info ();
321 df_grow_bb_info (df_scan);
325 unsigned int bb_index = bb->index;
326 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
329 bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
330 df_scan_set_bb_info (bb_index, bb_info);
332 bb_info->artificial_defs = NULL;
333 bb_info->artificial_uses = NULL;
336 df->hardware_regs_used = BITMAP_ALLOC (&problem_data->reg_bitmaps);
337 df->regular_block_artificial_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
338 df->eh_block_artificial_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
339 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
340 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
341 df->insns_to_delete = BITMAP_ALLOC (&problem_data->insn_bitmaps);
342 df->insns_to_rescan = BITMAP_ALLOC (&problem_data->insn_bitmaps);
343 df->insns_to_notes_rescan = BITMAP_ALLOC (&problem_data->insn_bitmaps);
347 /* Free all of the data associated with the scan problem. */
352 if (df_scan->problem_data)
353 df_scan_free_internal ();
355 if (df->blocks_to_analyze)
357 BITMAP_FREE (df->blocks_to_analyze);
358 df->blocks_to_analyze = NULL;
364 /* Dump the preamble for DF_SCAN dump. */
366 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
370 fprintf (file, ";; invalidated by call \t");
371 df_print_regset (file, df_invalidated_by_call);
372 fprintf (file, ";; hardware regs used \t");
373 df_print_regset (file, df->hardware_regs_used);
374 fprintf (file, ";; regular block artificial uses \t");
375 df_print_regset (file, df->regular_block_artificial_uses);
376 fprintf (file, ";; eh block artificial uses \t");
377 df_print_regset (file, df->eh_block_artificial_uses);
378 fprintf (file, ";; entry block defs \t");
379 df_print_regset (file, df->entry_block_defs);
380 fprintf (file, ";; exit block uses \t");
381 df_print_regset (file, df->exit_block_uses);
382 fprintf (file, ";; regs ever live \t");
383 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
384 if (df_regs_ever_live_p (i))
385 fprintf (file, " %d[%s]", i, reg_names[i]);
387 fprintf (file, "\n");
390 /* Dump the bb_info for a given basic block. */
392 df_scan_start_block (basic_block bb, FILE *file)
394 struct df_scan_bb_info *bb_info
395 = df_scan_get_bb_info (bb->index);
399 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
400 df_refs_chain_dump (bb_info->artificial_defs, true, file);
401 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
402 df_refs_chain_dump (bb_info->artificial_uses, true, file);
403 fprintf (file, "\n");
408 FOR_BB_INSNS (bb, insn)
410 df_insn_debug (insn, false, file);
415 static struct df_problem problem_SCAN =
417 DF_SCAN, /* Problem id. */
418 DF_NONE, /* Direction. */
419 df_scan_alloc, /* Allocate the problem specific data. */
420 NULL, /* Reset global information. */
421 df_scan_free_bb_info, /* Free basic block info. */
422 NULL, /* Local compute function. */
423 NULL, /* Init the solution specific data. */
424 NULL, /* Iterative solver. */
425 NULL, /* Confluence operator 0. */
426 NULL, /* Confluence operator n. */
427 NULL, /* Transfer function. */
428 NULL, /* Finalize function. */
429 df_scan_free, /* Free all of the problem information. */
430 NULL, /* Remove this problem from the stack of dataflow problems. */
431 df_scan_start_dump, /* Debugging. */
432 df_scan_start_block, /* Debugging start block. */
433 NULL, /* Debugging end block. */
434 NULL, /* Incremental solution verify start. */
435 NULL, /* Incremental solution verfiy end. */
436 NULL, /* Dependent problem. */
437 TV_DF_SCAN /* Timing variable. */
441 /* Create a new DATAFLOW instance and add it to an existing instance
442 of DF. The returned structure is what is used to get at the
446 df_scan_add_problem (void)
448 df_add_problem (&problem_SCAN);
452 /*----------------------------------------------------------------------------
453 Storage Allocation Utilities
454 ----------------------------------------------------------------------------*/
457 /* First, grow the reg_info information. If the current size is less than
458 the number of psuedos, grow to 25% more than the number of
461 Second, assure that all of the slots up to max_reg_num have been
462 filled with reg_info structures. */
465 df_grow_reg_info (void)
467 unsigned int max_reg = max_reg_num ();
468 unsigned int new_size = max_reg;
469 struct df_scan_problem_data *problem_data
470 = (struct df_scan_problem_data *) df_scan->problem_data;
473 if (df->regs_size < new_size)
475 new_size += new_size / 4;
476 df->def_regs = xrealloc (df->def_regs,
477 new_size *sizeof (struct df_reg_info*));
478 df->use_regs = xrealloc (df->use_regs,
479 new_size *sizeof (struct df_reg_info*));
480 df->eq_use_regs = xrealloc (df->eq_use_regs,
481 new_size *sizeof (struct df_reg_info*));
482 df->def_info.begin = xrealloc (df->def_info.begin,
483 new_size *sizeof (int));
484 df->def_info.count = xrealloc (df->def_info.count,
485 new_size *sizeof (int));
486 df->use_info.begin = xrealloc (df->use_info.begin,
487 new_size *sizeof (int));
488 df->use_info.count = xrealloc (df->use_info.count,
489 new_size *sizeof (int));
490 df->regs_size = new_size;
493 for (i = df->regs_inited; i < max_reg; i++)
495 struct df_reg_info *reg_info;
497 reg_info = pool_alloc (problem_data->reg_pool);
498 memset (reg_info, 0, sizeof (struct df_reg_info));
499 df->def_regs[i] = reg_info;
500 reg_info = pool_alloc (problem_data->reg_pool);
501 memset (reg_info, 0, sizeof (struct df_reg_info));
502 df->use_regs[i] = reg_info;
503 reg_info = pool_alloc (problem_data->reg_pool);
504 memset (reg_info, 0, sizeof (struct df_reg_info));
505 df->eq_use_regs[i] = reg_info;
506 df->def_info.begin[i] = 0;
507 df->def_info.count[i] = 0;
508 df->use_info.begin[i] = 0;
509 df->use_info.count[i] = 0;
512 df->regs_inited = max_reg;
516 /* Grow the ref information. */
519 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
521 if (ref_info->refs_size < new_size)
523 ref_info->refs = xrealloc (ref_info->refs,
524 new_size *sizeof (struct df_ref *));
525 memset (ref_info->refs + ref_info->refs_size, 0,
526 (new_size - ref_info->refs_size) *sizeof (struct df_ref *));
527 ref_info->refs_size = new_size;
532 /* Check and grow the ref information if necessary. This routine
533 guarantees total_size + BITMAP_ADDEND amount of entries in refs
534 array. It updates ref_info->refs_size only and does not change
535 ref_info->total_size. */
538 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
539 unsigned bitmap_addend)
541 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
543 int new_size = ref_info->total_size + bitmap_addend;
544 new_size += ref_info->total_size / 4;
545 df_grow_ref_info (ref_info, new_size);
550 /* Grow the ref information. If the current size is less than the
551 number of instructions, grow to 25% more than the number of
555 df_grow_insn_info (void)
557 unsigned int new_size = get_max_uid () + 1;
558 if (DF_INSN_SIZE () < new_size)
560 new_size += new_size / 4;
561 df->insns = xrealloc (df->insns,
562 new_size *sizeof (struct df_insn_info *));
563 memset (df->insns + df->insns_size, 0,
564 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
565 DF_INSN_SIZE () = new_size;
572 /*----------------------------------------------------------------------------
573 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
574 ----------------------------------------------------------------------------*/
576 /* Rescan all of the block_to_analyze or all of the blocks in the
577 function if df_set_blocks if blocks_to_analyze is NULL; */
580 df_scan_blocks (void)
584 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
585 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
587 df_get_regular_block_artificial_uses (df->regular_block_artificial_uses);
588 df_get_eh_block_artificial_uses (df->eh_block_artificial_uses);
590 bitmap_ior_into (df->eh_block_artificial_uses,
591 df->regular_block_artificial_uses);
593 /* ENTRY and EXIT blocks have special defs/uses. */
594 df_get_entry_block_def_set (df->entry_block_defs);
595 df_record_entry_block_defs (df->entry_block_defs);
596 df_get_exit_block_use_set (df->exit_block_uses);
597 df_record_exit_block_uses (df->exit_block_uses);
598 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
599 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
604 unsigned int bb_index = bb->index;
605 df_bb_refs_record (bb_index, true);
610 /* Create a new ref of type DF_REF_TYPE for register REG at address
611 LOC within INSN of BB. */
614 df_ref_create (rtx reg, rtx *loc, rtx insn,
616 enum df_ref_type ref_type,
617 enum df_ref_flags ref_flags)
620 struct df_reg_info **reg_info;
621 struct df_ref_info *ref_info;
622 struct df_ref **ref_rec;
623 struct df_ref ***ref_rec_ptr;
624 unsigned int count = 0;
629 /* You cannot hack artificial refs. */
631 ref = df_ref_create_structure (NULL, reg, loc, bb, insn,
632 ref_type, ref_flags);
634 if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
636 reg_info = df->def_regs;
637 ref_info = &df->def_info;
638 ref_rec_ptr = &DF_INSN_DEFS (insn);
639 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
641 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
643 reg_info = df->eq_use_regs;
644 ref_info = &df->use_info;
645 ref_rec_ptr = &DF_INSN_EQ_USES (insn);
646 switch (ref_info->ref_order)
648 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
649 case DF_REF_ORDER_BY_REG_WITH_NOTES:
650 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
654 add_to_table = false;
660 reg_info = df->use_regs;
661 ref_info = &df->use_info;
662 ref_rec_ptr = &DF_INSN_USES (insn);
663 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
666 /* Do not add if ref is not in the right blocks. */
667 if (add_to_table && df->analyze_subset)
668 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
670 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
673 switch (ref_info->ref_order)
675 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
676 case DF_REF_ORDER_BY_REG_WITH_NOTES:
677 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
678 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
681 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
685 ref_rec = *ref_rec_ptr;
692 ref_rec = *ref_rec_ptr;
695 ref_rec = xrealloc (ref_rec, (count+2) * sizeof (struct df_ref*));
696 *ref_rec_ptr = ref_rec;
697 ref_rec[count] = ref;
698 ref_rec[count+1] = NULL;
699 qsort (ref_rec, count + 1, sizeof (struct df_ref *), df_ref_compare);
703 struct df_ref **ref_rec = XNEWVEC (struct df_ref*, 2);
706 *ref_rec_ptr = ref_rec;
712 fprintf (dump_file, "adding ref ");
713 df_ref_debug (ref, dump_file);
716 /* By adding the ref directly, df_insn_rescan my not find any
717 differences even though the block will have changed. So we need
718 to mark the block dirty ourselves. */
719 df_set_bb_dirty (bb);
726 /*----------------------------------------------------------------------------
727 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
728 ----------------------------------------------------------------------------*/
731 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
732 Also delete the def-use or use-def chain if it exists. */
735 df_reg_chain_unlink (struct df_ref *ref)
737 struct df_ref *next = DF_REF_NEXT_REG (ref);
738 struct df_ref *prev = DF_REF_PREV_REG (ref);
739 struct df_scan_problem_data *problem_data
740 = (struct df_scan_problem_data *) df_scan->problem_data;
741 int id = DF_REF_ID (ref);
742 struct df_reg_info *reg_info;
743 struct df_ref **refs = NULL;
745 if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
747 reg_info = DF_REG_DEF_GET (DF_REF_REGNO (ref));
748 refs = df->def_info.refs;
752 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
754 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
755 switch (df->use_info.ref_order)
757 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
758 case DF_REF_ORDER_BY_REG_WITH_NOTES:
759 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
760 refs = df->use_info.refs;
768 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
769 refs = df->use_info.refs;
775 if (df->analyze_subset)
777 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BB (ref)->index))
784 /* Delete any def-use or use-def chains that start here. It is
785 possible that there is trash in this field. This happens for
786 insns that have been deleted when rescanning has been deferred
787 and the chain problem has also been deleted. The chain tear down
788 code skips deleted insns. */
789 if (df_chain && DF_REF_CHAIN (ref))
790 df_chain_unlink (ref);
793 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
795 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
796 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
799 /* Unlink from the reg chain. If there is no prev, this is the
800 first of the list. If not, just join the next and prev. */
802 DF_REF_NEXT_REG (prev) = next;
805 gcc_assert (reg_info->reg_chain == ref);
806 reg_info->reg_chain = next;
809 DF_REF_PREV_REG (next) = prev;
811 pool_free (problem_data->ref_pool, ref);
815 /* Remove REF from VEC. */
818 df_ref_compress_rec (struct df_ref ***vec_ptr, struct df_ref *ref)
820 struct df_ref **vec = *vec_ptr;
824 while (*vec && *vec != ref)
836 *vec_ptr = df_null_ref_rec;
841 /* Unlink REF from all def-use/use-def chains, etc. */
844 df_ref_remove (struct df_ref *ref)
849 fprintf (dump_file, "removing ref ");
850 df_ref_debug (ref, dump_file);
854 if (DF_REF_REG_DEF_P (ref))
856 if (DF_REF_IS_ARTIFICIAL (ref))
858 struct df_scan_bb_info *bb_info
859 = df_scan_get_bb_info (DF_REF_BB (ref)->index);
860 df_ref_compress_rec (&bb_info->artificial_defs, ref);
864 unsigned int uid = DF_REF_INSN_UID (ref);
865 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
866 df_ref_compress_rec (&insn_rec->defs, ref);
871 if (DF_REF_IS_ARTIFICIAL (ref))
873 struct df_scan_bb_info *bb_info
874 = df_scan_get_bb_info (DF_REF_BB (ref)->index);
875 df_ref_compress_rec (&bb_info->artificial_uses, ref);
879 unsigned int uid = DF_REF_INSN_UID (ref);
880 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
882 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
883 df_ref_compress_rec (&insn_rec->eq_uses, ref);
885 df_ref_compress_rec (&insn_rec->uses, ref);
889 /* By deleting the ref directly, df_insn_rescan my not find any
890 differences even though the block will have changed. So we need
891 to mark the block dirty ourselves. */
892 df_set_bb_dirty (DF_REF_BB (ref));
893 df_reg_chain_unlink (ref);
897 /* Create the insn record for INSN. If there was one there, zero it
900 struct df_insn_info *
901 df_insn_create_insn_record (rtx insn)
903 struct df_scan_problem_data *problem_data
904 = (struct df_scan_problem_data *) df_scan->problem_data;
905 struct df_insn_info *insn_rec;
907 df_grow_insn_info ();
908 insn_rec = DF_INSN_GET (insn);
911 insn_rec = pool_alloc (problem_data->insn_pool);
912 DF_INSN_SET (insn, insn_rec);
914 memset (insn_rec, 0, sizeof (struct df_insn_info));
915 insn_rec->insn = insn;
920 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
923 df_ref_chain_delete_du_chain (struct df_ref **ref_rec)
927 struct df_ref *ref = *ref_rec;
928 /* CHAIN is allocated by DF_CHAIN. So make sure to
929 pass df_scan instance for the problem. */
930 if (DF_REF_CHAIN (ref))
931 df_chain_unlink (ref);
937 /* Delete all refs in the ref chain. */
940 df_ref_chain_delete (struct df_ref **ref_rec)
942 struct df_ref **start = ref_rec;
945 df_reg_chain_unlink (*ref_rec);
949 /* If the list is empty, it has a special shared element that is not
956 /* Delete the hardreg chain. */
959 df_mw_hardreg_chain_delete (struct df_mw_hardreg **hardregs)
961 struct df_scan_problem_data *problem_data;
966 problem_data = (struct df_scan_problem_data *) df_scan->problem_data;
970 pool_free (problem_data->mw_reg_pool, *hardregs);
976 /* Delete all of the refs information from INSN. BB must be passed in
977 except when called from df_process_deferred_rescans to mark the block
981 df_insn_delete (basic_block bb, unsigned int uid)
983 struct df_insn_info *insn_info = NULL;
987 df_grow_bb_info (df_scan);
990 /* The block must be marked as dirty now, rather than later as in
991 df_insn_rescan and df_notes_rescan because it may not be there at
992 rescanning time and the mark would blow up. */
994 df_set_bb_dirty (bb);
996 insn_info = DF_INSN_UID_SAFE_GET (uid);
998 /* The client has deferred rescanning. */
999 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1003 bitmap_clear_bit (df->insns_to_rescan, uid);
1004 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1005 bitmap_set_bit (df->insns_to_delete, uid);
1008 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
1013 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
1015 bitmap_clear_bit (df->insns_to_delete, uid);
1016 bitmap_clear_bit (df->insns_to_rescan, uid);
1017 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1020 struct df_scan_problem_data *problem_data
1021 = (struct df_scan_problem_data *) df_scan->problem_data;
1023 /* In general, notes do not have the insn_info fields
1024 initialized. However, combine deletes insns by changing them
1025 to notes. How clever. So we cannot just check if it is a
1026 valid insn before short circuiting this code, we need to see
1027 if we actually initialized it. */
1028 if (insn_info->defs)
1030 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1034 df_ref_chain_delete_du_chain (insn_info->defs);
1035 df_ref_chain_delete_du_chain (insn_info->uses);
1036 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1039 df_ref_chain_delete (insn_info->defs);
1040 df_ref_chain_delete (insn_info->uses);
1041 df_ref_chain_delete (insn_info->eq_uses);
1043 pool_free (problem_data->insn_pool, insn_info);
1044 DF_INSN_UID_SET (uid, NULL);
1049 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
1052 df_free_collection_rec (struct df_collection_rec *collection_rec)
1054 struct df_scan_problem_data *problem_data
1055 = (struct df_scan_problem_data *) df_scan->problem_data;
1056 struct df_ref **ref;
1057 struct df_mw_hardreg **mw;
1059 if (collection_rec->def_vec)
1060 for (ref = collection_rec->def_vec; *ref; ref++)
1061 pool_free (problem_data->ref_pool, *ref);
1062 if (collection_rec->use_vec)
1063 for (ref = collection_rec->use_vec; *ref; ref++)
1064 pool_free (problem_data->ref_pool, *ref);
1065 if (collection_rec->eq_use_vec)
1066 for (ref = collection_rec->eq_use_vec; *ref; ref++)
1067 pool_free (problem_data->ref_pool, *ref);
1068 if (collection_rec->mw_vec)
1069 for (mw = collection_rec->mw_vec; *mw; mw++)
1070 pool_free (problem_data->mw_reg_pool, *mw);
1074 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1077 df_insn_rescan (rtx insn)
1079 unsigned int uid = INSN_UID (insn);
1080 struct df_insn_info *insn_info = NULL;
1081 basic_block bb = BLOCK_FOR_INSN (insn);
1082 struct df_collection_rec collection_rec;
1083 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
1084 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
1085 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
1086 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
1088 if ((!df) || (!INSN_P (insn)))
1094 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1098 /* The client has disabled rescanning and plans to do it itself. */
1099 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1102 df_grow_bb_info (df_scan);
1103 df_grow_reg_info ();
1105 insn_info = DF_INSN_UID_SAFE_GET (uid);
1107 /* The client has deferred rescanning. */
1108 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1112 insn_info = df_insn_create_insn_record (insn);
1113 insn_info->defs = df_null_ref_rec;
1114 insn_info->uses = df_null_ref_rec;
1115 insn_info->eq_uses = df_null_ref_rec;
1116 insn_info->mw_hardregs = df_null_mw_rec;
1119 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1121 bitmap_clear_bit (df->insns_to_delete, uid);
1122 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1123 bitmap_set_bit (df->insns_to_rescan, INSN_UID (insn));
1127 bitmap_clear_bit (df->insns_to_delete, uid);
1128 bitmap_clear_bit (df->insns_to_rescan, uid);
1129 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1132 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1133 /* If there's no change, return false. */
1136 df_free_collection_rec (&collection_rec);
1138 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1142 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1144 /* There's change - we need to delete the existing info. */
1145 df_insn_delete (NULL, uid);
1146 df_insn_create_insn_record (insn);
1150 df_insn_create_insn_record (insn);
1151 df_insn_refs_collect (&collection_rec, bb, insn);
1153 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1156 df_refs_add_to_chains (&collection_rec, bb, insn);
1157 df_set_bb_dirty (bb);
1162 /* Rescan all of the insns in the function. Note that the artificial
1163 uses and defs are not touched. This function will destroy def-se
1164 or use-def chains. */
1167 df_insn_rescan_all (void)
1169 bool no_insn_rescan = false;
1170 bool defer_insn_rescan = false;
1174 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1176 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1178 df_clear_flags (DF_NO_INSN_RESCAN);
1179 no_insn_rescan = true;
1182 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1184 df_clear_flags (DF_DEFER_INSN_RESCAN);
1185 defer_insn_rescan = true;
1188 bitmap_copy (tmp, df->insns_to_delete);
1189 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1191 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1193 df_insn_delete (NULL, uid);
1197 bitmap_clear (df->insns_to_delete);
1198 bitmap_clear (df->insns_to_rescan);
1199 bitmap_clear (df->insns_to_notes_rescan);
1204 FOR_BB_INSNS (bb, insn)
1206 df_insn_rescan (insn);
1211 df_set_flags (DF_NO_INSN_RESCAN);
1212 if (defer_insn_rescan)
1213 df_set_flags (DF_DEFER_INSN_RESCAN);
1217 /* Process all of the deferred rescans or deletions. */
1220 df_process_deferred_rescans (void)
1222 bool no_insn_rescan = false;
1223 bool defer_insn_rescan = false;
1226 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1228 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1230 df_clear_flags (DF_NO_INSN_RESCAN);
1231 no_insn_rescan = true;
1234 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1236 df_clear_flags (DF_DEFER_INSN_RESCAN);
1237 defer_insn_rescan = true;
1241 fprintf (dump_file, "starting the processing of deferred insns\n");
1243 bitmap_copy (tmp, df->insns_to_delete);
1244 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1246 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1248 df_insn_delete (NULL, uid);
1251 bitmap_copy (tmp, df->insns_to_rescan);
1252 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1254 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1256 df_insn_rescan (insn_info->insn);
1259 bitmap_copy (tmp, df->insns_to_notes_rescan);
1260 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1262 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1264 df_notes_rescan (insn_info->insn);
1268 fprintf (dump_file, "ending the processing of deferred insns\n");
1271 bitmap_clear (df->insns_to_delete);
1272 bitmap_clear (df->insns_to_rescan);
1273 bitmap_clear (df->insns_to_notes_rescan);
1276 df_set_flags (DF_NO_INSN_RESCAN);
1277 if (defer_insn_rescan)
1278 df_set_flags (DF_DEFER_INSN_RESCAN);
1280 /* If someone changed regs_ever_live during this pass, fix up the
1281 entry and exit blocks. */
1282 if (df->redo_entry_and_exit)
1284 df_update_entry_exit_and_calls ();
1285 df->redo_entry_and_exit = false;
1290 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1291 the uses if INCLUDE_USES. Include the eq_uses if
1295 df_count_refs (bool include_defs, bool include_uses,
1296 bool include_eq_uses)
1300 unsigned int m = df->regs_inited;
1302 for (regno = 0; regno < m; regno++)
1305 size += DF_REG_DEF_COUNT (regno);
1307 size += DF_REG_USE_COUNT (regno);
1308 if (include_eq_uses)
1309 size += DF_REG_EQ_USE_COUNT (regno);
1315 /* Take build ref table for either the uses or defs from the reg-use
1316 or reg-def chains. This version processes the refs in reg order
1317 which is likely to be best if processing the whole function. */
1320 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1323 bool include_eq_uses)
1325 unsigned int m = df->regs_inited;
1327 unsigned int offset = 0;
1330 if (df->changeable_flags & DF_NO_HARD_REGS)
1332 start = FIRST_PSEUDO_REGISTER;
1333 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1334 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1339 ref_info->total_size
1340 = df_count_refs (include_defs, include_uses, include_eq_uses);
1342 df_check_and_grow_ref_info (ref_info, 1);
1344 for (regno = start; regno < m; regno++)
1347 ref_info->begin[regno] = offset;
1350 struct df_ref *ref = DF_REG_DEF_CHAIN (regno);
1353 ref_info->refs[offset] = ref;
1354 DF_REF_ID (ref) = offset++;
1356 ref = DF_REF_NEXT_REG (ref);
1357 gcc_assert (offset < ref_info->refs_size);
1362 struct df_ref *ref = DF_REG_USE_CHAIN (regno);
1365 ref_info->refs[offset] = ref;
1366 DF_REF_ID (ref) = offset++;
1368 ref = DF_REF_NEXT_REG (ref);
1369 gcc_assert (offset < ref_info->refs_size);
1372 if (include_eq_uses)
1374 struct df_ref *ref = DF_REG_EQ_USE_CHAIN (regno);
1377 ref_info->refs[offset] = ref;
1378 DF_REF_ID (ref) = offset++;
1380 ref = DF_REF_NEXT_REG (ref);
1381 gcc_assert (offset < ref_info->refs_size);
1384 ref_info->count[regno] = count;
1387 /* The bitmap size is not decremented when refs are deleted. So
1388 reset it now that we have squished out all of the empty
1390 ref_info->table_size = offset;
1394 /* Take build ref table for either the uses or defs from the reg-use
1395 or reg-def chains. This version processes the refs in insn order
1396 which is likely to be best if processing some segment of the
1400 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1403 bool include_eq_uses)
1406 unsigned int bb_index;
1407 unsigned int m = df->regs_inited;
1408 unsigned int offset = 0;
1411 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1413 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1414 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1416 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1417 df_check_and_grow_ref_info (ref_info, 1);
1419 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1421 basic_block bb = BASIC_BLOCK (bb_index);
1423 struct df_ref **ref_rec;
1426 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1428 unsigned int regno = DF_REF_REGNO (*ref_rec);
1429 ref_info->count[regno]++;
1432 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1434 unsigned int regno = DF_REF_REGNO (*ref_rec);
1435 ref_info->count[regno]++;
1438 FOR_BB_INSNS (bb, insn)
1442 unsigned int uid = INSN_UID (insn);
1445 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1447 unsigned int regno = DF_REF_REGNO (*ref_rec);
1448 ref_info->count[regno]++;
1451 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1453 unsigned int regno = DF_REF_REGNO (*ref_rec);
1454 ref_info->count[regno]++;
1456 if (include_eq_uses)
1457 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1459 unsigned int regno = DF_REF_REGNO (*ref_rec);
1460 ref_info->count[regno]++;
1466 for (r = start; r < m; r++)
1468 ref_info->begin[r] = offset;
1469 offset += ref_info->count[r];
1470 ref_info->count[r] = 0;
1473 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1475 basic_block bb = BASIC_BLOCK (bb_index);
1477 struct df_ref **ref_rec;
1480 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1482 struct df_ref *ref = *ref_rec;
1483 unsigned int regno = DF_REF_REGNO (ref);
1487 = ref_info->begin[regno] + ref_info->count[regno]++;
1488 DF_REF_ID (ref) = id;
1489 ref_info->refs[id] = ref;
1493 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1495 struct df_ref *ref = *ref_rec;
1496 unsigned int regno = DF_REF_REGNO (ref);
1500 = ref_info->begin[regno] + ref_info->count[regno]++;
1501 DF_REF_ID (ref) = id;
1502 ref_info->refs[id] = ref;
1506 FOR_BB_INSNS (bb, insn)
1510 unsigned int uid = INSN_UID (insn);
1513 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1515 struct df_ref *ref = *ref_rec;
1516 unsigned int regno = DF_REF_REGNO (ref);
1520 = ref_info->begin[regno] + ref_info->count[regno]++;
1521 DF_REF_ID (ref) = id;
1522 ref_info->refs[id] = ref;
1526 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1528 struct df_ref *ref = *ref_rec;
1529 unsigned int regno = DF_REF_REGNO (ref);
1533 = ref_info->begin[regno] + ref_info->count[regno]++;
1534 DF_REF_ID (ref) = id;
1535 ref_info->refs[id] = ref;
1538 if (include_eq_uses)
1539 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1541 struct df_ref *ref = *ref_rec;
1542 unsigned int regno = DF_REF_REGNO (ref);
1546 = ref_info->begin[regno] + ref_info->count[regno]++;
1547 DF_REF_ID (ref) = id;
1548 ref_info->refs[id] = ref;
1555 /* The bitmap size is not decremented when refs are deleted. So
1556 reset it now that we have squished out all of the empty
1559 ref_info->table_size = offset;
1562 /* Take build ref table for either the uses or defs from the reg-use
1563 or reg-def chains. */
1566 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1569 bool include_eq_uses)
1571 if (df->analyze_subset)
1572 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1573 include_uses, include_eq_uses);
1575 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1576 include_uses, include_eq_uses);
1580 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1582 df_add_refs_to_table (unsigned int offset,
1583 struct df_ref_info *ref_info,
1584 struct df_ref **ref_vec)
1588 struct df_ref *ref = *ref_vec;
1589 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
1590 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1592 ref_info->refs[offset] = ref;
1593 DF_REF_ID (*ref_vec) = offset++;
1601 /* Count the number of refs in all of the insns of BB. Include the
1602 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1603 eq_uses if INCLUDE_EQ_USES. */
1606 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1607 struct df_ref_info *ref_info,
1608 bool include_defs, bool include_uses,
1609 bool include_eq_uses)
1614 offset = df_add_refs_to_table (offset, ref_info,
1615 df_get_artificial_defs (bb->index));
1617 offset = df_add_refs_to_table (offset, ref_info,
1618 df_get_artificial_uses (bb->index));
1620 FOR_BB_INSNS (bb, insn)
1623 unsigned int uid = INSN_UID (insn);
1625 offset = df_add_refs_to_table (offset, ref_info,
1626 DF_INSN_UID_DEFS (uid));
1628 offset = df_add_refs_to_table (offset, ref_info,
1629 DF_INSN_UID_USES (uid));
1630 if (include_eq_uses)
1631 offset = df_add_refs_to_table (offset, ref_info,
1632 DF_INSN_UID_EQ_USES (uid));
1638 /* Organize the refs by insn into the table in REF_INFO. If
1639 blocks_to_analyze is defined, use that set, otherwise the entire
1640 program. Include the defs if INCLUDE_DEFS. Include the uses if
1641 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1644 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1645 bool include_defs, bool include_uses,
1646 bool include_eq_uses)
1649 unsigned int offset = 0;
1651 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1652 df_check_and_grow_ref_info (ref_info, 1);
1653 if (df->blocks_to_analyze)
1658 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1660 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK (index), offset, ref_info,
1661 include_defs, include_uses,
1665 ref_info->table_size = offset;
1670 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1671 include_defs, include_uses,
1673 ref_info->table_size = offset;
1678 /* If the use refs in DF are not organized, reorganize them. */
1681 df_maybe_reorganize_use_refs (enum df_ref_order order)
1683 if (order == df->use_info.ref_order)
1688 case DF_REF_ORDER_BY_REG:
1689 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1692 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1693 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1696 case DF_REF_ORDER_BY_INSN:
1697 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1700 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1701 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1704 case DF_REF_ORDER_NO_TABLE:
1705 free (df->use_info.refs);
1706 df->use_info.refs = NULL;
1707 df->use_info.refs_size = 0;
1710 case DF_REF_ORDER_UNORDERED:
1711 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1716 df->use_info.ref_order = order;
1720 /* If the def refs in DF are not organized, reorganize them. */
1723 df_maybe_reorganize_def_refs (enum df_ref_order order)
1725 if (order == df->def_info.ref_order)
1730 case DF_REF_ORDER_BY_REG:
1731 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1734 case DF_REF_ORDER_BY_INSN:
1735 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1738 case DF_REF_ORDER_NO_TABLE:
1739 free (df->def_info.refs);
1740 df->def_info.refs = NULL;
1741 df->def_info.refs_size = 0;
1744 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1745 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1746 case DF_REF_ORDER_UNORDERED:
1747 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1752 df->def_info.ref_order = order;
1756 /* Change the BB of all refs in the ref chain to NEW_BB.
1757 Assumes that all refs in the chain have the same BB.
1758 If changed, return the original bb the chain belonged to
1760 If no change, return NEW_BB.
1761 If something's wrong, it will return NULL. */
1764 df_ref_chain_change_bb (struct df_ref **ref_rec,
1770 struct df_ref *ref = *ref_rec;
1772 if (DF_REF_BB (ref) == new_bb)
1776 gcc_assert (old_bb == NULL || DF_REF_BB (ref) == old_bb);
1777 old_bb = DF_REF_BB (ref);
1778 DF_REF_BB (ref) = new_bb;
1787 /* Change all of the basic block references in INSN to use the insn's
1788 current basic block. This function is called from routines that move
1789 instructions from one block to another. */
1792 df_insn_change_bb (rtx insn)
1794 basic_block new_bb = BLOCK_FOR_INSN (insn);
1795 basic_block old_bb = NULL;
1796 struct df_insn_info *insn_info;
1797 unsigned int uid = INSN_UID (insn);
1803 fprintf (dump_file, "changing bb of uid %d\n", uid);
1805 insn_info = DF_INSN_UID_SAFE_GET (uid);
1806 if (insn_info == NULL)
1809 fprintf (dump_file, " unscanned insn\n");
1810 df_insn_rescan (insn);
1817 old_bb = df_ref_chain_change_bb (insn_info->defs, old_bb, new_bb);
1818 if (old_bb == new_bb)
1821 old_bb = df_ref_chain_change_bb (insn_info->uses, old_bb, new_bb);
1822 if (old_bb == new_bb)
1825 old_bb = df_ref_chain_change_bb (insn_info->eq_uses, old_bb, new_bb);
1826 if (old_bb == new_bb)
1829 df_set_bb_dirty (new_bb);
1833 fprintf (dump_file, " from %d to %d\n",
1834 old_bb->index, new_bb->index);
1835 df_set_bb_dirty (old_bb);
1839 fprintf (dump_file, " to %d\n", new_bb->index);
1843 /* Helper function for df_ref_change_reg_with_loc. */
1846 df_ref_change_reg_with_loc_1 (struct df_reg_info *old, struct df_reg_info *new,
1847 int new_regno, rtx loc)
1849 struct df_ref *the_ref = old->reg_chain;
1853 if (DF_REF_LOC(the_ref) && (*DF_REF_LOC(the_ref) == loc))
1855 struct df_ref *next_ref = the_ref->next_reg;
1856 struct df_ref *prev_ref = the_ref->prev_reg;
1857 struct df_ref **ref_vec, **ref_vec_t;
1858 unsigned int count = 0;
1860 DF_REF_REGNO (the_ref) = new_regno;
1861 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1863 /* Pull the_ref out of the old regno chain. */
1865 prev_ref->next_reg = next_ref;
1867 old->reg_chain = next_ref;
1869 next_ref->prev_reg = prev_ref;
1872 /* Put the ref into the new regno chain. */
1873 the_ref->prev_reg = NULL;
1874 the_ref->next_reg = new->reg_chain;
1876 new->reg_chain->prev_reg = the_ref;
1877 new->reg_chain = the_ref;
1879 df_set_bb_dirty (DF_REF_BB (the_ref));
1881 /* Need to resort the record that the ref was in because the
1882 regno is a sorting key. First, find the right record. */
1883 if (DF_REF_IS_ARTIFICIAL (the_ref))
1885 unsigned int bb_index = DF_REF_BB (the_ref)->index;
1886 if (DF_REF_REG_DEF_P (the_ref))
1887 ref_vec = df_get_artificial_defs (bb_index);
1889 ref_vec = df_get_artificial_uses (bb_index);
1893 struct df_insn_info *insn_info
1894 = DF_INSN_GET (DF_REF_INSN (the_ref));
1895 if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1896 ref_vec = insn_info->eq_uses;
1898 ref_vec = insn_info->uses;
1900 fprintf (dump_file, "changing reg in insn %d\n",
1901 INSN_UID (DF_REF_INSN (the_ref)));
1903 ref_vec_t = ref_vec;
1905 /* Find the length. */
1911 qsort (ref_vec, count, sizeof (struct df_ref *), df_ref_compare);
1916 the_ref = the_ref->next_reg;
1921 /* Change the regno of all refs that contained LOC from OLD_REGNO to
1922 NEW_REGNO. Refs that do not match LOC are not changed. This call
1923 is to support the SET_REGNO macro. */
1926 df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
1928 if ((!df) || (old_regno == -1) || (old_regno == new_regno))
1931 df_grow_reg_info ();
1933 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1934 DF_REG_DEF_GET (new_regno), new_regno, loc);
1935 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1936 DF_REG_USE_GET (new_regno), new_regno, loc);
1937 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1938 DF_REG_EQ_USE_GET (new_regno), new_regno, loc);
1942 /* Delete the mw_hardregs that point into the eq_notes. */
1945 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1947 struct df_mw_hardreg **mw_vec = insn_info->mw_hardregs;
1948 unsigned int deleted = 0;
1949 unsigned int count = 0;
1950 struct df_scan_problem_data *problem_data
1951 = (struct df_scan_problem_data *) df_scan->problem_data;
1958 if ((*mw_vec)->flags & DF_REF_IN_NOTE)
1960 struct df_mw_hardreg **temp_vec = mw_vec;
1962 pool_free (problem_data->mw_reg_pool, *mw_vec);
1964 /* Shove the remaining ones down one to fill the gap. While
1965 this looks n**2, it is highly unusual to have any mw regs
1966 in eq_notes and the chances of more than one are almost
1970 *temp_vec = *(temp_vec + 1);
1984 free (insn_info->mw_hardregs);
1985 insn_info->mw_hardregs = df_null_mw_rec;
1992 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1995 df_notes_rescan (rtx insn)
1997 struct df_insn_info *insn_info;
1998 unsigned int uid = INSN_UID (insn);
2003 /* The client has disabled rescanning and plans to do it itself. */
2004 if (df->changeable_flags & DF_NO_INSN_RESCAN)
2007 df_grow_bb_info (df_scan);
2008 df_grow_reg_info ();
2010 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID(insn));
2012 /* The client has deferred rescanning. */
2013 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
2017 insn_info = df_insn_create_insn_record (insn);
2018 insn_info->defs = df_null_ref_rec;
2019 insn_info->uses = df_null_ref_rec;
2020 insn_info->eq_uses = df_null_ref_rec;
2021 insn_info->mw_hardregs = df_null_mw_rec;
2024 bitmap_clear_bit (df->insns_to_delete, uid);
2025 /* If the insn is set to be rescanned, it does not need to also
2026 be notes rescanned. */
2027 if (!bitmap_bit_p (df->insns_to_rescan, uid))
2028 bitmap_set_bit (df->insns_to_notes_rescan, INSN_UID (insn));
2032 bitmap_clear_bit (df->insns_to_delete, uid);
2033 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
2037 basic_block bb = BLOCK_FOR_INSN (insn);
2039 struct df_collection_rec collection_rec;
2040 unsigned int num_deleted;
2042 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
2043 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
2044 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 1000);
2046 num_deleted = df_mw_hardreg_chain_delete_eq_uses (insn_info);
2047 df_ref_chain_delete (insn_info->eq_uses);
2048 insn_info->eq_uses = NULL;
2050 /* Process REG_EQUIV/REG_EQUAL notes */
2051 for (note = REG_NOTES (insn); note;
2052 note = XEXP (note, 1))
2054 switch (REG_NOTE_KIND (note))
2058 df_uses_record (&collection_rec,
2059 &XEXP (note, 0), DF_REF_REG_USE,
2060 bb, insn, DF_REF_IN_NOTE);
2066 /* Find some place to put any new mw_hardregs. */
2067 df_canonize_collection_rec (&collection_rec);
2068 if (collection_rec.next_mw)
2070 unsigned int count = 0;
2071 struct df_mw_hardreg **mw_rec = insn_info->mw_hardregs;
2080 /* Append to the end of the existing record after
2081 expanding it if necessary. */
2082 if (collection_rec.next_mw > num_deleted)
2084 insn_info->mw_hardregs =
2085 xrealloc (insn_info->mw_hardregs,
2086 (count + 1 + collection_rec.next_mw)
2087 * sizeof (struct df_ref*));
2089 memcpy (&insn_info->mw_hardregs[count], collection_rec.mw_vec,
2090 (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2091 qsort (insn_info->mw_hardregs, count + collection_rec.next_mw,
2092 sizeof (struct df_mw_hardreg *), df_mw_compare);
2096 /* No vector there. */
2097 insn_info->mw_hardregs
2098 = XNEWVEC (struct df_mw_hardreg*,
2099 count + 1 + collection_rec.next_mw);
2100 memcpy (insn_info->mw_hardregs, collection_rec.mw_vec,
2101 (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2104 /* Get rid of the mw_rec so that df_refs_add_to_chains will
2106 collection_rec.mw_vec = NULL;
2107 collection_rec.next_mw = 0;
2108 df_refs_add_to_chains (&collection_rec, bb, insn);
2111 df_insn_rescan (insn);
2116 /*----------------------------------------------------------------------------
2117 Hard core instruction scanning code. No external interfaces here,
2118 just a lot of routines that look inside insns.
2119 ----------------------------------------------------------------------------*/
2122 /* Return true if the contents of two df_ref's are identical.
2123 It ignores DF_REF_MARKER. */
2126 df_ref_equal_p (struct df_ref *ref1, struct df_ref *ref2)
2130 return (ref1 == ref2) ||
2131 (DF_REF_REG (ref1) == DF_REF_REG (ref2)
2132 && DF_REF_REGNO (ref1) == DF_REF_REGNO (ref2)
2133 && DF_REF_LOC (ref1) == DF_REF_LOC (ref2)
2134 && DF_REF_INSN (ref1) == DF_REF_INSN (ref2)
2135 && DF_REF_TYPE (ref1) == DF_REF_TYPE (ref2)
2136 && ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2137 == (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2138 && DF_REF_BB (ref1) == DF_REF_BB (ref2));
2142 /* Compare REF1 and REF2 for sorting. This is only called from places
2143 where all of the refs are of the same type, in the same insn, and
2144 have the same bb. So these fields are not checked. */
2147 df_ref_compare (const void *r1, const void *r2)
2149 const struct df_ref *ref1 = *(struct df_ref **)r1;
2150 const struct df_ref *ref2 = *(struct df_ref **)r2;
2155 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2156 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2158 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2159 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2161 if ((DF_REF_REG (ref1) != DF_REF_REG (ref2))
2162 || (DF_REF_LOC (ref1) != DF_REF_LOC (ref2)))
2163 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2165 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2167 /* If two refs are identical except that one of them has is from
2168 a mw and one is not, we need to have the one with the mw
2170 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2171 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2172 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2173 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2182 df_swap_refs (struct df_ref **ref_vec, int i, int j)
2184 struct df_ref *tmp = ref_vec[i];
2185 ref_vec[i] = ref_vec[j];
2189 /* Sort and compress a set of refs. */
2192 df_sort_and_compress_refs (struct df_ref **ref_vec, unsigned int count)
2194 struct df_scan_problem_data *problem_data
2195 = (struct df_scan_problem_data *) df_scan->problem_data;
2197 unsigned int dist = 0;
2199 ref_vec[count] = NULL;
2200 /* If there are 1 or 0 elements, there is nothing to do. */
2203 else if (count == 2)
2205 if (df_ref_compare (&ref_vec[0], &ref_vec[1]) > 0)
2206 df_swap_refs (ref_vec, 0, 1);
2210 for (i = 0; i < count - 1; i++)
2211 if (df_ref_compare (&ref_vec[i], &ref_vec[i+1]) >= 0)
2213 /* If the array is already strictly ordered,
2214 which is the most common case for large COUNT case
2215 (which happens for CALL INSNs),
2216 no need to sort and filter out duplicate.
2217 Simply return the count.
2218 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2219 of DF_REF_COMPARE. */
2222 qsort (ref_vec, count, sizeof (struct df_ref *), df_ref_compare);
2225 for (i=0; i<count-dist; i++)
2227 /* Find the next ref that is not equal to the current ref. */
2228 while (df_ref_equal_p (ref_vec[i], ref_vec[i + dist + 1]))
2230 pool_free (problem_data->ref_pool, ref_vec[i + dist + 1]);
2233 /* Copy it down to the next position. */
2235 ref_vec[i+1] = ref_vec[i + dist + 1];
2239 ref_vec[count] = NULL;
2244 /* Return true if the contents of two df_ref's are identical.
2245 It ignores DF_REF_MARKER. */
2248 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2252 return (mw1 == mw2) ||
2253 (mw1->mw_reg == mw2->mw_reg
2254 && mw1->type == mw2->type
2255 && mw1->flags == mw2->flags
2256 && mw1->start_regno == mw2->start_regno
2257 && mw1->end_regno == mw2->end_regno);
2261 /* Compare MW1 and MW2 for sorting. */
2264 df_mw_compare (const void *m1, const void *m2)
2266 const struct df_mw_hardreg *mw1 = *(struct df_mw_hardreg **)m1;
2267 const struct df_mw_hardreg *mw2 = *(struct df_mw_hardreg **)m2;
2272 if (mw1->type != mw2->type)
2273 return mw1->type - mw2->type;
2275 if (mw1->flags != mw2->flags)
2276 return mw1->flags - mw2->flags;
2278 if (mw1->start_regno != mw2->start_regno)
2279 return mw1->start_regno - mw2->start_regno;
2281 if (mw1->end_regno != mw2->end_regno)
2282 return mw1->end_regno - mw2->end_regno;
2284 if (mw1->mw_reg != mw2->mw_reg)
2285 return mw1->mw_order - mw2->mw_order;
2291 /* Sort and compress a set of refs. */
2294 df_sort_and_compress_mws (struct df_mw_hardreg **mw_vec, unsigned int count)
2296 struct df_scan_problem_data *problem_data
2297 = (struct df_scan_problem_data *) df_scan->problem_data;
2299 unsigned int dist = 0;
2300 mw_vec[count] = NULL;
2304 else if (count == 2)
2306 if (df_mw_compare (&mw_vec[0], &mw_vec[1]) > 0)
2308 struct df_mw_hardreg *tmp = mw_vec[0];
2309 mw_vec[0] = mw_vec[1];
2314 qsort (mw_vec, count, sizeof (struct df_mw_hardreg *), df_mw_compare);
2316 for (i=0; i<count-dist; i++)
2318 /* Find the next ref that is not equal to the current ref. */
2319 while (df_mw_equal_p (mw_vec[i], mw_vec[i + dist + 1]))
2321 pool_free (problem_data->mw_reg_pool, mw_vec[i + dist + 1]);
2324 /* Copy it down to the next position. */
2326 mw_vec[i+1] = mw_vec[i + dist + 1];
2330 mw_vec[count] = NULL;
2335 /* Sort and remove duplicates from the COLLECTION_REC. */
2338 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2340 if (collection_rec->def_vec)
2341 collection_rec->next_def
2342 = df_sort_and_compress_refs (collection_rec->def_vec,
2343 collection_rec->next_def);
2344 if (collection_rec->use_vec)
2345 collection_rec->next_use
2346 = df_sort_and_compress_refs (collection_rec->use_vec,
2347 collection_rec->next_use);
2348 if (collection_rec->eq_use_vec)
2349 collection_rec->next_eq_use
2350 = df_sort_and_compress_refs (collection_rec->eq_use_vec,
2351 collection_rec->next_eq_use);
2352 if (collection_rec->mw_vec)
2353 collection_rec->next_mw
2354 = df_sort_and_compress_mws (collection_rec->mw_vec,
2355 collection_rec->next_mw);
2359 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2362 df_install_ref (struct df_ref *this_ref,
2363 struct df_reg_info *reg_info,
2364 struct df_ref_info *ref_info,
2367 unsigned int regno = DF_REF_REGNO (this_ref);
2368 /* Add the ref to the reg_{def,use,eq_use} chain. */
2369 struct df_ref *head = reg_info->reg_chain;
2371 reg_info->reg_chain = this_ref;
2374 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2376 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2377 df->hard_regs_live_count[regno]++;
2380 gcc_assert (DF_REF_NEXT_REG (this_ref) == NULL);
2381 gcc_assert (DF_REF_PREV_REG (this_ref) == NULL);
2383 DF_REF_NEXT_REG (this_ref) = head;
2385 /* We cannot actually link to the head of the chain. */
2386 DF_REF_PREV_REG (this_ref) = NULL;
2389 DF_REF_PREV_REG (head) = this_ref;
2393 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2394 df_check_and_grow_ref_info (ref_info, 1);
2395 DF_REF_ID (this_ref) = ref_info->table_size;
2396 /* Add the ref to the big array of defs. */
2397 ref_info->refs[ref_info->table_size] = this_ref;
2398 ref_info->table_size++;
2401 DF_REF_ID (this_ref) = -1;
2403 ref_info->total_size++;
2407 /* This function takes one of the groups of refs (defs, uses or
2408 eq_uses) and installs the entire group into the insn. It also adds
2409 each of these refs into the appropriate chains. */
2411 static struct df_ref **
2412 df_install_refs (basic_block bb,
2413 struct df_ref **old_vec, unsigned int count,
2414 struct df_reg_info **reg_info,
2415 struct df_ref_info *ref_info,
2421 struct df_ref **new_vec = XNEWVEC (struct df_ref*, count + 1);
2424 switch (ref_info->ref_order)
2426 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2427 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2428 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2429 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2430 add_to_table = true;
2432 case DF_REF_ORDER_UNORDERED:
2433 case DF_REF_ORDER_BY_REG:
2434 case DF_REF_ORDER_BY_INSN:
2435 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2436 add_to_table = !is_notes;
2439 add_to_table = false;
2443 /* Do not add if ref is not in the right blocks. */
2444 if (add_to_table && df->analyze_subset)
2445 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2447 for (i = 0; i < count; i++)
2449 struct df_ref *this_ref = old_vec[i];
2450 new_vec[i] = this_ref;
2451 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2452 ref_info, add_to_table);
2455 new_vec[count] = NULL;
2459 return df_null_ref_rec;
2463 /* This function takes the mws installs the entire group into the
2466 static struct df_mw_hardreg **
2467 df_install_mws (struct df_mw_hardreg **old_vec, unsigned int count)
2471 struct df_mw_hardreg **new_vec
2472 = XNEWVEC (struct df_mw_hardreg*, count + 1);
2473 memcpy (new_vec, old_vec,
2474 sizeof (struct df_mw_hardreg*) * (count + 1));
2478 return df_null_mw_rec;
2482 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2483 chains and update other necessary information. */
2486 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2487 basic_block bb, rtx insn)
2491 struct df_insn_info *insn_rec = DF_INSN_GET (insn);
2492 /* If there is a vector in the collection rec, add it to the
2493 insn. A null rec is a signal that the caller will handle the
2495 if (collection_rec->def_vec)
2497 if (insn_rec->defs && *insn_rec->defs)
2498 free (insn_rec->defs);
2500 = df_install_refs (bb, collection_rec->def_vec,
2501 collection_rec->next_def,
2503 &df->def_info, false);
2505 if (collection_rec->use_vec)
2507 if (insn_rec->uses && *insn_rec->uses)
2508 free (insn_rec->uses);
2510 = df_install_refs (bb, collection_rec->use_vec,
2511 collection_rec->next_use,
2513 &df->use_info, false);
2515 if (collection_rec->eq_use_vec)
2517 if (insn_rec->eq_uses && *insn_rec->eq_uses)
2518 free (insn_rec->eq_uses);
2520 = df_install_refs (bb, collection_rec->eq_use_vec,
2521 collection_rec->next_eq_use,
2523 &df->use_info, true);
2525 if (collection_rec->mw_vec)
2527 if (insn_rec->mw_hardregs && *insn_rec->mw_hardregs)
2528 free (insn_rec->mw_hardregs);
2529 insn_rec->mw_hardregs
2530 = df_install_mws (collection_rec->mw_vec,
2531 collection_rec->next_mw);
2536 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2538 if (bb_info->artificial_defs && *bb_info->artificial_defs)
2539 free (bb_info->artificial_defs);
2540 bb_info->artificial_defs
2541 = df_install_refs (bb, collection_rec->def_vec,
2542 collection_rec->next_def,
2544 &df->def_info, false);
2545 if (bb_info->artificial_uses && *bb_info->artificial_uses)
2546 free (bb_info->artificial_uses);
2547 bb_info->artificial_uses
2548 = df_install_refs (bb, collection_rec->use_vec,
2549 collection_rec->next_use,
2551 &df->use_info, false);
2556 /* Allocate a ref and initialize its fields. */
2558 static struct df_ref *
2559 df_ref_create_structure (struct df_collection_rec *collection_rec,
2561 basic_block bb, rtx insn,
2562 enum df_ref_type ref_type,
2563 enum df_ref_flags ref_flags)
2565 struct df_ref *this_ref;
2566 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2567 struct df_scan_problem_data *problem_data
2568 = (struct df_scan_problem_data *) df_scan->problem_data;
2570 this_ref = pool_alloc (problem_data->ref_pool);
2571 DF_REF_ID (this_ref) = -1;
2572 DF_REF_REG (this_ref) = reg;
2573 DF_REF_REGNO (this_ref) = regno;
2574 DF_REF_LOC (this_ref) = loc;
2575 DF_REF_INSN (this_ref) = insn;
2576 DF_REF_CHAIN (this_ref) = NULL;
2577 DF_REF_TYPE (this_ref) = ref_type;
2578 DF_REF_FLAGS (this_ref) = ref_flags;
2579 DF_REF_BB (this_ref) = bb;
2580 DF_REF_NEXT_REG (this_ref) = NULL;
2581 DF_REF_PREV_REG (this_ref) = NULL;
2582 DF_REF_ORDER (this_ref) = df->ref_order++;
2584 /* We need to clear this bit because fwprop, and in the future
2585 possibly other optimizations sometimes create new refs using ond
2586 refs as the model. */
2587 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2589 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2590 if ((regno < FIRST_PSEUDO_REGISTER)
2591 && (!DF_REF_IS_ARTIFICIAL (this_ref)))
2593 if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
2595 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2596 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2598 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2599 && (regno == FRAME_POINTER_REGNUM
2600 || regno == ARG_POINTER_REGNUM)))
2601 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2606 if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
2607 collection_rec->def_vec[collection_rec->next_def++] = this_ref;
2608 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2609 collection_rec->eq_use_vec[collection_rec->next_eq_use++] = this_ref;
2611 collection_rec->use_vec[collection_rec->next_use++] = this_ref;
2618 /* Create new references of type DF_REF_TYPE for each part of register REG
2619 at address LOC within INSN of BB. */
2622 df_ref_record (struct df_collection_rec *collection_rec,
2624 basic_block bb, rtx insn,
2625 enum df_ref_type ref_type,
2626 enum df_ref_flags ref_flags)
2631 gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2633 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2634 if (regno < FIRST_PSEUDO_REGISTER)
2636 struct df_mw_hardreg *hardreg = NULL;
2637 struct df_scan_problem_data *problem_data
2638 = (struct df_scan_problem_data *) df_scan->problem_data;
2640 unsigned int endregno;
2643 if (GET_CODE (reg) == SUBREG)
2645 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2646 SUBREG_BYTE (reg), GET_MODE (reg));
2647 endregno = regno + subreg_nregs (reg);
2650 endregno = END_HARD_REGNO (reg);
2652 /* If this is a multiword hardreg, we create some extra
2653 datastructures that will enable us to easily build REG_DEAD
2654 and REG_UNUSED notes. */
2655 if ((endregno != regno + 1) && insn)
2657 /* Sets to a subreg of a multiword register are partial.
2658 Sets to a non-subreg of a multiword register are not. */
2659 if (GET_CODE (oldreg) == SUBREG)
2660 ref_flags |= DF_REF_PARTIAL;
2661 ref_flags |= DF_REF_MW_HARDREG;
2663 hardreg = pool_alloc (problem_data->mw_reg_pool);
2664 hardreg->type = ref_type;
2665 hardreg->flags = ref_flags;
2666 hardreg->mw_reg = reg;
2668 hardreg->start_regno = regno;
2669 hardreg->end_regno = endregno - 1;
2670 hardreg->mw_order = df->ref_order++;
2671 collection_rec->mw_vec[collection_rec->next_mw++] = hardreg;
2674 for (i = regno; i < endregno; i++)
2676 ref = df_ref_create_structure (collection_rec, regno_reg_rtx[i], loc,
2677 bb, insn, ref_type, ref_flags);
2679 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2685 ref = df_ref_create_structure (collection_rec, reg, loc, bb, insn,
2686 ref_type, ref_flags);
2691 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2692 covered by the outer mode is smaller than that covered by the inner mode,
2693 is a read-modify-write operation.
2694 This function returns true iff the SUBREG X is such a SUBREG. */
2697 df_read_modify_subreg_p (rtx x)
2699 unsigned int isize, osize;
2700 if (GET_CODE (x) != SUBREG)
2702 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2703 osize = GET_MODE_SIZE (GET_MODE (x));
2704 return (isize > osize && isize > UNITS_PER_WORD);
2708 /* Process all the registers defined in the rtx, X.
2709 Autoincrement/decrement definitions will be picked up by
2713 df_def_record_1 (struct df_collection_rec *collection_rec,
2714 rtx x, basic_block bb, rtx insn,
2715 enum df_ref_flags flags)
2719 bool dst_in_strict_lowpart = false;
2721 /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
2723 if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
2726 loc = &SET_DEST (x);
2729 /* It is legal to have a set destination be a parallel. */
2730 if (GET_CODE (dst) == PARALLEL)
2734 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2736 rtx temp = XVECEXP (dst, 0, i);
2737 if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
2738 || GET_CODE (temp) == SET)
2739 df_def_record_1 (collection_rec,
2741 GET_CODE (temp) == CLOBBER
2742 ? flags | DF_REF_MUST_CLOBBER : flags);
2747 /* Maybe, we should flag the use of STRICT_LOW_PART somehow. It might
2748 be handy for the reg allocator. */
2749 while (GET_CODE (dst) == STRICT_LOW_PART
2750 || GET_CODE (dst) == ZERO_EXTRACT
2751 || df_read_modify_subreg_p (dst))
2754 /* Strict low part always contains SUBREG, but we do not want to make
2755 it appear outside, as whole register is always considered. */
2756 if (GET_CODE (dst) == STRICT_LOW_PART)
2758 loc = &XEXP (dst, 0);
2762 loc = &XEXP (dst, 0);
2763 if (GET_CODE (dst) == STRICT_LOW_PART)
2764 dst_in_strict_lowpart = true;
2766 flags |= DF_REF_READ_WRITE;
2770 /* Sets to a subreg of a single word register are partial sets if
2771 they are wrapped in a strict lowpart, and not partial otherwise.
2773 if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))
2774 && dst_in_strict_lowpart)
2775 flags |= DF_REF_PARTIAL;
2778 || (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))))
2779 df_ref_record (collection_rec,
2780 dst, loc, bb, insn, DF_REF_REG_DEF, flags);
2784 /* Process all the registers defined in the pattern rtx, X. */
2787 df_defs_record (struct df_collection_rec *collection_rec,
2788 rtx x, basic_block bb, rtx insn, enum df_ref_flags flags)
2790 RTX_CODE code = GET_CODE (x);
2792 if (code == SET || code == CLOBBER)
2794 /* Mark the single def within the pattern. */
2795 enum df_ref_flags clobber_flags = flags;
2796 clobber_flags |= (code == CLOBBER) ? DF_REF_MUST_CLOBBER : 0;
2797 df_def_record_1 (collection_rec, x, bb, insn, clobber_flags);
2799 else if (code == COND_EXEC)
2801 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2802 bb, insn, DF_REF_CONDITIONAL);
2804 else if (code == PARALLEL)
2808 /* Mark the multiple defs within the pattern. */
2809 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2810 df_defs_record (collection_rec, XVECEXP (x, 0, i), bb, insn, flags);
2815 /* Process all the registers used in the rtx at address LOC. */
2818 df_uses_record (struct df_collection_rec *collection_rec,
2819 rtx *loc, enum df_ref_type ref_type,
2820 basic_block bb, rtx insn, enum df_ref_flags flags)
2829 code = GET_CODE (x);
2845 /* If we are clobbering a MEM, mark any registers inside the address
2847 if (MEM_P (XEXP (x, 0)))
2848 df_uses_record (collection_rec,
2849 &XEXP (XEXP (x, 0), 0),
2850 DF_REF_REG_MEM_STORE, bb, insn, flags);
2852 /* If we're clobbering a REG then we have a def so ignore. */
2856 df_uses_record (collection_rec,
2857 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2858 bb, insn, flags & DF_REF_IN_NOTE);
2862 /* While we're here, optimize this case. */
2863 flags |= DF_REF_PARTIAL;
2864 /* In case the SUBREG is not of a REG, do not optimize. */
2865 if (!REG_P (SUBREG_REG (x)))
2867 loc = &SUBREG_REG (x);
2868 df_uses_record (collection_rec, loc, ref_type, bb, insn, flags);
2871 /* ... Fall through ... */
2874 df_ref_record (collection_rec,
2875 x, loc, bb, insn, ref_type, flags);
2880 rtx dst = SET_DEST (x);
2881 gcc_assert (!(flags & DF_REF_IN_NOTE));
2882 df_uses_record (collection_rec,
2883 &SET_SRC (x), DF_REF_REG_USE, bb, insn, flags);
2885 switch (GET_CODE (dst))
2888 if (df_read_modify_subreg_p (dst))
2890 df_uses_record (collection_rec, &SUBREG_REG (dst),
2891 DF_REF_REG_USE, bb, insn, flags | DF_REF_READ_WRITE);
2902 df_uses_record (collection_rec, &XEXP (dst, 0),
2903 DF_REF_REG_MEM_STORE, bb, insn, flags);
2905 case STRICT_LOW_PART:
2907 rtx *temp = &XEXP (dst, 0);
2908 /* A strict_low_part uses the whole REG and not just the
2910 dst = XEXP (dst, 0);
2911 df_uses_record (collection_rec,
2912 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2913 DF_REF_REG_USE, bb, insn, DF_REF_READ_WRITE);
2918 df_uses_record (collection_rec, &XEXP (dst, 0),
2919 DF_REF_REG_USE, bb, insn, DF_REF_READ_WRITE);
2920 df_uses_record (collection_rec, &XEXP (dst, 1),
2921 DF_REF_REG_USE, bb, insn, flags);
2922 df_uses_record (collection_rec, &XEXP (dst, 2),
2923 DF_REF_REG_USE, bb, insn, flags);
2924 dst = XEXP (dst, 0);
2936 case UNSPEC_VOLATILE:
2940 /* Traditional and volatile asm instructions must be
2941 considered to use and clobber all hard registers, all
2942 pseudo-registers and all of memory. So must TRAP_IF and
2943 UNSPEC_VOLATILE operations.
2945 Consider for instance a volatile asm that changes the fpu
2946 rounding mode. An insn should not be moved across this
2947 even if it only uses pseudo-regs because it might give an
2948 incorrectly rounded result.
2950 However, flow.c's liveness computation did *not* do this,
2951 giving the reasoning as " ?!? Unfortunately, marking all
2952 hard registers as live causes massive problems for the
2953 register allocator and marking all pseudos as live creates
2954 mountains of uninitialized variable warnings."
2956 In order to maintain the status quo with regard to liveness
2957 and uses, we do what flow.c did and just mark any regs we
2958 can find in ASM_OPERANDS as used. In global asm insns are
2959 scanned and regs_asm_clobbered is filled out.
2961 For all ASM_OPERANDS, we must traverse the vector of input
2962 operands. We can not just fall through here since then we
2963 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2964 which do not indicate traditional asms unlike their normal
2966 if (code == ASM_OPERANDS)
2970 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2971 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
2972 DF_REF_REG_USE, bb, insn, flags);
2984 /* Catch the def of the register being modified. */
2985 df_ref_record (collection_rec, XEXP (x, 0), &XEXP (x, 0), bb, insn,
2987 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
2989 /* ... Fall through to handle uses ... */
2995 /* Recursively scan the operands of this expression. */
2997 const char *fmt = GET_RTX_FORMAT (code);
3000 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3004 /* Tail recursive case: save a function call level. */
3010 df_uses_record (collection_rec, &XEXP (x, i), ref_type, bb, insn, flags);
3012 else if (fmt[i] == 'E')
3015 for (j = 0; j < XVECLEN (x, i); j++)
3016 df_uses_record (collection_rec,
3017 &XVECEXP (x, i, j), ref_type, bb, insn, flags);
3026 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3029 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3032 for (i = 0; i < collection_rec->next_def; i++)
3034 struct df_ref *ref = collection_rec->def_vec[i];
3035 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3038 = df_ref_create_structure (collection_rec, DF_REF_REG (ref),
3039 DF_REF_LOC (ref), DF_REF_BB (ref),
3040 DF_REF_INSN (ref), DF_REF_REG_USE,
3041 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3042 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3048 /* Get call's extra defs and uses. */
3051 df_get_call_refs (struct df_collection_rec * collection_rec,
3054 enum df_ref_flags flags)
3059 bool is_sibling_call;
3061 bitmap defs_generated = BITMAP_ALLOC (&df_bitmap_obstack);
3063 /* Do not generate clobbers for registers that are the result of the
3064 call. This causes ordering problems in the chain building code
3065 depending on which def is seen first. */
3066 for (i=0; i<collection_rec->next_def; i++)
3068 struct df_ref *def = collection_rec->def_vec[i];
3069 bitmap_set_bit (defs_generated, DF_REF_REGNO (def));
3072 /* Record the registers used to pass arguments, and explicitly
3073 noted as clobbered. */
3074 for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
3075 note = XEXP (note, 1))
3077 if (GET_CODE (XEXP (note, 0)) == USE)
3078 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3079 DF_REF_REG_USE, bb, insn, flags);
3080 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3082 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3083 if (!bitmap_bit_p (defs_generated, regno))
3084 df_defs_record (collection_rec, XEXP (note, 0), bb, insn, flags);
3088 /* The stack ptr is used (honorarily) by a CALL insn. */
3089 df_ref_record (collection_rec, regno_reg_rtx[STACK_POINTER_REGNUM],
3090 NULL, bb, insn, DF_REF_REG_USE, DF_REF_CALL_STACK_USAGE | flags);
3092 /* Calls may also reference any of the global registers,
3093 so they are recorded as used. */
3094 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3096 df_ref_record (collection_rec, regno_reg_rtx[i],
3097 NULL, bb, insn, DF_REF_REG_USE, flags);
3099 is_sibling_call = SIBLING_CALL_P (insn);
3100 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, ui, bi)
3102 if ((!bitmap_bit_p (defs_generated, ui))
3103 && (!is_sibling_call
3104 || !bitmap_bit_p (df->exit_block_uses, ui)
3105 || refers_to_regno_p (ui, ui+1,
3106 current_function_return_rtx, NULL)))
3108 df_ref_record (collection_rec, regno_reg_rtx[ui],
3109 NULL, bb, insn, DF_REF_REG_DEF, DF_REF_MAY_CLOBBER | flags);
3112 BITMAP_FREE (defs_generated);
3116 /* Collect all refs in the INSN. This function is free of any
3117 side-effect - it will create and return a lists of df_ref's in the
3118 COLLECTION_REC without putting those refs into existing ref chains
3122 df_insn_refs_collect (struct df_collection_rec* collection_rec,
3123 basic_block bb, rtx insn)
3126 bool is_cond_exec = (GET_CODE (PATTERN (insn)) == COND_EXEC);
3128 /* Clear out the collection record. */
3129 collection_rec->next_def = 0;
3130 collection_rec->next_use = 0;
3131 collection_rec->next_eq_use = 0;
3132 collection_rec->next_mw = 0;
3134 /* Record register defs. */
3135 df_defs_record (collection_rec, PATTERN (insn), bb, insn, 0);
3137 /* Process REG_EQUIV/REG_EQUAL notes */
3138 for (note = REG_NOTES (insn); note;
3139 note = XEXP (note, 1))
3141 switch (REG_NOTE_KIND (note))
3145 df_uses_record (collection_rec,
3146 &XEXP (note, 0), DF_REF_REG_USE,
3147 bb, insn, DF_REF_IN_NOTE);
3149 case REG_NON_LOCAL_GOTO:
3150 /* The frame ptr is used by a non-local goto. */
3151 df_ref_record (collection_rec,
3152 regno_reg_rtx[FRAME_POINTER_REGNUM],
3156 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3157 df_ref_record (collection_rec,
3158 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3170 df_get_call_refs (collection_rec, bb, insn,
3171 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3173 /* Record the register uses. */
3174 df_uses_record (collection_rec,
3175 &PATTERN (insn), DF_REF_REG_USE, bb, insn, 0);
3177 /* DF_REF_CONDITIONAL needs corresponding USES. */
3179 df_get_conditional_uses (collection_rec);
3181 df_canonize_collection_rec (collection_rec);
3184 /* Return true if any pred of BB is an eh. */
3187 df_has_eh_preds (basic_block bb)
3192 FOR_EACH_EDGE (e, ei, bb->preds)
3194 if (e->flags & EDGE_EH)
3201 /* Recompute the luids for the insns in BB. */
3204 df_recompute_luids (basic_block bb)
3209 df_grow_insn_info ();
3211 /* Scan the block an insn at a time from beginning to end. */
3212 FOR_BB_INSNS (bb, insn)
3214 struct df_insn_info *insn_info = DF_INSN_GET (insn);
3215 /* Inserting labels does not always trigger the incremental
3219 gcc_assert (!INSN_P (insn));
3220 df_insn_create_insn_record (insn);
3223 DF_INSN_LUID (insn) = luid;
3230 /* Returns true if the function entry needs to
3231 define the static chain register. */
3234 df_need_static_chain_reg (struct function *fun)
3236 tree fun_context = decl_function_context (fun->decl);
3238 && DECL_NO_STATIC_CHAIN (fun_context) == false;
3242 /* Collect all artificial refs at the block level for BB and add them
3243 to COLLECTION_REC. */
3246 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3248 collection_rec->next_def = 0;
3249 collection_rec->next_use = 0;
3250 collection_rec->next_eq_use = 0;
3251 collection_rec->next_mw = 0;
3253 if (bb->index == ENTRY_BLOCK)
3255 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3258 else if (bb->index == EXIT_BLOCK)
3260 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3264 #ifdef EH_RETURN_DATA_REGNO
3265 if (df_has_eh_preds (bb))
3268 /* Mark the registers that will contain data for the handler. */
3271 unsigned regno = EH_RETURN_DATA_REGNO (i);
3272 if (regno == INVALID_REGNUM)
3274 df_ref_record (collection_rec, regno_reg_rtx[regno], NULL,
3275 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3282 if (df_has_eh_preds (bb))
3285 /* This code is putting in an artificial ref for the use at the
3286 TOP of the block that receives the exception. It is too
3287 cumbersome to actually put the ref on the edge. We could
3288 either model this at the top of the receiver block or the
3289 bottom of the sender block.
3291 The bottom of the sender block is problematic because not all
3292 out-edges of the a block are eh-edges. However, it is true
3293 that all edges into a block are either eh-edges or none of
3294 them are eh-edges. Thus, we can model this at the top of the
3295 eh-receiver for all of the edges at once. */
3296 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3298 df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3299 bb, NULL, DF_REF_REG_USE, DF_REF_AT_TOP);
3303 /* Add the hard_frame_pointer if this block is the target of a
3305 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3306 df_ref_record (collection_rec, hard_frame_pointer_rtx, NULL,
3307 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3309 /* Add the artificial uses. */
3310 if (bb->index >= NUM_FIXED_BLOCKS)
3314 bitmap au = df_has_eh_preds (bb)
3315 ? df->eh_block_artificial_uses
3316 : df->regular_block_artificial_uses;
3318 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3320 df_ref_record (collection_rec, regno_reg_rtx[regno], NULL,
3321 bb, NULL, DF_REF_REG_USE, 0);
3325 df_canonize_collection_rec (collection_rec);
3329 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3332 df_bb_refs_record (int bb_index, bool scan_insns)
3334 basic_block bb = BASIC_BLOCK (bb_index);
3337 struct df_scan_bb_info *bb_info;
3338 struct df_collection_rec collection_rec;
3339 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
3340 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
3341 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
3342 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
3347 bb_info = df_scan_get_bb_info (bb_index);
3349 /* Need to make sure that there is a record in the basic block info. */
3352 bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
3353 df_scan_set_bb_info (bb_index, bb_info);
3354 bb_info->artificial_defs = NULL;
3355 bb_info->artificial_uses = NULL;
3359 /* Scan the block an insn at a time from beginning to end. */
3360 FOR_BB_INSNS (bb, insn)
3362 struct df_insn_info *insn_info = DF_INSN_GET (insn);
3363 gcc_assert (!insn_info);
3365 df_insn_create_insn_record (insn);
3368 /* Record refs within INSN. */
3369 DF_INSN_LUID (insn) = luid++;
3370 df_insn_refs_collect (&collection_rec, bb, insn);
3371 df_refs_add_to_chains (&collection_rec, bb, insn);
3373 DF_INSN_LUID (insn) = luid;
3376 /* Other block level artificial refs */
3377 df_bb_refs_collect (&collection_rec, bb);
3378 df_refs_add_to_chains (&collection_rec, bb, NULL);
3380 /* Now that the block has been processed, set the block as dirty so
3381 lr and ur will get it processed. */
3382 df_set_bb_dirty (bb);
3386 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3390 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3392 bitmap_clear (regular_block_artificial_uses);
3394 if (reload_completed)
3396 if (frame_pointer_needed)
3397 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3400 /* Before reload, there are a few registers that must be forced
3401 live everywhere -- which might not already be the case for
3402 blocks within infinite loops. */
3404 /* Any reference to any pseudo before reload is a potential
3405 reference of the frame pointer. */
3406 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3408 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3409 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3412 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3413 /* Pseudos with argument area equivalences may require
3414 reloading via the argument pointer. */
3415 if (fixed_regs[ARG_POINTER_REGNUM])
3416 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3419 /* Any constant, or pseudo with constant equivalences, may
3420 require reloading from memory using the pic register. */
3421 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3422 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3423 bitmap_set_bit (regular_block_artificial_uses, PIC_OFFSET_TABLE_REGNUM);
3425 /* The all-important stack pointer must always be live. */
3426 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3430 /* Get the artificial use set for an eh block. */
3433 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3435 bitmap_clear (eh_block_artificial_uses);
3437 /* The following code (down thru the arg_pointer seting APPEARS
3438 to be necessary because there is nothing that actually
3439 describes what the exception handling code may actually need
3441 if (reload_completed)
3443 if (frame_pointer_needed)
3445 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3446 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3447 bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3450 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3451 if (fixed_regs[ARG_POINTER_REGNUM])
3452 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3459 /*----------------------------------------------------------------------------
3460 Specialized hard register scanning functions.
3461 ----------------------------------------------------------------------------*/
3464 /* Mark a register in SET. Hard registers in large modes get all
3465 of their component registers set as well. */
3468 df_mark_reg (rtx reg, void *vset)
3470 bitmap set = (bitmap) vset;
3471 int regno = REGNO (reg);
3473 gcc_assert (GET_MODE (reg) != BLKmode);
3475 bitmap_set_bit (set, regno);
3476 if (regno < FIRST_PSEUDO_REGISTER)
3478 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3480 bitmap_set_bit (set, regno + n);
3487 /* Set the bit for regs that are considered being defined at the entry. */
3490 df_get_entry_block_def_set (bitmap entry_block_defs)
3495 bitmap_clear (entry_block_defs);
3497 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3499 if (FUNCTION_ARG_REGNO_P (i))
3500 #ifdef INCOMING_REGNO
3501 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3503 bitmap_set_bit (entry_block_defs, i);
3507 /* Once the prologue has been generated, all of these registers
3508 should just show up in the first regular block. */
3509 if (HAVE_prologue && epilogue_completed)
3511 /* Defs for the callee saved registers are inserted so that the
3512 pushes have some defining location. */
3513 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3514 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3515 bitmap_set_bit (entry_block_defs, i);
3519 /* The always important stack pointer. */
3520 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3522 /* If STATIC_CHAIN_INCOMING_REGNUM == STATIC_CHAIN_REGNUM
3523 only STATIC_CHAIN_REGNUM is defined. If they are different,
3524 we only care about the STATIC_CHAIN_INCOMING_REGNUM. */
3525 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3526 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3528 #ifdef STATIC_CHAIN_REGNUM
3529 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3533 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3535 bitmap_set_bit (entry_block_defs, REGNO (r));
3538 if ((!reload_completed) || frame_pointer_needed)
3540 /* Any reference to any pseudo before reload is a potential
3541 reference of the frame pointer. */
3542 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3543 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3544 /* If they are different, also mark the hard frame pointer as live. */
3545 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3546 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3550 /* These registers are live everywhere. */
3551 if (!reload_completed)
3554 /* The ia-64, the only machine that uses this, does not define these
3555 until after reload. */
3556 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3559 bitmap_set_bit (entry_block_defs, i);
3563 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3564 /* Pseudos with argument area equivalences may require
3565 reloading via the argument pointer. */
3566 if (fixed_regs[ARG_POINTER_REGNUM])
3567 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3570 #ifdef PIC_OFFSET_TABLE_REGNUM
3571 /* Any constant, or pseudo with constant equivalences, may
3572 require reloading from memory using the pic register. */
3573 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3574 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3575 bitmap_set_bit (entry_block_defs, PIC_OFFSET_TABLE_REGNUM);
3579 #ifdef INCOMING_RETURN_ADDR_RTX
3580 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3581 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3584 targetm.live_on_entry (entry_block_defs);
3586 /* If the function has an incoming STATIC_CHAIN,
3587 it has to show up in the entry def set. */
3588 if (df_need_static_chain_reg (cfun))
3590 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3591 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3593 #ifdef STATIC_CHAIN_REGNUM
3594 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3601 /* Return the (conservative) set of hard registers that are defined on
3602 entry to the function.
3603 It uses df->entry_block_defs to determine which register
3604 reference to include. */
3607 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3608 bitmap entry_block_defs)
3613 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3615 df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3616 ENTRY_BLOCK_PTR, NULL, DF_REF_REG_DEF, 0);
3619 df_canonize_collection_rec (collection_rec);
3623 /* Record the (conservative) set of hard registers that are defined on
3624 entry to the function. */
3627 df_record_entry_block_defs (bitmap entry_block_defs)
3629 struct df_collection_rec collection_rec;
3630 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3631 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * FIRST_PSEUDO_REGISTER);
3633 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3635 /* Process bb_refs chain */
3636 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (ENTRY_BLOCK), NULL);
3640 /* Update the defs in the entry bolck. */
3643 df_update_entry_block_defs (void)
3645 bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3646 bool changed = false;
3648 df_get_entry_block_def_set (refs);
3649 if (df->entry_block_defs)
3651 if (!bitmap_equal_p (df->entry_block_defs, refs))
3653 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3654 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3655 df_ref_chain_delete (bb_info->artificial_defs);
3656 bb_info->artificial_defs = NULL;
3662 struct df_scan_problem_data *problem_data
3663 = (struct df_scan_problem_data *) df_scan->problem_data;
3664 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3670 df_record_entry_block_defs (refs);
3671 bitmap_copy (df->entry_block_defs, refs);
3672 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
3678 /* Set the bit for regs that are considered being used at the exit. */
3681 df_get_exit_block_use_set (bitmap exit_block_uses)
3685 bitmap_clear (exit_block_uses);
3687 /* Stack pointer is always live at the exit. */
3688 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3690 /* Mark the frame pointer if needed at the end of the function.
3691 If we end up eliminating it, it will be removed from the live
3692 list of each basic block by reload. */
3694 if ((!reload_completed) || frame_pointer_needed)
3696 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3697 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3698 /* If they are different, also mark the hard frame pointer as live. */
3699 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3700 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3704 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3705 /* Many architectures have a GP register even without flag_pic.
3706 Assume the pic register is not in use, or will be handled by
3707 other means, if it is not fixed. */
3708 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3709 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3710 bitmap_set_bit (exit_block_uses, PIC_OFFSET_TABLE_REGNUM);
3713 /* Mark all global registers, and all registers used by the
3714 epilogue as being live at the end of the function since they
3715 may be referenced by our caller. */
3716 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3717 if (global_regs[i] || EPILOGUE_USES (i))
3718 bitmap_set_bit (exit_block_uses, i);
3720 if (HAVE_epilogue && epilogue_completed)
3722 /* Mark all call-saved registers that we actually used. */
3723 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3724 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3725 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3726 bitmap_set_bit (exit_block_uses, i);
3729 #ifdef EH_RETURN_DATA_REGNO
3730 /* Mark the registers that will contain data for the handler. */
3731 if (reload_completed && current_function_calls_eh_return)
3734 unsigned regno = EH_RETURN_DATA_REGNO (i);
3735 if (regno == INVALID_REGNUM)
3737 bitmap_set_bit (exit_block_uses, regno);
3741 #ifdef EH_RETURN_STACKADJ_RTX
3742 if ((!HAVE_epilogue || ! epilogue_completed)
3743 && current_function_calls_eh_return)
3745 rtx tmp = EH_RETURN_STACKADJ_RTX;
3746 if (tmp && REG_P (tmp))
3747 df_mark_reg (tmp, exit_block_uses);
3751 #ifdef EH_RETURN_HANDLER_RTX
3752 if ((!HAVE_epilogue || ! epilogue_completed)
3753 && current_function_calls_eh_return)
3755 rtx tmp = EH_RETURN_HANDLER_RTX;
3756 if (tmp && REG_P (tmp))
3757 df_mark_reg (tmp, exit_block_uses);
3761 /* Mark function return value. */
3762 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3766 /* Return the refs of hard registers that are used in the exit block.
3767 It uses df->exit_block_uses to determine register to include. */
3770 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3775 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3776 df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3777 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
3779 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3780 /* It is deliberate that this is not put in the exit block uses but
3781 I do not know why. */
3782 if (reload_completed
3783 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3784 && df_has_eh_preds (EXIT_BLOCK_PTR)
3785 && fixed_regs[ARG_POINTER_REGNUM])
3786 df_ref_record (collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3787 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
3790 df_canonize_collection_rec (collection_rec);
3794 /* Record the set of hard registers that are used in the exit block.
3795 It uses df->exit_block_uses to determine which bit to include. */
3798 df_record_exit_block_uses (bitmap exit_block_uses)
3800 struct df_collection_rec collection_rec;
3801 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3802 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * FIRST_PSEUDO_REGISTER);
3804 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3806 /* Process bb_refs chain */
3807 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (EXIT_BLOCK), NULL);
3811 /* Update the uses in the exit block. */
3814 df_update_exit_block_uses (void)
3816 bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3817 bool changed = false;
3819 df_get_exit_block_use_set (refs);
3820 if (df->exit_block_uses)
3822 if (!bitmap_equal_p (df->exit_block_uses, refs))
3824 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3825 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3826 df_ref_chain_delete (bb_info->artificial_uses);
3827 bb_info->artificial_uses = NULL;
3833 struct df_scan_problem_data *problem_data
3834 = (struct df_scan_problem_data *) df_scan->problem_data;
3835 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3841 df_record_exit_block_uses (refs);
3842 bitmap_copy (df->exit_block_uses, refs);
3843 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
3848 static bool initialized = false;
3851 /* Initialize some platform specific structures. */
3854 df_hard_reg_init (void)
3857 #ifdef ELIMINABLE_REGS
3858 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3863 bitmap_obstack_initialize (&persistent_obstack);
3865 /* Record which registers will be eliminated. We use this in
3867 CLEAR_HARD_REG_SET (elim_reg_set);
3869 #ifdef ELIMINABLE_REGS
3870 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3871 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3873 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3876 df_invalidated_by_call = BITMAP_ALLOC (&persistent_obstack);
3878 /* Inconveniently, this is only readily available in hard reg set
3880 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
3881 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3882 bitmap_set_bit (df_invalidated_by_call, i);
3888 /* Recompute the parts of scanning that are based on regs_ever_live
3889 because something changed in that array. */
3892 df_update_entry_exit_and_calls (void)
3896 df_update_entry_block_defs ();
3897 df_update_exit_block_uses ();
3899 /* The call insns need to be rescanned because there may be changes
3900 in the set of registers clobbered across the call. */
3904 FOR_BB_INSNS (bb, insn)
3906 if (INSN_P (insn) && CALL_P (insn))
3907 df_insn_rescan (insn);
3913 /* Return true if hard REG is actually used in the some instruction.
3914 There are a fair number of conditions that affect the setting of
3915 this array. See the comment in df.h for df->hard_regs_live_count
3916 for the conditions that this array is set. */
3919 df_hard_reg_used_p (unsigned int reg)
3922 return df->hard_regs_live_count[reg] != 0;
3926 /* A count of the number of times REG is actually used in the some
3927 instruction. There are a fair number of conditions that affect the
3928 setting of this array. See the comment in df.h for
3929 df->hard_regs_live_count for the conditions that this array is
3934 df_hard_reg_used_count (unsigned int reg)
3937 return df->hard_regs_live_count[reg];
3941 /* Get the value of regs_ever_live[REGNO]. */
3944 df_regs_ever_live_p (unsigned int regno)
3946 return regs_ever_live[regno];
3950 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3951 to change, schedule that change for the next update. */
3954 df_set_regs_ever_live (unsigned int regno, bool value)
3956 if (regs_ever_live[regno] == value)
3959 regs_ever_live[regno] = value;
3961 df->redo_entry_and_exit = true;
3965 /* Compute "regs_ever_live" information from the underlying df
3966 information. Set the vector to all false if RESET. */
3969 df_compute_regs_ever_live (bool reset)
3972 bool changed = df->redo_entry_and_exit;
3975 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3977 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3978 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3980 regs_ever_live[i] = true;
3984 df_update_entry_exit_and_calls ();
3985 df->redo_entry_and_exit = false;
3989 /*----------------------------------------------------------------------------
3990 Dataflow ref information verification functions.
3992 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3993 df_reg_chain_verify_unmarked (refs)
3994 df_refs_verify (ref*, ref*, bool)
3995 df_mws_verify (mw*, mw*, bool)
3996 df_insn_refs_verify (collection_rec, bb, insn, bool)
3997 df_bb_refs_verify (bb, refs, bool)
3999 df_exit_block_bitmap_verify (bool)
4000 df_entry_block_bitmap_verify (bool)
4002 ----------------------------------------------------------------------------*/
4005 /* Mark all refs in the reg chain. Verify that all of the registers
4006 are in the correct chain. */
4009 df_reg_chain_mark (struct df_ref *refs, unsigned int regno,
4010 bool is_def, bool is_eq_use)
4012 unsigned int count = 0;
4014 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4016 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4018 /* If there are no def-use or use-def chains, make sure that all
4019 of the chains are clear. */
4021 gcc_assert (!DF_REF_CHAIN (ref));
4023 /* Check to make sure the ref is in the correct chain. */
4024 gcc_assert (DF_REF_REGNO (ref) == regno);
4026 gcc_assert (DF_REF_TYPE(ref) == DF_REF_REG_DEF);
4028 gcc_assert (DF_REF_TYPE(ref) != DF_REF_REG_DEF);
4031 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4033 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4036 gcc_assert (ref->next_reg->prev_reg == ref);
4038 DF_REF_REG_MARK (ref);
4044 /* Verify that all of the registers in the chain are unmarked. */
4047 df_reg_chain_verify_unmarked (struct df_ref *refs)
4050 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4051 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4055 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4058 df_refs_verify (struct df_ref **new_rec, struct df_ref **old_rec,
4061 while ((*new_rec) && (*old_rec))
4063 if (!df_ref_equal_p (*new_rec, *old_rec))
4071 /* Abort if fail is called from the function level verifier. If
4072 that is the context, mark this reg as being seem. */
4075 gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
4076 DF_REF_REG_UNMARK (*old_rec);
4084 gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4086 return ((*new_rec == NULL) && (*old_rec == NULL));
4091 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4094 df_mws_verify (struct df_mw_hardreg **new_rec, struct df_mw_hardreg **old_rec,
4097 while ((*new_rec) && (*old_rec))
4099 if (!df_mw_equal_p (*new_rec, *old_rec))
4111 gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4113 return ((*new_rec == NULL) && (*old_rec == NULL));
4118 /* Return true if the existing insn refs information is complete and
4119 correct. Otherwise (i.e. if there's any missing or extra refs),
4120 return the correct df_ref chain in REFS_RETURN.
4122 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4123 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4124 verification mode instead of the whole function, so unmark
4127 If ABORT_IF_FAIL is set, this function never returns false. */
4130 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4135 bool ret1, ret2, ret3, ret4;
4136 unsigned int uid = INSN_UID (insn);
4138 df_insn_refs_collect (collection_rec, bb, insn);
4140 if (!DF_INSN_UID_DEFS (uid))
4142 /* The insn_rec was created but it was never filled out. */
4149 /* Unfortunately we cannot opt out early if one of these is not
4150 right because the marks will not get cleared. */
4151 ret1 = df_refs_verify (collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4153 ret2 = df_refs_verify (collection_rec->use_vec, DF_INSN_UID_USES (uid),
4155 ret3 = df_refs_verify (collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4157 ret4 = df_mws_verify (collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4159 return (ret1 && ret2 && ret3 && ret4);
4163 /* Return true if all refs in the basic block are correct and complete.
4164 Due to df_ref_chain_verify, it will cause all refs
4165 that are verified to have DF_REF_MARK bit set. */
4168 df_bb_verify (basic_block bb)
4171 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4172 struct df_collection_rec collection_rec;
4174 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4175 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
4176 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
4177 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
4178 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
4180 gcc_assert (bb_info);
4182 /* Scan the block an insn at a time from beginning to end. */
4183 FOR_BB_INSNS_REVERSE (bb, insn)
4187 df_insn_refs_verify (&collection_rec, bb, insn, true);
4188 df_free_collection_rec (&collection_rec);
4191 /* Do the artificial defs and uses. */
4192 df_bb_refs_collect (&collection_rec, bb);
4193 df_refs_verify (collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4194 df_refs_verify (collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4195 df_free_collection_rec (&collection_rec);
4201 /* Returns true if the entry block has correct and complete df_ref set.
4202 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4205 df_entry_block_bitmap_verify (bool abort_if_fail)
4207 bitmap entry_block_defs = BITMAP_ALLOC (&df_bitmap_obstack);
4210 df_get_entry_block_def_set (entry_block_defs);
4212 is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4214 if (!is_eq && abort_if_fail)
4216 print_current_pass (stderr);
4217 fprintf (stderr, "entry_block_defs = ");
4218 df_print_regset (stderr, entry_block_defs);
4219 fprintf (stderr, "df->entry_block_defs = ");
4220 df_print_regset (stderr, df->entry_block_defs);
4224 BITMAP_FREE (entry_block_defs);
4230 /* Returns true if the exit block has correct and complete df_ref set.
4231 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4234 df_exit_block_bitmap_verify (bool abort_if_fail)
4236 bitmap exit_block_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4239 df_get_exit_block_use_set (exit_block_uses);
4241 is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4243 if (!is_eq && abort_if_fail)
4245 print_current_pass (stderr);
4246 fprintf (stderr, "exit_block_uses = ");
4247 df_print_regset (stderr, exit_block_uses);
4248 fprintf (stderr, "df->exit_block_uses = ");
4249 df_print_regset (stderr, df->exit_block_uses);
4253 BITMAP_FREE (exit_block_uses);
4259 /* Return true if df_ref information for all insns in all BLOCKS are
4260 correct and complete. If BLOCKS is null, all blocks are
4264 df_scan_verify (void)
4268 bitmap regular_block_artificial_uses;
4269 bitmap eh_block_artificial_uses;
4274 /* This is a hack, but a necessary one. If you do not do this,
4275 insn_attrtab can never be compiled in a bootstrap. This
4276 verification is just too expensive. */
4277 if (n_basic_blocks > 250)
4280 /* Verification is a 4 step process. */
4282 /* (1) All of the refs are marked by going thru the reg chains. */
4283 for (i = 0; i < DF_REG_SIZE (df); i++)
4285 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4286 == DF_REG_DEF_COUNT(i));
4287 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4288 == DF_REG_USE_COUNT(i));
4289 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4290 == DF_REG_EQ_USE_COUNT(i));
4293 /* (2) There are various bitmaps whose value may change over the
4294 course of the compilation. This step recomputes them to make
4295 sure that they have not slipped out of date. */
4296 regular_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4297 eh_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4299 df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4300 df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4302 bitmap_ior_into (eh_block_artificial_uses,
4303 regular_block_artificial_uses);
4305 /* Check artificial_uses bitmaps didn't change. */
4306 gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4307 df->regular_block_artificial_uses));
4308 gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4309 df->eh_block_artificial_uses));
4311 BITMAP_FREE (regular_block_artificial_uses);
4312 BITMAP_FREE (eh_block_artificial_uses);
4314 /* Verify entry block and exit block. These only verify the bitmaps,
4315 the refs are verified in df_bb_verify. */
4316 df_entry_block_bitmap_verify (true);
4317 df_exit_block_bitmap_verify (true);
4319 /* (3) All of the insns in all of the blocks are traversed and the
4320 marks are cleared both in the artificial refs attached to the
4321 blocks and the real refs inside the insns. It is a failure to
4322 clear a mark that has not been set as this means that the ref in
4323 the block or insn was not in the reg chain. */
4328 /* (4) See if all reg chains are traversed a second time. This time
4329 a check is made that the marks are clear. A set mark would be a
4330 from a reg that is not in any insn or basic block. */
4332 for (i = 0; i < DF_REG_SIZE (df); i++)
4334 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4335 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4336 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));