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);
344 df_scan->optional_p = false;
348 /* Free all of the data associated with the scan problem. */
353 if (df_scan->problem_data)
354 df_scan_free_internal ();
356 if (df->blocks_to_analyze)
358 BITMAP_FREE (df->blocks_to_analyze);
359 df->blocks_to_analyze = NULL;
365 /* Dump the preamble for DF_SCAN dump. */
367 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
371 fprintf (file, ";; invalidated by call \t");
372 df_print_regset (file, df_invalidated_by_call);
373 fprintf (file, ";; hardware regs used \t");
374 df_print_regset (file, df->hardware_regs_used);
375 fprintf (file, ";; regular block artificial uses \t");
376 df_print_regset (file, df->regular_block_artificial_uses);
377 fprintf (file, ";; eh block artificial uses \t");
378 df_print_regset (file, df->eh_block_artificial_uses);
379 fprintf (file, ";; entry block defs \t");
380 df_print_regset (file, df->entry_block_defs);
381 fprintf (file, ";; exit block uses \t");
382 df_print_regset (file, df->exit_block_uses);
383 fprintf (file, ";; regs ever live \t");
384 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
385 if (df_regs_ever_live_p (i))
386 fprintf (file, " %d[%s]", i, reg_names[i]);
388 fprintf (file, "\n");
391 /* Dump the bb_info for a given basic block. */
393 df_scan_start_block (basic_block bb, FILE *file)
395 struct df_scan_bb_info *bb_info
396 = df_scan_get_bb_info (bb->index);
400 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
401 df_refs_chain_dump (bb_info->artificial_defs, true, file);
402 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
403 df_refs_chain_dump (bb_info->artificial_uses, true, file);
404 fprintf (file, "\n");
409 FOR_BB_INSNS (bb, insn)
411 df_insn_debug (insn, false, file);
416 static struct df_problem problem_SCAN =
418 DF_SCAN, /* Problem id. */
419 DF_NONE, /* Direction. */
420 df_scan_alloc, /* Allocate the problem specific data. */
421 NULL, /* Reset global information. */
422 df_scan_free_bb_info, /* Free basic block info. */
423 NULL, /* Local compute function. */
424 NULL, /* Init the solution specific data. */
425 NULL, /* Iterative solver. */
426 NULL, /* Confluence operator 0. */
427 NULL, /* Confluence operator n. */
428 NULL, /* Transfer function. */
429 NULL, /* Finalize function. */
430 df_scan_free, /* Free all of the problem information. */
431 NULL, /* Remove this problem from the stack of dataflow problems. */
432 df_scan_start_dump, /* Debugging. */
433 df_scan_start_block, /* Debugging start block. */
434 NULL, /* Debugging end block. */
435 NULL, /* Incremental solution verify start. */
436 NULL, /* Incremental solution verfiy end. */
437 NULL, /* Dependent problem. */
438 TV_DF_SCAN, /* Timing variable. */
439 false /* Reset blocks on dropping out of blocks_to_analyze. */
443 /* Create a new DATAFLOW instance and add it to an existing instance
444 of DF. The returned structure is what is used to get at the
448 df_scan_add_problem (void)
450 df_add_problem (&problem_SCAN);
454 /*----------------------------------------------------------------------------
455 Storage Allocation Utilities
456 ----------------------------------------------------------------------------*/
459 /* First, grow the reg_info information. If the current size is less than
460 the number of psuedos, grow to 25% more than the number of
463 Second, assure that all of the slots up to max_reg_num have been
464 filled with reg_info structures. */
467 df_grow_reg_info (void)
469 unsigned int max_reg = max_reg_num ();
470 unsigned int new_size = max_reg;
471 struct df_scan_problem_data *problem_data
472 = (struct df_scan_problem_data *) df_scan->problem_data;
475 if (df->regs_size < new_size)
477 new_size += new_size / 4;
478 df->def_regs = xrealloc (df->def_regs,
479 new_size *sizeof (struct df_reg_info*));
480 df->use_regs = xrealloc (df->use_regs,
481 new_size *sizeof (struct df_reg_info*));
482 df->eq_use_regs = xrealloc (df->eq_use_regs,
483 new_size *sizeof (struct df_reg_info*));
484 df->def_info.begin = xrealloc (df->def_info.begin,
485 new_size *sizeof (int));
486 df->def_info.count = xrealloc (df->def_info.count,
487 new_size *sizeof (int));
488 df->use_info.begin = xrealloc (df->use_info.begin,
489 new_size *sizeof (int));
490 df->use_info.count = xrealloc (df->use_info.count,
491 new_size *sizeof (int));
492 df->regs_size = new_size;
495 for (i = df->regs_inited; i < max_reg; i++)
497 struct df_reg_info *reg_info;
499 reg_info = pool_alloc (problem_data->reg_pool);
500 memset (reg_info, 0, sizeof (struct df_reg_info));
501 df->def_regs[i] = reg_info;
502 reg_info = pool_alloc (problem_data->reg_pool);
503 memset (reg_info, 0, sizeof (struct df_reg_info));
504 df->use_regs[i] = reg_info;
505 reg_info = pool_alloc (problem_data->reg_pool);
506 memset (reg_info, 0, sizeof (struct df_reg_info));
507 df->eq_use_regs[i] = reg_info;
508 df->def_info.begin[i] = 0;
509 df->def_info.count[i] = 0;
510 df->use_info.begin[i] = 0;
511 df->use_info.count[i] = 0;
514 df->regs_inited = max_reg;
518 /* Grow the ref information. */
521 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
523 if (ref_info->refs_size < new_size)
525 ref_info->refs = xrealloc (ref_info->refs,
526 new_size *sizeof (struct df_ref *));
527 memset (ref_info->refs + ref_info->refs_size, 0,
528 (new_size - ref_info->refs_size) *sizeof (struct df_ref *));
529 ref_info->refs_size = new_size;
534 /* Check and grow the ref information if necessary. This routine
535 guarantees total_size + BITMAP_ADDEND amount of entries in refs
536 array. It updates ref_info->refs_size only and does not change
537 ref_info->total_size. */
540 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
541 unsigned bitmap_addend)
543 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
545 int new_size = ref_info->total_size + bitmap_addend;
546 new_size += ref_info->total_size / 4;
547 df_grow_ref_info (ref_info, new_size);
552 /* Grow the ref information. If the current size is less than the
553 number of instructions, grow to 25% more than the number of
557 df_grow_insn_info (void)
559 unsigned int new_size = get_max_uid () + 1;
560 if (DF_INSN_SIZE () < new_size)
562 new_size += new_size / 4;
563 df->insns = xrealloc (df->insns,
564 new_size *sizeof (struct df_insn_info *));
565 memset (df->insns + df->insns_size, 0,
566 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
567 DF_INSN_SIZE () = new_size;
574 /*----------------------------------------------------------------------------
575 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
576 ----------------------------------------------------------------------------*/
578 /* Rescan all of the block_to_analyze or all of the blocks in the
579 function if df_set_blocks if blocks_to_analyze is NULL; */
582 df_scan_blocks (void)
586 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
587 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
589 df_get_regular_block_artificial_uses (df->regular_block_artificial_uses);
590 df_get_eh_block_artificial_uses (df->eh_block_artificial_uses);
592 bitmap_ior_into (df->eh_block_artificial_uses,
593 df->regular_block_artificial_uses);
595 /* ENTRY and EXIT blocks have special defs/uses. */
596 df_get_entry_block_def_set (df->entry_block_defs);
597 df_record_entry_block_defs (df->entry_block_defs);
598 df_get_exit_block_use_set (df->exit_block_uses);
599 df_record_exit_block_uses (df->exit_block_uses);
600 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
601 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
606 unsigned int bb_index = bb->index;
607 df_bb_refs_record (bb_index, true);
612 /* Create a new ref of type DF_REF_TYPE for register REG at address
613 LOC within INSN of BB. */
616 df_ref_create (rtx reg, rtx *loc, rtx insn,
618 enum df_ref_type ref_type,
619 enum df_ref_flags ref_flags)
622 struct df_reg_info **reg_info;
623 struct df_ref_info *ref_info;
624 struct df_ref **ref_rec;
625 struct df_ref ***ref_rec_ptr;
626 unsigned int count = 0;
631 /* You cannot hack artificial refs. */
633 ref = df_ref_create_structure (NULL, reg, loc, bb, insn,
634 ref_type, ref_flags);
636 if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
638 reg_info = df->def_regs;
639 ref_info = &df->def_info;
640 ref_rec_ptr = &DF_INSN_DEFS (insn);
641 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
643 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
645 reg_info = df->eq_use_regs;
646 ref_info = &df->use_info;
647 ref_rec_ptr = &DF_INSN_EQ_USES (insn);
648 switch (ref_info->ref_order)
650 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
651 case DF_REF_ORDER_BY_REG_WITH_NOTES:
652 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
656 add_to_table = false;
662 reg_info = df->use_regs;
663 ref_info = &df->use_info;
664 ref_rec_ptr = &DF_INSN_USES (insn);
665 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
668 /* Do not add if ref is not in the right blocks. */
669 if (add_to_table && df->analyze_subset)
670 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
672 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
675 switch (ref_info->ref_order)
677 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
678 case DF_REF_ORDER_BY_REG_WITH_NOTES:
679 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
680 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
683 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
687 ref_rec = *ref_rec_ptr;
694 ref_rec = *ref_rec_ptr;
697 ref_rec = xrealloc (ref_rec, (count+2) * sizeof (struct df_ref*));
698 *ref_rec_ptr = ref_rec;
699 ref_rec[count] = ref;
700 ref_rec[count+1] = NULL;
701 qsort (ref_rec, count + 1, sizeof (struct df_ref *), df_ref_compare);
705 struct df_ref **ref_rec = XNEWVEC (struct df_ref*, 2);
708 *ref_rec_ptr = ref_rec;
714 fprintf (dump_file, "adding ref ");
715 df_ref_debug (ref, dump_file);
718 /* By adding the ref directly, df_insn_rescan my not find any
719 differences even though the block will have changed. So we need
720 to mark the block dirty ourselves. */
721 df_set_bb_dirty (bb);
728 /*----------------------------------------------------------------------------
729 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
730 ----------------------------------------------------------------------------*/
733 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
734 Also delete the def-use or use-def chain if it exists. */
737 df_reg_chain_unlink (struct df_ref *ref)
739 struct df_ref *next = DF_REF_NEXT_REG (ref);
740 struct df_ref *prev = DF_REF_PREV_REG (ref);
741 struct df_scan_problem_data *problem_data
742 = (struct df_scan_problem_data *) df_scan->problem_data;
743 int id = DF_REF_ID (ref);
744 struct df_reg_info *reg_info;
745 struct df_ref **refs = NULL;
747 if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
749 reg_info = DF_REG_DEF_GET (DF_REF_REGNO (ref));
750 refs = df->def_info.refs;
754 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
756 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
757 switch (df->use_info.ref_order)
759 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
760 case DF_REF_ORDER_BY_REG_WITH_NOTES:
761 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
762 refs = df->use_info.refs;
770 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
771 refs = df->use_info.refs;
777 if (df->analyze_subset)
779 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BB (ref)->index))
786 /* Delete any def-use or use-def chains that start here. It is
787 possible that there is trash in this field. This happens for
788 insns that have been deleted when rescanning has been deferred
789 and the chain problem has also been deleted. The chain tear down
790 code skips deleted insns. */
791 if (df_chain && DF_REF_CHAIN (ref))
792 df_chain_unlink (ref);
795 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
797 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
798 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
801 /* Unlink from the reg chain. If there is no prev, this is the
802 first of the list. If not, just join the next and prev. */
804 DF_REF_NEXT_REG (prev) = next;
807 gcc_assert (reg_info->reg_chain == ref);
808 reg_info->reg_chain = next;
811 DF_REF_PREV_REG (next) = prev;
813 pool_free (problem_data->ref_pool, ref);
817 /* Remove REF from VEC. */
820 df_ref_compress_rec (struct df_ref ***vec_ptr, struct df_ref *ref)
822 struct df_ref **vec = *vec_ptr;
826 while (*vec && *vec != ref)
838 *vec_ptr = df_null_ref_rec;
843 /* Unlink REF from all def-use/use-def chains, etc. */
846 df_ref_remove (struct df_ref *ref)
851 fprintf (dump_file, "removing ref ");
852 df_ref_debug (ref, dump_file);
856 if (DF_REF_REG_DEF_P (ref))
858 if (DF_REF_IS_ARTIFICIAL (ref))
860 struct df_scan_bb_info *bb_info
861 = df_scan_get_bb_info (DF_REF_BB (ref)->index);
862 df_ref_compress_rec (&bb_info->artificial_defs, ref);
866 unsigned int uid = DF_REF_INSN_UID (ref);
867 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
868 df_ref_compress_rec (&insn_rec->defs, ref);
873 if (DF_REF_IS_ARTIFICIAL (ref))
875 struct df_scan_bb_info *bb_info
876 = df_scan_get_bb_info (DF_REF_BB (ref)->index);
877 df_ref_compress_rec (&bb_info->artificial_uses, ref);
881 unsigned int uid = DF_REF_INSN_UID (ref);
882 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
884 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
885 df_ref_compress_rec (&insn_rec->eq_uses, ref);
887 df_ref_compress_rec (&insn_rec->uses, ref);
891 /* By deleting the ref directly, df_insn_rescan my not find any
892 differences even though the block will have changed. So we need
893 to mark the block dirty ourselves. */
894 df_set_bb_dirty (DF_REF_BB (ref));
895 df_reg_chain_unlink (ref);
899 /* Create the insn record for INSN. If there was one there, zero it
902 struct df_insn_info *
903 df_insn_create_insn_record (rtx insn)
905 struct df_scan_problem_data *problem_data
906 = (struct df_scan_problem_data *) df_scan->problem_data;
907 struct df_insn_info *insn_rec;
909 df_grow_insn_info ();
910 insn_rec = DF_INSN_GET (insn);
913 insn_rec = pool_alloc (problem_data->insn_pool);
914 DF_INSN_SET (insn, insn_rec);
916 memset (insn_rec, 0, sizeof (struct df_insn_info));
917 insn_rec->insn = insn;
922 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
925 df_ref_chain_delete_du_chain (struct df_ref **ref_rec)
929 struct df_ref *ref = *ref_rec;
930 /* CHAIN is allocated by DF_CHAIN. So make sure to
931 pass df_scan instance for the problem. */
932 if (DF_REF_CHAIN (ref))
933 df_chain_unlink (ref);
939 /* Delete all refs in the ref chain. */
942 df_ref_chain_delete (struct df_ref **ref_rec)
944 struct df_ref **start = ref_rec;
947 df_reg_chain_unlink (*ref_rec);
951 /* If the list is empty, it has a special shared element that is not
958 /* Delete the hardreg chain. */
961 df_mw_hardreg_chain_delete (struct df_mw_hardreg **hardregs)
963 struct df_scan_problem_data *problem_data;
968 problem_data = (struct df_scan_problem_data *) df_scan->problem_data;
972 pool_free (problem_data->mw_reg_pool, *hardregs);
978 /* Delete all of the refs information from INSN. BB must be passed in
979 except when called from df_process_deferred_rescans to mark the block
983 df_insn_delete (basic_block bb, unsigned int uid)
985 struct df_insn_info *insn_info = NULL;
989 df_grow_bb_info (df_scan);
992 /* The block must be marked as dirty now, rather than later as in
993 df_insn_rescan and df_notes_rescan because it may not be there at
994 rescanning time and the mark would blow up. */
996 df_set_bb_dirty (bb);
998 insn_info = DF_INSN_UID_SAFE_GET (uid);
1000 /* The client has deferred rescanning. */
1001 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1005 bitmap_clear_bit (df->insns_to_rescan, uid);
1006 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1007 bitmap_set_bit (df->insns_to_delete, uid);
1010 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
1015 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
1017 bitmap_clear_bit (df->insns_to_delete, uid);
1018 bitmap_clear_bit (df->insns_to_rescan, uid);
1019 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1022 struct df_scan_problem_data *problem_data
1023 = (struct df_scan_problem_data *) df_scan->problem_data;
1025 /* In general, notes do not have the insn_info fields
1026 initialized. However, combine deletes insns by changing them
1027 to notes. How clever. So we cannot just check if it is a
1028 valid insn before short circuiting this code, we need to see
1029 if we actually initialized it. */
1030 if (insn_info->defs)
1032 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1036 df_ref_chain_delete_du_chain (insn_info->defs);
1037 df_ref_chain_delete_du_chain (insn_info->uses);
1038 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1041 df_ref_chain_delete (insn_info->defs);
1042 df_ref_chain_delete (insn_info->uses);
1043 df_ref_chain_delete (insn_info->eq_uses);
1045 pool_free (problem_data->insn_pool, insn_info);
1046 DF_INSN_UID_SET (uid, NULL);
1051 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
1054 df_free_collection_rec (struct df_collection_rec *collection_rec)
1056 struct df_scan_problem_data *problem_data
1057 = (struct df_scan_problem_data *) df_scan->problem_data;
1058 struct df_ref **ref;
1059 struct df_mw_hardreg **mw;
1061 if (collection_rec->def_vec)
1062 for (ref = collection_rec->def_vec; *ref; ref++)
1063 pool_free (problem_data->ref_pool, *ref);
1064 if (collection_rec->use_vec)
1065 for (ref = collection_rec->use_vec; *ref; ref++)
1066 pool_free (problem_data->ref_pool, *ref);
1067 if (collection_rec->eq_use_vec)
1068 for (ref = collection_rec->eq_use_vec; *ref; ref++)
1069 pool_free (problem_data->ref_pool, *ref);
1070 if (collection_rec->mw_vec)
1071 for (mw = collection_rec->mw_vec; *mw; mw++)
1072 pool_free (problem_data->mw_reg_pool, *mw);
1076 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1079 df_insn_rescan (rtx insn)
1081 unsigned int uid = INSN_UID (insn);
1082 struct df_insn_info *insn_info = NULL;
1083 basic_block bb = BLOCK_FOR_INSN (insn);
1084 struct df_collection_rec collection_rec;
1085 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
1086 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
1087 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
1088 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
1090 if ((!df) || (!INSN_P (insn)))
1096 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1100 /* The client has disabled rescanning and plans to do it itself. */
1101 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1104 df_grow_bb_info (df_scan);
1105 df_grow_reg_info ();
1107 insn_info = DF_INSN_UID_SAFE_GET (uid);
1109 /* The client has deferred rescanning. */
1110 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1114 insn_info = df_insn_create_insn_record (insn);
1115 insn_info->defs = df_null_ref_rec;
1116 insn_info->uses = df_null_ref_rec;
1117 insn_info->eq_uses = df_null_ref_rec;
1118 insn_info->mw_hardregs = df_null_mw_rec;
1121 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1123 bitmap_clear_bit (df->insns_to_delete, uid);
1124 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1125 bitmap_set_bit (df->insns_to_rescan, INSN_UID (insn));
1129 bitmap_clear_bit (df->insns_to_delete, uid);
1130 bitmap_clear_bit (df->insns_to_rescan, uid);
1131 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1134 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1135 /* If there's no change, return false. */
1138 df_free_collection_rec (&collection_rec);
1140 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1144 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1146 /* There's change - we need to delete the existing info. */
1147 df_insn_delete (NULL, uid);
1148 df_insn_create_insn_record (insn);
1152 df_insn_create_insn_record (insn);
1153 df_insn_refs_collect (&collection_rec, bb, insn);
1155 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1158 df_refs_add_to_chains (&collection_rec, bb, insn);
1159 df_set_bb_dirty (bb);
1164 /* Rescan all of the insns in the function. Note that the artificial
1165 uses and defs are not touched. This function will destroy def-se
1166 or use-def chains. */
1169 df_insn_rescan_all (void)
1171 bool no_insn_rescan = false;
1172 bool defer_insn_rescan = false;
1176 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1178 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1180 df_clear_flags (DF_NO_INSN_RESCAN);
1181 no_insn_rescan = true;
1184 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1186 df_clear_flags (DF_DEFER_INSN_RESCAN);
1187 defer_insn_rescan = true;
1190 bitmap_copy (tmp, df->insns_to_delete);
1191 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1193 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1195 df_insn_delete (NULL, uid);
1199 bitmap_clear (df->insns_to_delete);
1200 bitmap_clear (df->insns_to_rescan);
1201 bitmap_clear (df->insns_to_notes_rescan);
1206 FOR_BB_INSNS (bb, insn)
1208 df_insn_rescan (insn);
1213 df_set_flags (DF_NO_INSN_RESCAN);
1214 if (defer_insn_rescan)
1215 df_set_flags (DF_DEFER_INSN_RESCAN);
1219 /* Process all of the deferred rescans or deletions. */
1222 df_process_deferred_rescans (void)
1224 bool no_insn_rescan = false;
1225 bool defer_insn_rescan = false;
1228 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1230 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1232 df_clear_flags (DF_NO_INSN_RESCAN);
1233 no_insn_rescan = true;
1236 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1238 df_clear_flags (DF_DEFER_INSN_RESCAN);
1239 defer_insn_rescan = true;
1243 fprintf (dump_file, "starting the processing of deferred insns\n");
1245 bitmap_copy (tmp, df->insns_to_delete);
1246 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1248 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1250 df_insn_delete (NULL, uid);
1253 bitmap_copy (tmp, df->insns_to_rescan);
1254 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1256 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1258 df_insn_rescan (insn_info->insn);
1261 bitmap_copy (tmp, df->insns_to_notes_rescan);
1262 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1264 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1266 df_notes_rescan (insn_info->insn);
1270 fprintf (dump_file, "ending the processing of deferred insns\n");
1273 bitmap_clear (df->insns_to_delete);
1274 bitmap_clear (df->insns_to_rescan);
1275 bitmap_clear (df->insns_to_notes_rescan);
1278 df_set_flags (DF_NO_INSN_RESCAN);
1279 if (defer_insn_rescan)
1280 df_set_flags (DF_DEFER_INSN_RESCAN);
1282 /* If someone changed regs_ever_live during this pass, fix up the
1283 entry and exit blocks. */
1284 if (df->redo_entry_and_exit)
1286 df_update_entry_exit_and_calls ();
1287 df->redo_entry_and_exit = false;
1292 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1293 the uses if INCLUDE_USES. Include the eq_uses if
1297 df_count_refs (bool include_defs, bool include_uses,
1298 bool include_eq_uses)
1302 unsigned int m = df->regs_inited;
1304 for (regno = 0; regno < m; regno++)
1307 size += DF_REG_DEF_COUNT (regno);
1309 size += DF_REG_USE_COUNT (regno);
1310 if (include_eq_uses)
1311 size += DF_REG_EQ_USE_COUNT (regno);
1317 /* Take build ref table for either the uses or defs from the reg-use
1318 or reg-def chains. This version processes the refs in reg order
1319 which is likely to be best if processing the whole function. */
1322 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1325 bool include_eq_uses)
1327 unsigned int m = df->regs_inited;
1329 unsigned int offset = 0;
1332 if (df->changeable_flags & DF_NO_HARD_REGS)
1334 start = FIRST_PSEUDO_REGISTER;
1335 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1336 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1341 ref_info->total_size
1342 = df_count_refs (include_defs, include_uses, include_eq_uses);
1344 df_check_and_grow_ref_info (ref_info, 1);
1346 for (regno = start; regno < m; regno++)
1349 ref_info->begin[regno] = offset;
1352 struct df_ref *ref = DF_REG_DEF_CHAIN (regno);
1355 ref_info->refs[offset] = ref;
1356 DF_REF_ID (ref) = offset++;
1358 ref = DF_REF_NEXT_REG (ref);
1359 gcc_assert (offset < ref_info->refs_size);
1364 struct df_ref *ref = DF_REG_USE_CHAIN (regno);
1367 ref_info->refs[offset] = ref;
1368 DF_REF_ID (ref) = offset++;
1370 ref = DF_REF_NEXT_REG (ref);
1371 gcc_assert (offset < ref_info->refs_size);
1374 if (include_eq_uses)
1376 struct df_ref *ref = DF_REG_EQ_USE_CHAIN (regno);
1379 ref_info->refs[offset] = ref;
1380 DF_REF_ID (ref) = offset++;
1382 ref = DF_REF_NEXT_REG (ref);
1383 gcc_assert (offset < ref_info->refs_size);
1386 ref_info->count[regno] = count;
1389 /* The bitmap size is not decremented when refs are deleted. So
1390 reset it now that we have squished out all of the empty
1392 ref_info->table_size = offset;
1396 /* Take build ref table for either the uses or defs from the reg-use
1397 or reg-def chains. This version processes the refs in insn order
1398 which is likely to be best if processing some segment of the
1402 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1405 bool include_eq_uses)
1408 unsigned int bb_index;
1409 unsigned int m = df->regs_inited;
1410 unsigned int offset = 0;
1413 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1415 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1416 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1418 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1419 df_check_and_grow_ref_info (ref_info, 1);
1421 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1423 basic_block bb = BASIC_BLOCK (bb_index);
1425 struct df_ref **ref_rec;
1428 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1430 unsigned int regno = DF_REF_REGNO (*ref_rec);
1431 ref_info->count[regno]++;
1434 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1436 unsigned int regno = DF_REF_REGNO (*ref_rec);
1437 ref_info->count[regno]++;
1440 FOR_BB_INSNS (bb, insn)
1444 unsigned int uid = INSN_UID (insn);
1447 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1449 unsigned int regno = DF_REF_REGNO (*ref_rec);
1450 ref_info->count[regno]++;
1453 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1455 unsigned int regno = DF_REF_REGNO (*ref_rec);
1456 ref_info->count[regno]++;
1458 if (include_eq_uses)
1459 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1461 unsigned int regno = DF_REF_REGNO (*ref_rec);
1462 ref_info->count[regno]++;
1468 for (r = start; r < m; r++)
1470 ref_info->begin[r] = offset;
1471 offset += ref_info->count[r];
1472 ref_info->count[r] = 0;
1475 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1477 basic_block bb = BASIC_BLOCK (bb_index);
1479 struct df_ref **ref_rec;
1482 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1484 struct df_ref *ref = *ref_rec;
1485 unsigned int regno = DF_REF_REGNO (ref);
1489 = ref_info->begin[regno] + ref_info->count[regno]++;
1490 DF_REF_ID (ref) = id;
1491 ref_info->refs[id] = ref;
1495 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1497 struct df_ref *ref = *ref_rec;
1498 unsigned int regno = DF_REF_REGNO (ref);
1502 = ref_info->begin[regno] + ref_info->count[regno]++;
1503 DF_REF_ID (ref) = id;
1504 ref_info->refs[id] = ref;
1508 FOR_BB_INSNS (bb, insn)
1512 unsigned int uid = INSN_UID (insn);
1515 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1517 struct df_ref *ref = *ref_rec;
1518 unsigned int regno = DF_REF_REGNO (ref);
1522 = ref_info->begin[regno] + ref_info->count[regno]++;
1523 DF_REF_ID (ref) = id;
1524 ref_info->refs[id] = ref;
1528 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1530 struct df_ref *ref = *ref_rec;
1531 unsigned int regno = DF_REF_REGNO (ref);
1535 = ref_info->begin[regno] + ref_info->count[regno]++;
1536 DF_REF_ID (ref) = id;
1537 ref_info->refs[id] = ref;
1540 if (include_eq_uses)
1541 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1543 struct df_ref *ref = *ref_rec;
1544 unsigned int regno = DF_REF_REGNO (ref);
1548 = ref_info->begin[regno] + ref_info->count[regno]++;
1549 DF_REF_ID (ref) = id;
1550 ref_info->refs[id] = ref;
1557 /* The bitmap size is not decremented when refs are deleted. So
1558 reset it now that we have squished out all of the empty
1561 ref_info->table_size = offset;
1564 /* Take build ref table for either the uses or defs from the reg-use
1565 or reg-def chains. */
1568 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1571 bool include_eq_uses)
1573 if (df->analyze_subset)
1574 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1575 include_uses, include_eq_uses);
1577 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1578 include_uses, include_eq_uses);
1582 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1584 df_add_refs_to_table (unsigned int offset,
1585 struct df_ref_info *ref_info,
1586 struct df_ref **ref_vec)
1590 struct df_ref *ref = *ref_vec;
1591 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
1592 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1594 ref_info->refs[offset] = ref;
1595 DF_REF_ID (*ref_vec) = offset++;
1603 /* Count the number of refs in all of the insns of BB. Include the
1604 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1605 eq_uses if INCLUDE_EQ_USES. */
1608 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1609 struct df_ref_info *ref_info,
1610 bool include_defs, bool include_uses,
1611 bool include_eq_uses)
1616 offset = df_add_refs_to_table (offset, ref_info,
1617 df_get_artificial_defs (bb->index));
1619 offset = df_add_refs_to_table (offset, ref_info,
1620 df_get_artificial_uses (bb->index));
1622 FOR_BB_INSNS (bb, insn)
1625 unsigned int uid = INSN_UID (insn);
1627 offset = df_add_refs_to_table (offset, ref_info,
1628 DF_INSN_UID_DEFS (uid));
1630 offset = df_add_refs_to_table (offset, ref_info,
1631 DF_INSN_UID_USES (uid));
1632 if (include_eq_uses)
1633 offset = df_add_refs_to_table (offset, ref_info,
1634 DF_INSN_UID_EQ_USES (uid));
1640 /* Organize the refs by insn into the table in REF_INFO. If
1641 blocks_to_analyze is defined, use that set, otherwise the entire
1642 program. Include the defs if INCLUDE_DEFS. Include the uses if
1643 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1646 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1647 bool include_defs, bool include_uses,
1648 bool include_eq_uses)
1651 unsigned int offset = 0;
1653 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1654 df_check_and_grow_ref_info (ref_info, 1);
1655 if (df->blocks_to_analyze)
1660 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1662 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK (index), offset, ref_info,
1663 include_defs, include_uses,
1667 ref_info->table_size = offset;
1672 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1673 include_defs, include_uses,
1675 ref_info->table_size = offset;
1680 /* If the use refs in DF are not organized, reorganize them. */
1683 df_maybe_reorganize_use_refs (enum df_ref_order order)
1685 if (order == df->use_info.ref_order)
1690 case DF_REF_ORDER_BY_REG:
1691 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1694 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1695 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1698 case DF_REF_ORDER_BY_INSN:
1699 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1702 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1703 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1706 case DF_REF_ORDER_NO_TABLE:
1707 free (df->use_info.refs);
1708 df->use_info.refs = NULL;
1709 df->use_info.refs_size = 0;
1712 case DF_REF_ORDER_UNORDERED:
1713 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1718 df->use_info.ref_order = order;
1722 /* If the def refs in DF are not organized, reorganize them. */
1725 df_maybe_reorganize_def_refs (enum df_ref_order order)
1727 if (order == df->def_info.ref_order)
1732 case DF_REF_ORDER_BY_REG:
1733 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1736 case DF_REF_ORDER_BY_INSN:
1737 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1740 case DF_REF_ORDER_NO_TABLE:
1741 free (df->def_info.refs);
1742 df->def_info.refs = NULL;
1743 df->def_info.refs_size = 0;
1746 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1747 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1748 case DF_REF_ORDER_UNORDERED:
1749 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1754 df->def_info.ref_order = order;
1758 /* Change the BB of all refs in the ref chain to NEW_BB.
1759 Assumes that all refs in the chain have the same BB.
1760 If changed, return the original bb the chain belonged to
1762 If no change, return NEW_BB.
1763 If something's wrong, it will return NULL. */
1766 df_ref_chain_change_bb (struct df_ref **ref_rec,
1772 struct df_ref *ref = *ref_rec;
1774 if (DF_REF_BB (ref) == new_bb)
1778 gcc_assert (old_bb == NULL || DF_REF_BB (ref) == old_bb);
1779 old_bb = DF_REF_BB (ref);
1780 DF_REF_BB (ref) = new_bb;
1789 /* Change all of the basic block references in INSN to use the insn's
1790 current basic block. This function is called from routines that move
1791 instructions from one block to another. */
1794 df_insn_change_bb (rtx insn)
1796 basic_block new_bb = BLOCK_FOR_INSN (insn);
1797 basic_block old_bb = NULL;
1798 struct df_insn_info *insn_info;
1799 unsigned int uid = INSN_UID (insn);
1805 fprintf (dump_file, "changing bb of uid %d\n", uid);
1807 insn_info = DF_INSN_UID_SAFE_GET (uid);
1808 if (insn_info == NULL)
1811 fprintf (dump_file, " unscanned insn\n");
1812 df_insn_rescan (insn);
1819 old_bb = df_ref_chain_change_bb (insn_info->defs, old_bb, new_bb);
1820 if (old_bb == new_bb)
1823 old_bb = df_ref_chain_change_bb (insn_info->uses, old_bb, new_bb);
1824 if (old_bb == new_bb)
1827 old_bb = df_ref_chain_change_bb (insn_info->eq_uses, old_bb, new_bb);
1828 if (old_bb == new_bb)
1831 df_set_bb_dirty (new_bb);
1835 fprintf (dump_file, " from %d to %d\n",
1836 old_bb->index, new_bb->index);
1837 df_set_bb_dirty (old_bb);
1841 fprintf (dump_file, " to %d\n", new_bb->index);
1845 /* Helper function for df_ref_change_reg_with_loc. */
1848 df_ref_change_reg_with_loc_1 (struct df_reg_info *old, struct df_reg_info *new,
1849 int new_regno, rtx loc)
1851 struct df_ref *the_ref = old->reg_chain;
1855 if (DF_REF_LOC(the_ref) && (*DF_REF_LOC(the_ref) == loc))
1857 struct df_ref *next_ref = the_ref->next_reg;
1858 struct df_ref *prev_ref = the_ref->prev_reg;
1859 struct df_ref **ref_vec, **ref_vec_t;
1860 unsigned int count = 0;
1862 DF_REF_REGNO (the_ref) = new_regno;
1863 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1865 /* Pull the_ref out of the old regno chain. */
1867 prev_ref->next_reg = next_ref;
1869 old->reg_chain = next_ref;
1871 next_ref->prev_reg = prev_ref;
1874 /* Put the ref into the new regno chain. */
1875 the_ref->prev_reg = NULL;
1876 the_ref->next_reg = new->reg_chain;
1878 new->reg_chain->prev_reg = the_ref;
1879 new->reg_chain = the_ref;
1881 df_set_bb_dirty (DF_REF_BB (the_ref));
1883 /* Need to resort the record that the ref was in because the
1884 regno is a sorting key. First, find the right record. */
1885 if (DF_REF_IS_ARTIFICIAL (the_ref))
1887 unsigned int bb_index = DF_REF_BB (the_ref)->index;
1888 if (DF_REF_REG_DEF_P (the_ref))
1889 ref_vec = df_get_artificial_defs (bb_index);
1891 ref_vec = df_get_artificial_uses (bb_index);
1895 struct df_insn_info *insn_info
1896 = DF_INSN_GET (DF_REF_INSN (the_ref));
1897 if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1898 ref_vec = insn_info->eq_uses;
1900 ref_vec = insn_info->uses;
1902 fprintf (dump_file, "changing reg in insn %d\n",
1903 INSN_UID (DF_REF_INSN (the_ref)));
1905 ref_vec_t = ref_vec;
1907 /* Find the length. */
1913 qsort (ref_vec, count, sizeof (struct df_ref *), df_ref_compare);
1918 the_ref = the_ref->next_reg;
1923 /* Change the regno of all refs that contained LOC from OLD_REGNO to
1924 NEW_REGNO. Refs that do not match LOC are not changed. This call
1925 is to support the SET_REGNO macro. */
1928 df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
1930 if ((!df) || (old_regno == -1) || (old_regno == new_regno))
1933 df_grow_reg_info ();
1935 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1936 DF_REG_DEF_GET (new_regno), new_regno, loc);
1937 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1938 DF_REG_USE_GET (new_regno), new_regno, loc);
1939 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1940 DF_REG_EQ_USE_GET (new_regno), new_regno, loc);
1944 /* Delete the mw_hardregs that point into the eq_notes. */
1947 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1949 struct df_mw_hardreg **mw_vec = insn_info->mw_hardregs;
1950 unsigned int deleted = 0;
1951 unsigned int count = 0;
1952 struct df_scan_problem_data *problem_data
1953 = (struct df_scan_problem_data *) df_scan->problem_data;
1960 if ((*mw_vec)->flags & DF_REF_IN_NOTE)
1962 struct df_mw_hardreg **temp_vec = mw_vec;
1964 pool_free (problem_data->mw_reg_pool, *mw_vec);
1966 /* Shove the remaining ones down one to fill the gap. While
1967 this looks n**2, it is highly unusual to have any mw regs
1968 in eq_notes and the chances of more than one are almost
1972 *temp_vec = *(temp_vec + 1);
1986 free (insn_info->mw_hardregs);
1987 insn_info->mw_hardregs = df_null_mw_rec;
1994 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1997 df_notes_rescan (rtx insn)
1999 struct df_insn_info *insn_info;
2000 unsigned int uid = INSN_UID (insn);
2005 /* The client has disabled rescanning and plans to do it itself. */
2006 if (df->changeable_flags & DF_NO_INSN_RESCAN)
2009 df_grow_bb_info (df_scan);
2010 df_grow_reg_info ();
2012 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID(insn));
2014 /* The client has deferred rescanning. */
2015 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
2019 insn_info = df_insn_create_insn_record (insn);
2020 insn_info->defs = df_null_ref_rec;
2021 insn_info->uses = df_null_ref_rec;
2022 insn_info->eq_uses = df_null_ref_rec;
2023 insn_info->mw_hardregs = df_null_mw_rec;
2026 bitmap_clear_bit (df->insns_to_delete, uid);
2027 /* If the insn is set to be rescanned, it does not need to also
2028 be notes rescanned. */
2029 if (!bitmap_bit_p (df->insns_to_rescan, uid))
2030 bitmap_set_bit (df->insns_to_notes_rescan, INSN_UID (insn));
2034 bitmap_clear_bit (df->insns_to_delete, uid);
2035 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
2039 basic_block bb = BLOCK_FOR_INSN (insn);
2041 struct df_collection_rec collection_rec;
2042 unsigned int num_deleted;
2044 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
2045 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
2046 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 1000);
2048 num_deleted = df_mw_hardreg_chain_delete_eq_uses (insn_info);
2049 df_ref_chain_delete (insn_info->eq_uses);
2050 insn_info->eq_uses = NULL;
2052 /* Process REG_EQUIV/REG_EQUAL notes */
2053 for (note = REG_NOTES (insn); note;
2054 note = XEXP (note, 1))
2056 switch (REG_NOTE_KIND (note))
2060 df_uses_record (&collection_rec,
2061 &XEXP (note, 0), DF_REF_REG_USE,
2062 bb, insn, DF_REF_IN_NOTE);
2068 /* Find some place to put any new mw_hardregs. */
2069 df_canonize_collection_rec (&collection_rec);
2070 if (collection_rec.next_mw)
2072 unsigned int count = 0;
2073 struct df_mw_hardreg **mw_rec = insn_info->mw_hardregs;
2082 /* Append to the end of the existing record after
2083 expanding it if necessary. */
2084 if (collection_rec.next_mw > num_deleted)
2086 insn_info->mw_hardregs =
2087 xrealloc (insn_info->mw_hardregs,
2088 (count + 1 + collection_rec.next_mw)
2089 * sizeof (struct df_ref*));
2091 memcpy (&insn_info->mw_hardregs[count], collection_rec.mw_vec,
2092 (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2093 qsort (insn_info->mw_hardregs, count + collection_rec.next_mw,
2094 sizeof (struct df_mw_hardreg *), df_mw_compare);
2098 /* No vector there. */
2099 insn_info->mw_hardregs
2100 = XNEWVEC (struct df_mw_hardreg*,
2101 count + 1 + collection_rec.next_mw);
2102 memcpy (insn_info->mw_hardregs, collection_rec.mw_vec,
2103 (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2106 /* Get rid of the mw_rec so that df_refs_add_to_chains will
2108 collection_rec.mw_vec = NULL;
2109 collection_rec.next_mw = 0;
2110 df_refs_add_to_chains (&collection_rec, bb, insn);
2113 df_insn_rescan (insn);
2118 /*----------------------------------------------------------------------------
2119 Hard core instruction scanning code. No external interfaces here,
2120 just a lot of routines that look inside insns.
2121 ----------------------------------------------------------------------------*/
2124 /* Return true if the contents of two df_ref's are identical.
2125 It ignores DF_REF_MARKER. */
2128 df_ref_equal_p (struct df_ref *ref1, struct df_ref *ref2)
2132 return (ref1 == ref2) ||
2133 (DF_REF_REG (ref1) == DF_REF_REG (ref2)
2134 && DF_REF_REGNO (ref1) == DF_REF_REGNO (ref2)
2135 && DF_REF_LOC (ref1) == DF_REF_LOC (ref2)
2136 && DF_REF_INSN (ref1) == DF_REF_INSN (ref2)
2137 && DF_REF_TYPE (ref1) == DF_REF_TYPE (ref2)
2138 && ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2139 == (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2140 && DF_REF_BB (ref1) == DF_REF_BB (ref2));
2144 /* Compare REF1 and REF2 for sorting. This is only called from places
2145 where all of the refs are of the same type, in the same insn, and
2146 have the same bb. So these fields are not checked. */
2149 df_ref_compare (const void *r1, const void *r2)
2151 const struct df_ref *ref1 = *(struct df_ref **)r1;
2152 const struct df_ref *ref2 = *(struct df_ref **)r2;
2157 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2158 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2160 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2161 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2163 if ((DF_REF_REG (ref1) != DF_REF_REG (ref2))
2164 || (DF_REF_LOC (ref1) != DF_REF_LOC (ref2)))
2165 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2167 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2169 /* If two refs are identical except that one of them has is from
2170 a mw and one is not, we need to have the one with the mw
2172 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2173 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2174 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2175 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2184 df_swap_refs (struct df_ref **ref_vec, int i, int j)
2186 struct df_ref *tmp = ref_vec[i];
2187 ref_vec[i] = ref_vec[j];
2191 /* Sort and compress a set of refs. */
2194 df_sort_and_compress_refs (struct df_ref **ref_vec, unsigned int count)
2196 struct df_scan_problem_data *problem_data
2197 = (struct df_scan_problem_data *) df_scan->problem_data;
2199 unsigned int dist = 0;
2201 ref_vec[count] = NULL;
2202 /* If there are 1 or 0 elements, there is nothing to do. */
2205 else if (count == 2)
2207 if (df_ref_compare (&ref_vec[0], &ref_vec[1]) > 0)
2208 df_swap_refs (ref_vec, 0, 1);
2212 for (i = 0; i < count - 1; i++)
2213 if (df_ref_compare (&ref_vec[i], &ref_vec[i+1]) >= 0)
2215 /* If the array is already strictly ordered,
2216 which is the most common case for large COUNT case
2217 (which happens for CALL INSNs),
2218 no need to sort and filter out duplicate.
2219 Simply return the count.
2220 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2221 of DF_REF_COMPARE. */
2224 qsort (ref_vec, count, sizeof (struct df_ref *), df_ref_compare);
2227 for (i=0; i<count-dist; i++)
2229 /* Find the next ref that is not equal to the current ref. */
2230 while (df_ref_equal_p (ref_vec[i], ref_vec[i + dist + 1]))
2232 pool_free (problem_data->ref_pool, ref_vec[i + dist + 1]);
2235 /* Copy it down to the next position. */
2237 ref_vec[i+1] = ref_vec[i + dist + 1];
2241 ref_vec[count] = NULL;
2246 /* Return true if the contents of two df_ref's are identical.
2247 It ignores DF_REF_MARKER. */
2250 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2254 return (mw1 == mw2) ||
2255 (mw1->mw_reg == mw2->mw_reg
2256 && mw1->type == mw2->type
2257 && mw1->flags == mw2->flags
2258 && mw1->start_regno == mw2->start_regno
2259 && mw1->end_regno == mw2->end_regno);
2263 /* Compare MW1 and MW2 for sorting. */
2266 df_mw_compare (const void *m1, const void *m2)
2268 const struct df_mw_hardreg *mw1 = *(struct df_mw_hardreg **)m1;
2269 const struct df_mw_hardreg *mw2 = *(struct df_mw_hardreg **)m2;
2274 if (mw1->type != mw2->type)
2275 return mw1->type - mw2->type;
2277 if (mw1->flags != mw2->flags)
2278 return mw1->flags - mw2->flags;
2280 if (mw1->start_regno != mw2->start_regno)
2281 return mw1->start_regno - mw2->start_regno;
2283 if (mw1->end_regno != mw2->end_regno)
2284 return mw1->end_regno - mw2->end_regno;
2286 if (mw1->mw_reg != mw2->mw_reg)
2287 return mw1->mw_order - mw2->mw_order;
2293 /* Sort and compress a set of refs. */
2296 df_sort_and_compress_mws (struct df_mw_hardreg **mw_vec, unsigned int count)
2298 struct df_scan_problem_data *problem_data
2299 = (struct df_scan_problem_data *) df_scan->problem_data;
2301 unsigned int dist = 0;
2302 mw_vec[count] = NULL;
2306 else if (count == 2)
2308 if (df_mw_compare (&mw_vec[0], &mw_vec[1]) > 0)
2310 struct df_mw_hardreg *tmp = mw_vec[0];
2311 mw_vec[0] = mw_vec[1];
2316 qsort (mw_vec, count, sizeof (struct df_mw_hardreg *), df_mw_compare);
2318 for (i=0; i<count-dist; i++)
2320 /* Find the next ref that is not equal to the current ref. */
2321 while (df_mw_equal_p (mw_vec[i], mw_vec[i + dist + 1]))
2323 pool_free (problem_data->mw_reg_pool, mw_vec[i + dist + 1]);
2326 /* Copy it down to the next position. */
2328 mw_vec[i+1] = mw_vec[i + dist + 1];
2332 mw_vec[count] = NULL;
2337 /* Sort and remove duplicates from the COLLECTION_REC. */
2340 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2342 if (collection_rec->def_vec)
2343 collection_rec->next_def
2344 = df_sort_and_compress_refs (collection_rec->def_vec,
2345 collection_rec->next_def);
2346 if (collection_rec->use_vec)
2347 collection_rec->next_use
2348 = df_sort_and_compress_refs (collection_rec->use_vec,
2349 collection_rec->next_use);
2350 if (collection_rec->eq_use_vec)
2351 collection_rec->next_eq_use
2352 = df_sort_and_compress_refs (collection_rec->eq_use_vec,
2353 collection_rec->next_eq_use);
2354 if (collection_rec->mw_vec)
2355 collection_rec->next_mw
2356 = df_sort_and_compress_mws (collection_rec->mw_vec,
2357 collection_rec->next_mw);
2361 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2364 df_install_ref (struct df_ref *this_ref,
2365 struct df_reg_info *reg_info,
2366 struct df_ref_info *ref_info,
2369 unsigned int regno = DF_REF_REGNO (this_ref);
2370 /* Add the ref to the reg_{def,use,eq_use} chain. */
2371 struct df_ref *head = reg_info->reg_chain;
2373 reg_info->reg_chain = this_ref;
2376 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2378 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2379 df->hard_regs_live_count[regno]++;
2382 gcc_assert (DF_REF_NEXT_REG (this_ref) == NULL);
2383 gcc_assert (DF_REF_PREV_REG (this_ref) == NULL);
2385 DF_REF_NEXT_REG (this_ref) = head;
2387 /* We cannot actually link to the head of the chain. */
2388 DF_REF_PREV_REG (this_ref) = NULL;
2391 DF_REF_PREV_REG (head) = this_ref;
2395 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2396 df_check_and_grow_ref_info (ref_info, 1);
2397 DF_REF_ID (this_ref) = ref_info->table_size;
2398 /* Add the ref to the big array of defs. */
2399 ref_info->refs[ref_info->table_size] = this_ref;
2400 ref_info->table_size++;
2403 DF_REF_ID (this_ref) = -1;
2405 ref_info->total_size++;
2409 /* This function takes one of the groups of refs (defs, uses or
2410 eq_uses) and installs the entire group into the insn. It also adds
2411 each of these refs into the appropriate chains. */
2413 static struct df_ref **
2414 df_install_refs (basic_block bb,
2415 struct df_ref **old_vec, unsigned int count,
2416 struct df_reg_info **reg_info,
2417 struct df_ref_info *ref_info,
2423 struct df_ref **new_vec = XNEWVEC (struct df_ref*, count + 1);
2426 switch (ref_info->ref_order)
2428 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2429 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2430 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2431 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2432 add_to_table = true;
2434 case DF_REF_ORDER_UNORDERED:
2435 case DF_REF_ORDER_BY_REG:
2436 case DF_REF_ORDER_BY_INSN:
2437 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2438 add_to_table = !is_notes;
2441 add_to_table = false;
2445 /* Do not add if ref is not in the right blocks. */
2446 if (add_to_table && df->analyze_subset)
2447 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2449 for (i = 0; i < count; i++)
2451 struct df_ref *this_ref = old_vec[i];
2452 new_vec[i] = this_ref;
2453 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2454 ref_info, add_to_table);
2457 new_vec[count] = NULL;
2461 return df_null_ref_rec;
2465 /* This function takes the mws installs the entire group into the
2468 static struct df_mw_hardreg **
2469 df_install_mws (struct df_mw_hardreg **old_vec, unsigned int count)
2473 struct df_mw_hardreg **new_vec
2474 = XNEWVEC (struct df_mw_hardreg*, count + 1);
2475 memcpy (new_vec, old_vec,
2476 sizeof (struct df_mw_hardreg*) * (count + 1));
2480 return df_null_mw_rec;
2484 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2485 chains and update other necessary information. */
2488 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2489 basic_block bb, rtx insn)
2493 struct df_insn_info *insn_rec = DF_INSN_GET (insn);
2494 /* If there is a vector in the collection rec, add it to the
2495 insn. A null rec is a signal that the caller will handle the
2497 if (collection_rec->def_vec)
2499 if (insn_rec->defs && *insn_rec->defs)
2500 free (insn_rec->defs);
2502 = df_install_refs (bb, collection_rec->def_vec,
2503 collection_rec->next_def,
2505 &df->def_info, false);
2507 if (collection_rec->use_vec)
2509 if (insn_rec->uses && *insn_rec->uses)
2510 free (insn_rec->uses);
2512 = df_install_refs (bb, collection_rec->use_vec,
2513 collection_rec->next_use,
2515 &df->use_info, false);
2517 if (collection_rec->eq_use_vec)
2519 if (insn_rec->eq_uses && *insn_rec->eq_uses)
2520 free (insn_rec->eq_uses);
2522 = df_install_refs (bb, collection_rec->eq_use_vec,
2523 collection_rec->next_eq_use,
2525 &df->use_info, true);
2527 if (collection_rec->mw_vec)
2529 if (insn_rec->mw_hardregs && *insn_rec->mw_hardregs)
2530 free (insn_rec->mw_hardregs);
2531 insn_rec->mw_hardregs
2532 = df_install_mws (collection_rec->mw_vec,
2533 collection_rec->next_mw);
2538 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2540 if (bb_info->artificial_defs && *bb_info->artificial_defs)
2541 free (bb_info->artificial_defs);
2542 bb_info->artificial_defs
2543 = df_install_refs (bb, collection_rec->def_vec,
2544 collection_rec->next_def,
2546 &df->def_info, false);
2547 if (bb_info->artificial_uses && *bb_info->artificial_uses)
2548 free (bb_info->artificial_uses);
2549 bb_info->artificial_uses
2550 = df_install_refs (bb, collection_rec->use_vec,
2551 collection_rec->next_use,
2553 &df->use_info, false);
2558 /* Allocate a ref and initialize its fields. */
2560 static struct df_ref *
2561 df_ref_create_structure (struct df_collection_rec *collection_rec,
2563 basic_block bb, rtx insn,
2564 enum df_ref_type ref_type,
2565 enum df_ref_flags ref_flags)
2567 struct df_ref *this_ref;
2568 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2569 struct df_scan_problem_data *problem_data
2570 = (struct df_scan_problem_data *) df_scan->problem_data;
2572 this_ref = pool_alloc (problem_data->ref_pool);
2573 DF_REF_ID (this_ref) = -1;
2574 DF_REF_REG (this_ref) = reg;
2575 DF_REF_REGNO (this_ref) = regno;
2576 DF_REF_LOC (this_ref) = loc;
2577 DF_REF_INSN (this_ref) = insn;
2578 DF_REF_CHAIN (this_ref) = NULL;
2579 DF_REF_TYPE (this_ref) = ref_type;
2580 DF_REF_FLAGS (this_ref) = ref_flags;
2581 DF_REF_BB (this_ref) = bb;
2582 DF_REF_NEXT_REG (this_ref) = NULL;
2583 DF_REF_PREV_REG (this_ref) = NULL;
2584 DF_REF_ORDER (this_ref) = df->ref_order++;
2586 /* We need to clear this bit because fwprop, and in the future
2587 possibly other optimizations sometimes create new refs using ond
2588 refs as the model. */
2589 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2591 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2592 if ((regno < FIRST_PSEUDO_REGISTER)
2593 && (!DF_REF_IS_ARTIFICIAL (this_ref)))
2595 if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
2597 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2598 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2600 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2601 && (regno == FRAME_POINTER_REGNUM
2602 || regno == ARG_POINTER_REGNUM)))
2603 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2608 if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
2609 collection_rec->def_vec[collection_rec->next_def++] = this_ref;
2610 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2611 collection_rec->eq_use_vec[collection_rec->next_eq_use++] = this_ref;
2613 collection_rec->use_vec[collection_rec->next_use++] = this_ref;
2620 /* Create new references of type DF_REF_TYPE for each part of register REG
2621 at address LOC within INSN of BB. */
2624 df_ref_record (struct df_collection_rec *collection_rec,
2626 basic_block bb, rtx insn,
2627 enum df_ref_type ref_type,
2628 enum df_ref_flags ref_flags)
2633 gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2635 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2636 if (regno < FIRST_PSEUDO_REGISTER)
2638 struct df_mw_hardreg *hardreg = NULL;
2639 struct df_scan_problem_data *problem_data
2640 = (struct df_scan_problem_data *) df_scan->problem_data;
2642 unsigned int endregno;
2645 if (GET_CODE (reg) == SUBREG)
2647 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2648 SUBREG_BYTE (reg), GET_MODE (reg));
2649 endregno = regno + subreg_nregs (reg);
2652 endregno = END_HARD_REGNO (reg);
2654 /* If this is a multiword hardreg, we create some extra
2655 datastructures that will enable us to easily build REG_DEAD
2656 and REG_UNUSED notes. */
2657 if ((endregno != regno + 1) && insn)
2659 /* Sets to a subreg of a multiword register are partial.
2660 Sets to a non-subreg of a multiword register are not. */
2661 if (GET_CODE (oldreg) == SUBREG)
2662 ref_flags |= DF_REF_PARTIAL;
2663 ref_flags |= DF_REF_MW_HARDREG;
2665 hardreg = pool_alloc (problem_data->mw_reg_pool);
2666 hardreg->type = ref_type;
2667 hardreg->flags = ref_flags;
2668 hardreg->mw_reg = reg;
2670 hardreg->start_regno = regno;
2671 hardreg->end_regno = endregno - 1;
2672 hardreg->mw_order = df->ref_order++;
2673 collection_rec->mw_vec[collection_rec->next_mw++] = hardreg;
2676 for (i = regno; i < endregno; i++)
2678 ref = df_ref_create_structure (collection_rec, regno_reg_rtx[i], loc,
2679 bb, insn, ref_type, ref_flags);
2681 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2687 ref = df_ref_create_structure (collection_rec, reg, loc, bb, insn,
2688 ref_type, ref_flags);
2693 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2694 covered by the outer mode is smaller than that covered by the inner mode,
2695 is a read-modify-write operation.
2696 This function returns true iff the SUBREG X is such a SUBREG. */
2699 df_read_modify_subreg_p (rtx x)
2701 unsigned int isize, osize;
2702 if (GET_CODE (x) != SUBREG)
2704 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2705 osize = GET_MODE_SIZE (GET_MODE (x));
2706 return isize > osize
2707 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2711 /* Process all the registers defined in the rtx, X.
2712 Autoincrement/decrement definitions will be picked up by
2716 df_def_record_1 (struct df_collection_rec *collection_rec,
2717 rtx x, basic_block bb, rtx insn,
2718 enum df_ref_flags flags)
2723 /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
2725 if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
2728 loc = &SET_DEST (x);
2731 /* It is legal to have a set destination be a parallel. */
2732 if (GET_CODE (dst) == PARALLEL)
2736 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2738 rtx temp = XVECEXP (dst, 0, i);
2739 if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
2740 || GET_CODE (temp) == SET)
2741 df_def_record_1 (collection_rec,
2743 GET_CODE (temp) == CLOBBER
2744 ? flags | DF_REF_MUST_CLOBBER : flags);
2749 /* Maybe, we should flag the use of STRICT_LOW_PART somehow. It might
2750 be handy for the reg allocator. */
2751 while (GET_CODE (dst) == STRICT_LOW_PART
2752 || GET_CODE (dst) == ZERO_EXTRACT)
2754 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2755 loc = &XEXP (dst, 0);
2759 if (df_read_modify_subreg_p (dst))
2760 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2763 || (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))))
2764 df_ref_record (collection_rec,
2765 dst, loc, bb, insn, DF_REF_REG_DEF, flags);
2769 /* Process all the registers defined in the pattern rtx, X. */
2772 df_defs_record (struct df_collection_rec *collection_rec,
2773 rtx x, basic_block bb, rtx insn, enum df_ref_flags flags)
2775 RTX_CODE code = GET_CODE (x);
2777 if (code == SET || code == CLOBBER)
2779 /* Mark the single def within the pattern. */
2780 enum df_ref_flags clobber_flags = flags;
2781 clobber_flags |= (code == CLOBBER) ? DF_REF_MUST_CLOBBER : 0;
2782 df_def_record_1 (collection_rec, x, bb, insn, clobber_flags);
2784 else if (code == COND_EXEC)
2786 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2787 bb, insn, DF_REF_CONDITIONAL);
2789 else if (code == PARALLEL)
2793 /* Mark the multiple defs within the pattern. */
2794 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2795 df_defs_record (collection_rec, XVECEXP (x, 0, i), bb, insn, flags);
2800 /* Process all the registers used in the rtx at address LOC. */
2803 df_uses_record (struct df_collection_rec *collection_rec,
2804 rtx *loc, enum df_ref_type ref_type,
2805 basic_block bb, rtx insn, enum df_ref_flags flags)
2814 code = GET_CODE (x);
2830 /* If we are clobbering a MEM, mark any registers inside the address
2832 if (MEM_P (XEXP (x, 0)))
2833 df_uses_record (collection_rec,
2834 &XEXP (XEXP (x, 0), 0),
2835 DF_REF_REG_MEM_STORE, bb, insn, flags);
2837 /* If we're clobbering a REG then we have a def so ignore. */
2841 df_uses_record (collection_rec,
2842 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2843 bb, insn, flags & DF_REF_IN_NOTE);
2847 /* While we're here, optimize this case. */
2848 flags |= DF_REF_PARTIAL;
2849 /* In case the SUBREG is not of a REG, do not optimize. */
2850 if (!REG_P (SUBREG_REG (x)))
2852 loc = &SUBREG_REG (x);
2853 df_uses_record (collection_rec, loc, ref_type, bb, insn, flags);
2856 /* ... Fall through ... */
2859 df_ref_record (collection_rec,
2860 x, loc, bb, insn, ref_type, flags);
2865 rtx dst = SET_DEST (x);
2866 gcc_assert (!(flags & DF_REF_IN_NOTE));
2867 df_uses_record (collection_rec,
2868 &SET_SRC (x), DF_REF_REG_USE, bb, insn, flags);
2870 switch (GET_CODE (dst))
2873 if (df_read_modify_subreg_p (dst))
2875 df_uses_record (collection_rec, &SUBREG_REG (dst),
2876 DF_REF_REG_USE, bb, insn, flags | DF_REF_READ_WRITE);
2887 df_uses_record (collection_rec, &XEXP (dst, 0),
2888 DF_REF_REG_MEM_STORE, bb, insn, flags);
2890 case STRICT_LOW_PART:
2892 rtx *temp = &XEXP (dst, 0);
2893 /* A strict_low_part uses the whole REG and not just the
2895 dst = XEXP (dst, 0);
2896 df_uses_record (collection_rec,
2897 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2898 DF_REF_REG_USE, bb, insn, DF_REF_READ_WRITE);
2903 df_uses_record (collection_rec, &XEXP (dst, 0),
2904 DF_REF_REG_USE, bb, insn, DF_REF_READ_WRITE);
2905 df_uses_record (collection_rec, &XEXP (dst, 1),
2906 DF_REF_REG_USE, bb, insn, flags);
2907 df_uses_record (collection_rec, &XEXP (dst, 2),
2908 DF_REF_REG_USE, bb, insn, flags);
2909 dst = XEXP (dst, 0);
2921 case UNSPEC_VOLATILE:
2925 /* Traditional and volatile asm instructions must be
2926 considered to use and clobber all hard registers, all
2927 pseudo-registers and all of memory. So must TRAP_IF and
2928 UNSPEC_VOLATILE operations.
2930 Consider for instance a volatile asm that changes the fpu
2931 rounding mode. An insn should not be moved across this
2932 even if it only uses pseudo-regs because it might give an
2933 incorrectly rounded result.
2935 However, flow.c's liveness computation did *not* do this,
2936 giving the reasoning as " ?!? Unfortunately, marking all
2937 hard registers as live causes massive problems for the
2938 register allocator and marking all pseudos as live creates
2939 mountains of uninitialized variable warnings."
2941 In order to maintain the status quo with regard to liveness
2942 and uses, we do what flow.c did and just mark any regs we
2943 can find in ASM_OPERANDS as used. In global asm insns are
2944 scanned and regs_asm_clobbered is filled out.
2946 For all ASM_OPERANDS, we must traverse the vector of input
2947 operands. We can not just fall through here since then we
2948 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2949 which do not indicate traditional asms unlike their normal
2951 if (code == ASM_OPERANDS)
2955 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2956 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
2957 DF_REF_REG_USE, bb, insn, flags);
2969 /* Catch the def of the register being modified. */
2970 df_ref_record (collection_rec, XEXP (x, 0), &XEXP (x, 0), bb, insn,
2972 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
2974 /* ... Fall through to handle uses ... */
2980 /* Recursively scan the operands of this expression. */
2982 const char *fmt = GET_RTX_FORMAT (code);
2985 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2989 /* Tail recursive case: save a function call level. */
2995 df_uses_record (collection_rec, &XEXP (x, i), ref_type, bb, insn, flags);
2997 else if (fmt[i] == 'E')
3000 for (j = 0; j < XVECLEN (x, i); j++)
3001 df_uses_record (collection_rec,
3002 &XVECEXP (x, i, j), ref_type, bb, insn, flags);
3011 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3014 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3017 for (i = 0; i < collection_rec->next_def; i++)
3019 struct df_ref *ref = collection_rec->def_vec[i];
3020 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3023 = df_ref_create_structure (collection_rec, DF_REF_REG (ref),
3024 DF_REF_LOC (ref), DF_REF_BB (ref),
3025 DF_REF_INSN (ref), DF_REF_REG_USE,
3026 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3027 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3033 /* Get call's extra defs and uses. */
3036 df_get_call_refs (struct df_collection_rec * collection_rec,
3039 enum df_ref_flags flags)
3044 bool is_sibling_call;
3046 bitmap defs_generated = BITMAP_ALLOC (&df_bitmap_obstack);
3048 /* Do not generate clobbers for registers that are the result of the
3049 call. This causes ordering problems in the chain building code
3050 depending on which def is seen first. */
3051 for (i=0; i<collection_rec->next_def; i++)
3053 struct df_ref *def = collection_rec->def_vec[i];
3054 bitmap_set_bit (defs_generated, DF_REF_REGNO (def));
3057 /* Record the registers used to pass arguments, and explicitly
3058 noted as clobbered. */
3059 for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
3060 note = XEXP (note, 1))
3062 if (GET_CODE (XEXP (note, 0)) == USE)
3063 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3064 DF_REF_REG_USE, bb, insn, flags);
3065 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3067 if (REG_P (XEXP (XEXP (note, 0), 0)))
3069 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3070 if (!bitmap_bit_p (defs_generated, regno))
3071 df_defs_record (collection_rec, XEXP (note, 0), bb,
3075 df_uses_record (collection_rec, &XEXP (note, 0),
3076 DF_REF_REG_USE, bb, insn, flags);
3080 /* The stack ptr is used (honorarily) by a CALL insn. */
3081 df_ref_record (collection_rec, regno_reg_rtx[STACK_POINTER_REGNUM],
3082 NULL, bb, insn, DF_REF_REG_USE, DF_REF_CALL_STACK_USAGE | flags);
3084 /* Calls may also reference any of the global registers,
3085 so they are recorded as used. */
3086 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3088 df_ref_record (collection_rec, regno_reg_rtx[i],
3089 NULL, bb, insn, DF_REF_REG_USE, flags);
3091 is_sibling_call = SIBLING_CALL_P (insn);
3092 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, ui, bi)
3094 if ((!bitmap_bit_p (defs_generated, ui))
3095 && (!is_sibling_call
3096 || !bitmap_bit_p (df->exit_block_uses, ui)
3097 || refers_to_regno_p (ui, ui+1,
3098 current_function_return_rtx, NULL)))
3100 df_ref_record (collection_rec, regno_reg_rtx[ui],
3101 NULL, bb, insn, DF_REF_REG_DEF, DF_REF_MAY_CLOBBER | flags);
3104 BITMAP_FREE (defs_generated);
3108 /* Collect all refs in the INSN. This function is free of any
3109 side-effect - it will create and return a lists of df_ref's in the
3110 COLLECTION_REC without putting those refs into existing ref chains
3114 df_insn_refs_collect (struct df_collection_rec* collection_rec,
3115 basic_block bb, rtx insn)
3118 bool is_cond_exec = (GET_CODE (PATTERN (insn)) == COND_EXEC);
3120 /* Clear out the collection record. */
3121 collection_rec->next_def = 0;
3122 collection_rec->next_use = 0;
3123 collection_rec->next_eq_use = 0;
3124 collection_rec->next_mw = 0;
3126 /* Record register defs. */
3127 df_defs_record (collection_rec, PATTERN (insn), bb, insn, 0);
3129 /* Process REG_EQUIV/REG_EQUAL notes */
3130 for (note = REG_NOTES (insn); note;
3131 note = XEXP (note, 1))
3133 switch (REG_NOTE_KIND (note))
3137 df_uses_record (collection_rec,
3138 &XEXP (note, 0), DF_REF_REG_USE,
3139 bb, insn, DF_REF_IN_NOTE);
3141 case REG_NON_LOCAL_GOTO:
3142 /* The frame ptr is used by a non-local goto. */
3143 df_ref_record (collection_rec,
3144 regno_reg_rtx[FRAME_POINTER_REGNUM],
3148 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3149 df_ref_record (collection_rec,
3150 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3162 df_get_call_refs (collection_rec, bb, insn,
3163 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3165 /* Record the register uses. */
3166 df_uses_record (collection_rec,
3167 &PATTERN (insn), DF_REF_REG_USE, bb, insn, 0);
3169 /* DF_REF_CONDITIONAL needs corresponding USES. */
3171 df_get_conditional_uses (collection_rec);
3173 df_canonize_collection_rec (collection_rec);
3176 /* Return true if any pred of BB is an eh. */
3179 df_has_eh_preds (basic_block bb)
3184 FOR_EACH_EDGE (e, ei, bb->preds)
3186 if (e->flags & EDGE_EH)
3193 /* Recompute the luids for the insns in BB. */
3196 df_recompute_luids (basic_block bb)
3201 df_grow_insn_info ();
3203 /* Scan the block an insn at a time from beginning to end. */
3204 FOR_BB_INSNS (bb, insn)
3206 struct df_insn_info *insn_info = DF_INSN_GET (insn);
3207 /* Inserting labels does not always trigger the incremental
3211 gcc_assert (!INSN_P (insn));
3212 df_insn_create_insn_record (insn);
3215 DF_INSN_LUID (insn) = luid;
3222 /* Returns true if the function entry needs to
3223 define the static chain register. */
3226 df_need_static_chain_reg (struct function *fun)
3228 tree fun_context = decl_function_context (fun->decl);
3230 && DECL_NO_STATIC_CHAIN (fun_context) == false;
3234 /* Collect all artificial refs at the block level for BB and add them
3235 to COLLECTION_REC. */
3238 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3240 collection_rec->next_def = 0;
3241 collection_rec->next_use = 0;
3242 collection_rec->next_eq_use = 0;
3243 collection_rec->next_mw = 0;
3245 if (bb->index == ENTRY_BLOCK)
3247 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3250 else if (bb->index == EXIT_BLOCK)
3252 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3256 #ifdef EH_RETURN_DATA_REGNO
3257 if (df_has_eh_preds (bb))
3260 /* Mark the registers that will contain data for the handler. */
3263 unsigned regno = EH_RETURN_DATA_REGNO (i);
3264 if (regno == INVALID_REGNUM)
3266 df_ref_record (collection_rec, regno_reg_rtx[regno], NULL,
3267 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3274 if (df_has_eh_preds (bb))
3277 /* This code is putting in an artificial ref for the use at the
3278 TOP of the block that receives the exception. It is too
3279 cumbersome to actually put the ref on the edge. We could
3280 either model this at the top of the receiver block or the
3281 bottom of the sender block.
3283 The bottom of the sender block is problematic because not all
3284 out-edges of the a block are eh-edges. However, it is true
3285 that all edges into a block are either eh-edges or none of
3286 them are eh-edges. Thus, we can model this at the top of the
3287 eh-receiver for all of the edges at once. */
3288 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3290 df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3291 bb, NULL, DF_REF_REG_USE, DF_REF_AT_TOP);
3295 /* Add the hard_frame_pointer if this block is the target of a
3297 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3298 df_ref_record (collection_rec, hard_frame_pointer_rtx, NULL,
3299 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3301 /* Add the artificial uses. */
3302 if (bb->index >= NUM_FIXED_BLOCKS)
3306 bitmap au = df_has_eh_preds (bb)
3307 ? df->eh_block_artificial_uses
3308 : df->regular_block_artificial_uses;
3310 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3312 df_ref_record (collection_rec, regno_reg_rtx[regno], NULL,
3313 bb, NULL, DF_REF_REG_USE, 0);
3317 df_canonize_collection_rec (collection_rec);
3321 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3324 df_bb_refs_record (int bb_index, bool scan_insns)
3326 basic_block bb = BASIC_BLOCK (bb_index);
3329 struct df_scan_bb_info *bb_info;
3330 struct df_collection_rec collection_rec;
3331 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
3332 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
3333 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
3334 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
3339 bb_info = df_scan_get_bb_info (bb_index);
3341 /* Need to make sure that there is a record in the basic block info. */
3344 bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
3345 df_scan_set_bb_info (bb_index, bb_info);
3346 bb_info->artificial_defs = NULL;
3347 bb_info->artificial_uses = NULL;
3351 /* Scan the block an insn at a time from beginning to end. */
3352 FOR_BB_INSNS (bb, insn)
3354 struct df_insn_info *insn_info = DF_INSN_GET (insn);
3355 gcc_assert (!insn_info);
3357 df_insn_create_insn_record (insn);
3360 /* Record refs within INSN. */
3361 DF_INSN_LUID (insn) = luid++;
3362 df_insn_refs_collect (&collection_rec, bb, insn);
3363 df_refs_add_to_chains (&collection_rec, bb, insn);
3365 DF_INSN_LUID (insn) = luid;
3368 /* Other block level artificial refs */
3369 df_bb_refs_collect (&collection_rec, bb);
3370 df_refs_add_to_chains (&collection_rec, bb, NULL);
3372 /* Now that the block has been processed, set the block as dirty so
3373 lr and ur will get it processed. */
3374 df_set_bb_dirty (bb);
3378 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3382 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3384 bitmap_clear (regular_block_artificial_uses);
3386 if (reload_completed)
3388 if (frame_pointer_needed)
3389 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3392 /* Before reload, there are a few registers that must be forced
3393 live everywhere -- which might not already be the case for
3394 blocks within infinite loops. */
3396 /* Any reference to any pseudo before reload is a potential
3397 reference of the frame pointer. */
3398 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3400 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3401 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3404 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3405 /* Pseudos with argument area equivalences may require
3406 reloading via the argument pointer. */
3407 if (fixed_regs[ARG_POINTER_REGNUM])
3408 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3411 /* Any constant, or pseudo with constant equivalences, may
3412 require reloading from memory using the pic register. */
3413 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3414 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3415 bitmap_set_bit (regular_block_artificial_uses, PIC_OFFSET_TABLE_REGNUM);
3417 /* The all-important stack pointer must always be live. */
3418 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3422 /* Get the artificial use set for an eh block. */
3425 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3427 bitmap_clear (eh_block_artificial_uses);
3429 /* The following code (down thru the arg_pointer seting APPEARS
3430 to be necessary because there is nothing that actually
3431 describes what the exception handling code may actually need
3433 if (reload_completed)
3435 if (frame_pointer_needed)
3437 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3438 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3439 bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3442 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3443 if (fixed_regs[ARG_POINTER_REGNUM])
3444 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3451 /*----------------------------------------------------------------------------
3452 Specialized hard register scanning functions.
3453 ----------------------------------------------------------------------------*/
3456 /* Mark a register in SET. Hard registers in large modes get all
3457 of their component registers set as well. */
3460 df_mark_reg (rtx reg, void *vset)
3462 bitmap set = (bitmap) vset;
3463 int regno = REGNO (reg);
3465 gcc_assert (GET_MODE (reg) != BLKmode);
3467 bitmap_set_bit (set, regno);
3468 if (regno < FIRST_PSEUDO_REGISTER)
3470 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3472 bitmap_set_bit (set, regno + n);
3479 /* Set the bit for regs that are considered being defined at the entry. */
3482 df_get_entry_block_def_set (bitmap entry_block_defs)
3487 bitmap_clear (entry_block_defs);
3489 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3491 if (FUNCTION_ARG_REGNO_P (i))
3492 #ifdef INCOMING_REGNO
3493 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3495 bitmap_set_bit (entry_block_defs, i);
3499 /* Once the prologue has been generated, all of these registers
3500 should just show up in the first regular block. */
3501 if (HAVE_prologue && epilogue_completed)
3503 /* Defs for the callee saved registers are inserted so that the
3504 pushes have some defining location. */
3505 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3506 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3507 bitmap_set_bit (entry_block_defs, i);
3511 /* The always important stack pointer. */
3512 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3514 /* If STATIC_CHAIN_INCOMING_REGNUM == STATIC_CHAIN_REGNUM
3515 only STATIC_CHAIN_REGNUM is defined. If they are different,
3516 we only care about the STATIC_CHAIN_INCOMING_REGNUM. */
3517 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3518 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3520 #ifdef STATIC_CHAIN_REGNUM
3521 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3525 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3527 bitmap_set_bit (entry_block_defs, REGNO (r));
3530 if ((!reload_completed) || frame_pointer_needed)
3532 /* Any reference to any pseudo before reload is a potential
3533 reference of the frame pointer. */
3534 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3535 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3536 /* If they are different, also mark the hard frame pointer as live. */
3537 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3538 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3542 /* These registers are live everywhere. */
3543 if (!reload_completed)
3546 /* The ia-64, the only machine that uses this, does not define these
3547 until after reload. */
3548 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3551 bitmap_set_bit (entry_block_defs, i);
3555 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3556 /* Pseudos with argument area equivalences may require
3557 reloading via the argument pointer. */
3558 if (fixed_regs[ARG_POINTER_REGNUM])
3559 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3562 #ifdef PIC_OFFSET_TABLE_REGNUM
3563 /* Any constant, or pseudo with constant equivalences, may
3564 require reloading from memory using the pic register. */
3565 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3566 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3567 bitmap_set_bit (entry_block_defs, PIC_OFFSET_TABLE_REGNUM);
3571 #ifdef INCOMING_RETURN_ADDR_RTX
3572 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3573 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3576 targetm.live_on_entry (entry_block_defs);
3578 /* If the function has an incoming STATIC_CHAIN,
3579 it has to show up in the entry def set. */
3580 if (df_need_static_chain_reg (cfun))
3582 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3583 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3585 #ifdef STATIC_CHAIN_REGNUM
3586 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3593 /* Return the (conservative) set of hard registers that are defined on
3594 entry to the function.
3595 It uses df->entry_block_defs to determine which register
3596 reference to include. */
3599 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3600 bitmap entry_block_defs)
3605 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3607 df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3608 ENTRY_BLOCK_PTR, NULL, DF_REF_REG_DEF, 0);
3611 df_canonize_collection_rec (collection_rec);
3615 /* Record the (conservative) set of hard registers that are defined on
3616 entry to the function. */
3619 df_record_entry_block_defs (bitmap entry_block_defs)
3621 struct df_collection_rec collection_rec;
3622 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3623 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * FIRST_PSEUDO_REGISTER);
3625 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3627 /* Process bb_refs chain */
3628 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (ENTRY_BLOCK), NULL);
3632 /* Update the defs in the entry bolck. */
3635 df_update_entry_block_defs (void)
3637 bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3638 bool changed = false;
3640 df_get_entry_block_def_set (refs);
3641 if (df->entry_block_defs)
3643 if (!bitmap_equal_p (df->entry_block_defs, refs))
3645 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3646 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3647 df_ref_chain_delete (bb_info->artificial_defs);
3648 bb_info->artificial_defs = NULL;
3654 struct df_scan_problem_data *problem_data
3655 = (struct df_scan_problem_data *) df_scan->problem_data;
3656 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3662 df_record_entry_block_defs (refs);
3663 bitmap_copy (df->entry_block_defs, refs);
3664 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
3670 /* Set the bit for regs that are considered being used at the exit. */
3673 df_get_exit_block_use_set (bitmap exit_block_uses)
3677 bitmap_clear (exit_block_uses);
3679 /* Stack pointer is always live at the exit. */
3680 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3682 /* Mark the frame pointer if needed at the end of the function.
3683 If we end up eliminating it, it will be removed from the live
3684 list of each basic block by reload. */
3686 if ((!reload_completed) || frame_pointer_needed)
3688 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3689 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3690 /* If they are different, also mark the hard frame pointer as live. */
3691 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3692 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3696 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3697 /* Many architectures have a GP register even without flag_pic.
3698 Assume the pic register is not in use, or will be handled by
3699 other means, if it is not fixed. */
3700 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3701 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3702 bitmap_set_bit (exit_block_uses, PIC_OFFSET_TABLE_REGNUM);
3705 /* Mark all global registers, and all registers used by the
3706 epilogue as being live at the end of the function since they
3707 may be referenced by our caller. */
3708 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3709 if (global_regs[i] || EPILOGUE_USES (i))
3710 bitmap_set_bit (exit_block_uses, i);
3712 if (HAVE_epilogue && epilogue_completed)
3714 /* Mark all call-saved registers that we actually used. */
3715 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3716 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3717 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3718 bitmap_set_bit (exit_block_uses, i);
3721 #ifdef EH_RETURN_DATA_REGNO
3722 /* Mark the registers that will contain data for the handler. */
3723 if (reload_completed && current_function_calls_eh_return)
3726 unsigned regno = EH_RETURN_DATA_REGNO (i);
3727 if (regno == INVALID_REGNUM)
3729 bitmap_set_bit (exit_block_uses, regno);
3733 #ifdef EH_RETURN_STACKADJ_RTX
3734 if ((!HAVE_epilogue || ! epilogue_completed)
3735 && current_function_calls_eh_return)
3737 rtx tmp = EH_RETURN_STACKADJ_RTX;
3738 if (tmp && REG_P (tmp))
3739 df_mark_reg (tmp, exit_block_uses);
3743 #ifdef EH_RETURN_HANDLER_RTX
3744 if ((!HAVE_epilogue || ! epilogue_completed)
3745 && current_function_calls_eh_return)
3747 rtx tmp = EH_RETURN_HANDLER_RTX;
3748 if (tmp && REG_P (tmp))
3749 df_mark_reg (tmp, exit_block_uses);
3753 /* Mark function return value. */
3754 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3758 /* Return the refs of hard registers that are used in the exit block.
3759 It uses df->exit_block_uses to determine register to include. */
3762 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3767 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3768 df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3769 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
3771 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3772 /* It is deliberate that this is not put in the exit block uses but
3773 I do not know why. */
3774 if (reload_completed
3775 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3776 && df_has_eh_preds (EXIT_BLOCK_PTR)
3777 && fixed_regs[ARG_POINTER_REGNUM])
3778 df_ref_record (collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3779 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
3782 df_canonize_collection_rec (collection_rec);
3786 /* Record the set of hard registers that are used in the exit block.
3787 It uses df->exit_block_uses to determine which bit to include. */
3790 df_record_exit_block_uses (bitmap exit_block_uses)
3792 struct df_collection_rec collection_rec;
3793 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3794 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * FIRST_PSEUDO_REGISTER);
3796 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3798 /* Process bb_refs chain */
3799 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (EXIT_BLOCK), NULL);
3803 /* Update the uses in the exit block. */
3806 df_update_exit_block_uses (void)
3808 bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3809 bool changed = false;
3811 df_get_exit_block_use_set (refs);
3812 if (df->exit_block_uses)
3814 if (!bitmap_equal_p (df->exit_block_uses, refs))
3816 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3817 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3818 df_ref_chain_delete (bb_info->artificial_uses);
3819 bb_info->artificial_uses = NULL;
3825 struct df_scan_problem_data *problem_data
3826 = (struct df_scan_problem_data *) df_scan->problem_data;
3827 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3833 df_record_exit_block_uses (refs);
3834 bitmap_copy (df->exit_block_uses, refs);
3835 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
3840 static bool initialized = false;
3843 /* Initialize some platform specific structures. */
3846 df_hard_reg_init (void)
3849 #ifdef ELIMINABLE_REGS
3850 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3855 bitmap_obstack_initialize (&persistent_obstack);
3857 /* Record which registers will be eliminated. We use this in
3859 CLEAR_HARD_REG_SET (elim_reg_set);
3861 #ifdef ELIMINABLE_REGS
3862 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3863 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3865 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3868 df_invalidated_by_call = BITMAP_ALLOC (&persistent_obstack);
3870 /* Inconveniently, this is only readily available in hard reg set
3872 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
3873 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3874 bitmap_set_bit (df_invalidated_by_call, i);
3880 /* Recompute the parts of scanning that are based on regs_ever_live
3881 because something changed in that array. */
3884 df_update_entry_exit_and_calls (void)
3888 df_update_entry_block_defs ();
3889 df_update_exit_block_uses ();
3891 /* The call insns need to be rescanned because there may be changes
3892 in the set of registers clobbered across the call. */
3896 FOR_BB_INSNS (bb, insn)
3898 if (INSN_P (insn) && CALL_P (insn))
3899 df_insn_rescan (insn);
3905 /* Return true if hard REG is actually used in the some instruction.
3906 There are a fair number of conditions that affect the setting of
3907 this array. See the comment in df.h for df->hard_regs_live_count
3908 for the conditions that this array is set. */
3911 df_hard_reg_used_p (unsigned int reg)
3914 return df->hard_regs_live_count[reg] != 0;
3918 /* A count of the number of times REG is actually used in the some
3919 instruction. There are a fair number of conditions that affect the
3920 setting of this array. See the comment in df.h for
3921 df->hard_regs_live_count for the conditions that this array is
3926 df_hard_reg_used_count (unsigned int reg)
3929 return df->hard_regs_live_count[reg];
3933 /* Get the value of regs_ever_live[REGNO]. */
3936 df_regs_ever_live_p (unsigned int regno)
3938 return regs_ever_live[regno];
3942 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3943 to change, schedule that change for the next update. */
3946 df_set_regs_ever_live (unsigned int regno, bool value)
3948 if (regs_ever_live[regno] == value)
3951 regs_ever_live[regno] = value;
3953 df->redo_entry_and_exit = true;
3957 /* Compute "regs_ever_live" information from the underlying df
3958 information. Set the vector to all false if RESET. */
3961 df_compute_regs_ever_live (bool reset)
3964 bool changed = df->redo_entry_and_exit;
3967 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3969 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3970 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3972 regs_ever_live[i] = true;
3976 df_update_entry_exit_and_calls ();
3977 df->redo_entry_and_exit = false;
3981 /*----------------------------------------------------------------------------
3982 Dataflow ref information verification functions.
3984 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3985 df_reg_chain_verify_unmarked (refs)
3986 df_refs_verify (ref*, ref*, bool)
3987 df_mws_verify (mw*, mw*, bool)
3988 df_insn_refs_verify (collection_rec, bb, insn, bool)
3989 df_bb_refs_verify (bb, refs, bool)
3991 df_exit_block_bitmap_verify (bool)
3992 df_entry_block_bitmap_verify (bool)
3994 ----------------------------------------------------------------------------*/
3997 /* Mark all refs in the reg chain. Verify that all of the registers
3998 are in the correct chain. */
4001 df_reg_chain_mark (struct df_ref *refs, unsigned int regno,
4002 bool is_def, bool is_eq_use)
4004 unsigned int count = 0;
4006 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4008 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4010 /* If there are no def-use or use-def chains, make sure that all
4011 of the chains are clear. */
4013 gcc_assert (!DF_REF_CHAIN (ref));
4015 /* Check to make sure the ref is in the correct chain. */
4016 gcc_assert (DF_REF_REGNO (ref) == regno);
4018 gcc_assert (DF_REF_TYPE(ref) == DF_REF_REG_DEF);
4020 gcc_assert (DF_REF_TYPE(ref) != DF_REF_REG_DEF);
4023 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4025 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4028 gcc_assert (ref->next_reg->prev_reg == ref);
4030 DF_REF_REG_MARK (ref);
4036 /* Verify that all of the registers in the chain are unmarked. */
4039 df_reg_chain_verify_unmarked (struct df_ref *refs)
4042 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4043 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4047 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4050 df_refs_verify (struct df_ref **new_rec, struct df_ref **old_rec,
4053 while ((*new_rec) && (*old_rec))
4055 if (!df_ref_equal_p (*new_rec, *old_rec))
4063 /* Abort if fail is called from the function level verifier. If
4064 that is the context, mark this reg as being seem. */
4067 gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
4068 DF_REF_REG_UNMARK (*old_rec);
4076 gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4078 return ((*new_rec == NULL) && (*old_rec == NULL));
4083 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4086 df_mws_verify (struct df_mw_hardreg **new_rec, struct df_mw_hardreg **old_rec,
4089 while ((*new_rec) && (*old_rec))
4091 if (!df_mw_equal_p (*new_rec, *old_rec))
4103 gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4105 return ((*new_rec == NULL) && (*old_rec == NULL));
4110 /* Return true if the existing insn refs information is complete and
4111 correct. Otherwise (i.e. if there's any missing or extra refs),
4112 return the correct df_ref chain in REFS_RETURN.
4114 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4115 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4116 verification mode instead of the whole function, so unmark
4119 If ABORT_IF_FAIL is set, this function never returns false. */
4122 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4127 bool ret1, ret2, ret3, ret4;
4128 unsigned int uid = INSN_UID (insn);
4130 df_insn_refs_collect (collection_rec, bb, insn);
4132 if (!DF_INSN_UID_DEFS (uid))
4134 /* The insn_rec was created but it was never filled out. */
4141 /* Unfortunately we cannot opt out early if one of these is not
4142 right because the marks will not get cleared. */
4143 ret1 = df_refs_verify (collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4145 ret2 = df_refs_verify (collection_rec->use_vec, DF_INSN_UID_USES (uid),
4147 ret3 = df_refs_verify (collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4149 ret4 = df_mws_verify (collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4151 return (ret1 && ret2 && ret3 && ret4);
4155 /* Return true if all refs in the basic block are correct and complete.
4156 Due to df_ref_chain_verify, it will cause all refs
4157 that are verified to have DF_REF_MARK bit set. */
4160 df_bb_verify (basic_block bb)
4163 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4164 struct df_collection_rec collection_rec;
4166 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4167 collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
4168 collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
4169 collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
4170 collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
4172 gcc_assert (bb_info);
4174 /* Scan the block an insn at a time from beginning to end. */
4175 FOR_BB_INSNS_REVERSE (bb, insn)
4179 df_insn_refs_verify (&collection_rec, bb, insn, true);
4180 df_free_collection_rec (&collection_rec);
4183 /* Do the artificial defs and uses. */
4184 df_bb_refs_collect (&collection_rec, bb);
4185 df_refs_verify (collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4186 df_refs_verify (collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4187 df_free_collection_rec (&collection_rec);
4193 /* Returns true if the entry block has correct and complete df_ref set.
4194 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4197 df_entry_block_bitmap_verify (bool abort_if_fail)
4199 bitmap entry_block_defs = BITMAP_ALLOC (&df_bitmap_obstack);
4202 df_get_entry_block_def_set (entry_block_defs);
4204 is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4206 if (!is_eq && abort_if_fail)
4208 print_current_pass (stderr);
4209 fprintf (stderr, "entry_block_defs = ");
4210 df_print_regset (stderr, entry_block_defs);
4211 fprintf (stderr, "df->entry_block_defs = ");
4212 df_print_regset (stderr, df->entry_block_defs);
4216 BITMAP_FREE (entry_block_defs);
4222 /* Returns true if the exit block has correct and complete df_ref set.
4223 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4226 df_exit_block_bitmap_verify (bool abort_if_fail)
4228 bitmap exit_block_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4231 df_get_exit_block_use_set (exit_block_uses);
4233 is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4235 if (!is_eq && abort_if_fail)
4237 print_current_pass (stderr);
4238 fprintf (stderr, "exit_block_uses = ");
4239 df_print_regset (stderr, exit_block_uses);
4240 fprintf (stderr, "df->exit_block_uses = ");
4241 df_print_regset (stderr, df->exit_block_uses);
4245 BITMAP_FREE (exit_block_uses);
4251 /* Return true if df_ref information for all insns in all BLOCKS are
4252 correct and complete. If BLOCKS is null, all blocks are
4256 df_scan_verify (void)
4260 bitmap regular_block_artificial_uses;
4261 bitmap eh_block_artificial_uses;
4266 /* This is a hack, but a necessary one. If you do not do this,
4267 insn_attrtab can never be compiled in a bootstrap. This
4268 verification is just too expensive. */
4269 if (n_basic_blocks > 250)
4272 /* Verification is a 4 step process. */
4274 /* (1) All of the refs are marked by going thru the reg chains. */
4275 for (i = 0; i < DF_REG_SIZE (df); i++)
4277 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4278 == DF_REG_DEF_COUNT(i));
4279 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4280 == DF_REG_USE_COUNT(i));
4281 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4282 == DF_REG_EQ_USE_COUNT(i));
4285 /* (2) There are various bitmaps whose value may change over the
4286 course of the compilation. This step recomputes them to make
4287 sure that they have not slipped out of date. */
4288 regular_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4289 eh_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4291 df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4292 df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4294 bitmap_ior_into (eh_block_artificial_uses,
4295 regular_block_artificial_uses);
4297 /* Check artificial_uses bitmaps didn't change. */
4298 gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4299 df->regular_block_artificial_uses));
4300 gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4301 df->eh_block_artificial_uses));
4303 BITMAP_FREE (regular_block_artificial_uses);
4304 BITMAP_FREE (eh_block_artificial_uses);
4306 /* Verify entry block and exit block. These only verify the bitmaps,
4307 the refs are verified in df_bb_verify. */
4308 df_entry_block_bitmap_verify (true);
4309 df_exit_block_bitmap_verify (true);
4311 /* (3) All of the insns in all of the blocks are traversed and the
4312 marks are cleared both in the artificial refs attached to the
4313 blocks and the real refs inside the insns. It is a failure to
4314 clear a mark that has not been set as this means that the ref in
4315 the block or insn was not in the reg chain. */
4320 /* (4) See if all reg chains are traversed a second time. This time
4321 a check is made that the marks are clear. A set mark would be a
4322 from a reg that is not in any insn or basic block. */
4324 for (i = 0; i < DF_REG_SIZE (df); i++)
4326 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4327 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4328 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));