1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999-2013 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
30 #include "insn-config.h"
34 #include "alloc-pool.h"
36 #include "hard-reg-set.h"
37 #include "basic-block.h"
43 #include "target-def.h"
45 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
48 typedef struct df_mw_hardreg *df_mw_hardreg_ptr;
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 following two macros free the vecs that hold either the refs or
66 the mw refs. They are a little tricky because the vec has 0
67 elements is special and is not to be freed. */
68 #define df_scan_free_ref_vec(V) \
74 #define df_scan_free_mws_vec(V) \
80 /* The set of hard registers in eliminables[i].from. */
82 static HARD_REG_SET elim_reg_set;
84 /* Initialize ur_in and ur_out as if all hard registers were partially
87 struct df_collection_rec
89 vec<df_ref, va_stack> def_vec;
90 vec<df_ref, va_stack> use_vec;
91 vec<df_ref, va_stack> eq_use_vec;
92 vec<df_mw_hardreg_ptr, va_stack> mw_vec;
95 static df_ref df_null_ref_rec[1];
96 static struct df_mw_hardreg * df_null_mw_rec[1];
98 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
100 basic_block, struct df_insn_info *,
101 enum df_ref_type, int ref_flags);
102 static void df_def_record_1 (struct df_collection_rec *, rtx *,
103 basic_block, struct df_insn_info *,
105 static void df_defs_record (struct df_collection_rec *, rtx,
106 basic_block, struct df_insn_info *,
108 static void df_uses_record (struct df_collection_rec *,
109 rtx *, enum df_ref_type,
110 basic_block, struct df_insn_info *,
113 static void df_install_ref_incremental (df_ref);
114 static df_ref df_ref_create_structure (enum df_ref_class,
115 struct df_collection_rec *, rtx, rtx *,
116 basic_block, struct df_insn_info *,
117 enum df_ref_type, int ref_flags);
118 static void df_insn_refs_collect (struct df_collection_rec*,
119 basic_block, struct df_insn_info *);
120 static void df_canonize_collection_rec (struct df_collection_rec *);
122 static void df_get_regular_block_artificial_uses (bitmap);
123 static void df_get_eh_block_artificial_uses (bitmap);
125 static void df_record_entry_block_defs (bitmap);
126 static void df_record_exit_block_uses (bitmap);
127 static void df_get_exit_block_use_set (bitmap);
128 static void df_get_entry_block_def_set (bitmap);
129 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
130 static void df_ref_chain_delete_du_chain (df_ref *);
131 static void df_ref_chain_delete (df_ref *);
133 static void df_refs_add_to_chains (struct df_collection_rec *,
136 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block, rtx, bool);
137 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
138 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
139 static void df_install_ref (df_ref, struct df_reg_info *,
140 struct df_ref_info *, bool);
142 static int df_ref_compare (const void *, const void *);
143 static int df_mw_compare (const void *, const void *);
145 /* Indexed by hardware reg number, is true if that register is ever
146 used in the current function.
148 In df-scan.c, this is set up to record the hard regs used
149 explicitly. Reload adds in the hard regs used for holding pseudo
150 regs. Final uses it to generate the code in the function prologue
151 and epilogue to save and restore registers as needed. */
153 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
155 /*----------------------------------------------------------------------------
156 SCANNING DATAFLOW PROBLEM
158 There are several ways in which scanning looks just like the other
159 dataflow problems. It shares the all the mechanisms for local info
160 as well as basic block info. Where it differs is when and how often
161 it gets run. It also has no need for the iterative solver.
162 ----------------------------------------------------------------------------*/
164 /* Problem data for the scanning dataflow function. */
165 struct df_scan_problem_data
167 alloc_pool ref_base_pool;
168 alloc_pool ref_artificial_pool;
169 alloc_pool ref_regular_pool;
170 alloc_pool insn_pool;
172 alloc_pool mw_reg_pool;
173 bitmap_obstack reg_bitmaps;
174 bitmap_obstack insn_bitmaps;
177 typedef struct df_scan_bb_info *df_scan_bb_info_t;
180 /* Internal function to shut down the scanning problem. */
182 df_scan_free_internal (void)
184 struct df_scan_problem_data *problem_data
185 = (struct df_scan_problem_data *) df_scan->problem_data;
189 /* The vectors that hold the refs are not pool allocated because
190 they come in many sizes. This makes them impossible to delete
192 for (i = 0; i < DF_INSN_SIZE(); i++)
194 struct df_insn_info *insn_info = DF_INSN_UID_GET(i);
195 /* Skip the insns that have no insn_info or have been
199 df_scan_free_ref_vec (insn_info->defs);
200 df_scan_free_ref_vec (insn_info->uses);
201 df_scan_free_ref_vec (insn_info->eq_uses);
202 df_scan_free_mws_vec (insn_info->mw_hardregs);
208 unsigned int bb_index = bb->index;
209 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
212 df_scan_free_ref_vec (bb_info->artificial_defs);
213 df_scan_free_ref_vec (bb_info->artificial_uses);
217 free (df->def_info.refs);
218 free (df->def_info.begin);
219 free (df->def_info.count);
220 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
222 free (df->use_info.refs);
223 free (df->use_info.begin);
224 free (df->use_info.count);
225 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
231 free (df->eq_use_regs);
232 df->eq_use_regs = NULL;
240 free (df_scan->block_info);
241 df_scan->block_info = NULL;
242 df_scan->block_info_size = 0;
244 bitmap_clear (&df->hardware_regs_used);
245 bitmap_clear (&df->regular_block_artificial_uses);
246 bitmap_clear (&df->eh_block_artificial_uses);
247 BITMAP_FREE (df->entry_block_defs);
248 BITMAP_FREE (df->exit_block_uses);
249 bitmap_clear (&df->insns_to_delete);
250 bitmap_clear (&df->insns_to_rescan);
251 bitmap_clear (&df->insns_to_notes_rescan);
253 free_alloc_pool (problem_data->ref_base_pool);
254 free_alloc_pool (problem_data->ref_artificial_pool);
255 free_alloc_pool (problem_data->ref_regular_pool);
256 free_alloc_pool (problem_data->insn_pool);
257 free_alloc_pool (problem_data->reg_pool);
258 free_alloc_pool (problem_data->mw_reg_pool);
259 bitmap_obstack_release (&problem_data->reg_bitmaps);
260 bitmap_obstack_release (&problem_data->insn_bitmaps);
261 free (df_scan->problem_data);
265 /* Free basic block info. */
268 df_scan_free_bb_info (basic_block bb, void *vbb_info)
270 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
271 unsigned int bb_index = bb->index;
273 /* See if bb_info is initialized. */
274 if (bb_info->artificial_defs)
277 FOR_BB_INSNS (bb, insn)
280 /* Record defs within INSN. */
281 df_insn_delete (bb, INSN_UID (insn));
284 if (bb_index < df_scan->block_info_size)
285 bb_info = df_scan_get_bb_info (bb_index);
287 /* Get rid of any artificial uses or defs. */
288 if (bb_info->artificial_defs)
290 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
291 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
292 df_ref_chain_delete (bb_info->artificial_defs);
293 df_ref_chain_delete (bb_info->artificial_uses);
294 bb_info->artificial_defs = NULL;
295 bb_info->artificial_uses = NULL;
301 /* Allocate the problem data for the scanning problem. This should be
302 called when the problem is created or when the entire function is to
305 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
307 struct df_scan_problem_data *problem_data;
308 unsigned int insn_num = get_max_uid () + 1;
309 unsigned int block_size = 512;
312 /* Given the number of pools, this is really faster than tearing
314 if (df_scan->problem_data)
315 df_scan_free_internal ();
317 problem_data = XNEW (struct df_scan_problem_data);
318 df_scan->problem_data = problem_data;
319 df_scan->computed = true;
321 problem_data->ref_base_pool
322 = create_alloc_pool ("df_scan ref base",
323 sizeof (struct df_base_ref), block_size);
324 problem_data->ref_artificial_pool
325 = create_alloc_pool ("df_scan ref artificial",
326 sizeof (struct df_artificial_ref), block_size);
327 problem_data->ref_regular_pool
328 = create_alloc_pool ("df_scan ref regular",
329 sizeof (struct df_regular_ref), block_size);
330 problem_data->insn_pool
331 = create_alloc_pool ("df_scan insn",
332 sizeof (struct df_insn_info), block_size);
333 problem_data->reg_pool
334 = create_alloc_pool ("df_scan reg",
335 sizeof (struct df_reg_info), block_size);
336 problem_data->mw_reg_pool
337 = create_alloc_pool ("df_scan mw_reg",
338 sizeof (struct df_mw_hardreg), block_size / 16);
340 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
341 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
343 insn_num += insn_num / 4;
346 df_grow_insn_info ();
347 df_grow_bb_info (df_scan);
351 unsigned int bb_index = bb->index;
352 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
353 bb_info->artificial_defs = NULL;
354 bb_info->artificial_uses = NULL;
357 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
358 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
359 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
360 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
361 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
362 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
363 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
364 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
365 df_scan->optional_p = false;
369 /* Free all of the data associated with the scan problem. */
374 if (df_scan->problem_data)
375 df_scan_free_internal ();
377 if (df->blocks_to_analyze)
379 BITMAP_FREE (df->blocks_to_analyze);
380 df->blocks_to_analyze = NULL;
386 /* Dump the preamble for DF_SCAN dump. */
388 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
399 fprintf (file, ";; invalidated by call \t");
400 df_print_regset (file, regs_invalidated_by_call_regset);
401 fprintf (file, ";; hardware regs used \t");
402 df_print_regset (file, &df->hardware_regs_used);
403 fprintf (file, ";; regular block artificial uses \t");
404 df_print_regset (file, &df->regular_block_artificial_uses);
405 fprintf (file, ";; eh block artificial uses \t");
406 df_print_regset (file, &df->eh_block_artificial_uses);
407 fprintf (file, ";; entry block defs \t");
408 df_print_regset (file, df->entry_block_defs);
409 fprintf (file, ";; exit block uses \t");
410 df_print_regset (file, df->exit_block_uses);
411 fprintf (file, ";; regs ever live \t");
412 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
413 if (df_regs_ever_live_p (i))
414 fprintf (file, " %d[%s]", i, reg_names[i]);
415 fprintf (file, "\n;; ref usage \t");
417 for (i = 0; i < (int)df->regs_inited; i++)
418 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
420 const char * sep = "";
422 fprintf (file, "r%d={", i);
423 if (DF_REG_DEF_COUNT (i))
425 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
427 dcount += DF_REG_DEF_COUNT (i);
429 if (DF_REG_USE_COUNT (i))
431 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
433 ucount += DF_REG_USE_COUNT (i);
435 if (DF_REG_EQ_USE_COUNT (i))
437 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
438 ecount += DF_REG_EQ_USE_COUNT (i);
440 fprintf (file, "} ");
444 FOR_BB_INSNS (bb, insn)
453 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
454 " in %d{%d regular + %d call} insns.\n",
455 dcount + ucount + ecount, dcount, ucount, ecount,
456 icount + ccount, icount, ccount);
459 /* Dump the bb_info for a given basic block. */
461 df_scan_start_block (basic_block bb, FILE *file)
463 struct df_scan_bb_info *bb_info
464 = df_scan_get_bb_info (bb->index);
468 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
469 df_refs_chain_dump (bb_info->artificial_defs, true, file);
470 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
471 df_refs_chain_dump (bb_info->artificial_uses, true, file);
472 fprintf (file, "\n");
477 FOR_BB_INSNS (bb, insn)
479 df_insn_debug (insn, false, file);
484 static struct df_problem problem_SCAN =
486 DF_SCAN, /* Problem id. */
487 DF_NONE, /* Direction. */
488 df_scan_alloc, /* Allocate the problem specific data. */
489 NULL, /* Reset global information. */
490 df_scan_free_bb_info, /* Free basic block info. */
491 NULL, /* Local compute function. */
492 NULL, /* Init the solution specific data. */
493 NULL, /* Iterative solver. */
494 NULL, /* Confluence operator 0. */
495 NULL, /* Confluence operator n. */
496 NULL, /* Transfer function. */
497 NULL, /* Finalize function. */
498 df_scan_free, /* Free all of the problem information. */
499 NULL, /* Remove this problem from the stack of dataflow problems. */
500 df_scan_start_dump, /* Debugging. */
501 df_scan_start_block, /* Debugging start block. */
502 NULL, /* Debugging end block. */
503 NULL, /* Debugging start insn. */
504 NULL, /* Debugging end insn. */
505 NULL, /* Incremental solution verify start. */
506 NULL, /* Incremental solution verify end. */
507 NULL, /* Dependent problem. */
508 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
509 TV_DF_SCAN, /* Timing variable. */
510 false /* Reset blocks on dropping out of blocks_to_analyze. */
514 /* Create a new DATAFLOW instance and add it to an existing instance
515 of DF. The returned structure is what is used to get at the
519 df_scan_add_problem (void)
521 df_add_problem (&problem_SCAN);
525 /*----------------------------------------------------------------------------
526 Storage Allocation Utilities
527 ----------------------------------------------------------------------------*/
530 /* First, grow the reg_info information. If the current size is less than
531 the number of pseudos, grow to 25% more than the number of
534 Second, assure that all of the slots up to max_reg_num have been
535 filled with reg_info structures. */
538 df_grow_reg_info (void)
540 unsigned int max_reg = max_reg_num ();
541 unsigned int new_size = max_reg;
542 struct df_scan_problem_data *problem_data
543 = (struct df_scan_problem_data *) df_scan->problem_data;
546 if (df->regs_size < new_size)
548 new_size += new_size / 4;
549 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
550 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
551 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
553 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
554 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
555 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
556 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
557 df->regs_size = new_size;
560 for (i = df->regs_inited; i < max_reg; i++)
562 struct df_reg_info *reg_info;
564 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
565 memset (reg_info, 0, sizeof (struct df_reg_info));
566 df->def_regs[i] = reg_info;
567 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
568 memset (reg_info, 0, sizeof (struct df_reg_info));
569 df->use_regs[i] = reg_info;
570 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
571 memset (reg_info, 0, sizeof (struct df_reg_info));
572 df->eq_use_regs[i] = reg_info;
573 df->def_info.begin[i] = 0;
574 df->def_info.count[i] = 0;
575 df->use_info.begin[i] = 0;
576 df->use_info.count[i] = 0;
579 df->regs_inited = max_reg;
583 /* Grow the ref information. */
586 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
588 if (ref_info->refs_size < new_size)
590 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
591 memset (ref_info->refs + ref_info->refs_size, 0,
592 (new_size - ref_info->refs_size) *sizeof (df_ref));
593 ref_info->refs_size = new_size;
598 /* Check and grow the ref information if necessary. This routine
599 guarantees total_size + BITMAP_ADDEND amount of entries in refs
600 array. It updates ref_info->refs_size only and does not change
601 ref_info->total_size. */
604 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
605 unsigned bitmap_addend)
607 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
609 int new_size = ref_info->total_size + bitmap_addend;
610 new_size += ref_info->total_size / 4;
611 df_grow_ref_info (ref_info, new_size);
616 /* Grow the ref information. If the current size is less than the
617 number of instructions, grow to 25% more than the number of
621 df_grow_insn_info (void)
623 unsigned int new_size = get_max_uid () + 1;
624 if (DF_INSN_SIZE () < new_size)
626 new_size += new_size / 4;
627 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
628 memset (df->insns + df->insns_size, 0,
629 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
630 DF_INSN_SIZE () = new_size;
637 /*----------------------------------------------------------------------------
638 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
639 ----------------------------------------------------------------------------*/
641 /* Rescan all of the block_to_analyze or all of the blocks in the
642 function if df_set_blocks if blocks_to_analyze is NULL; */
645 df_scan_blocks (void)
649 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
650 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
652 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
653 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
655 bitmap_ior_into (&df->eh_block_artificial_uses,
656 &df->regular_block_artificial_uses);
658 /* ENTRY and EXIT blocks have special defs/uses. */
659 df_get_entry_block_def_set (df->entry_block_defs);
660 df_record_entry_block_defs (df->entry_block_defs);
661 df_get_exit_block_use_set (df->exit_block_uses);
662 df_record_exit_block_uses (df->exit_block_uses);
663 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
664 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
669 unsigned int bb_index = bb->index;
670 df_bb_refs_record (bb_index, true);
674 /* Create new refs under address LOC within INSN. This function is
675 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
676 depending on whether LOC is inside PATTERN (INSN) or a note. */
679 df_uses_create (rtx *loc, rtx insn, int ref_flags)
681 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
682 df_uses_record (NULL, loc, DF_REF_REG_USE,
683 BLOCK_FOR_INSN (insn),
684 DF_INSN_INFO_GET (insn),
688 /* Create a new ref of type DF_REF_TYPE for register REG at address
689 LOC within INSN of BB. This function is only used externally. */
692 df_ref_create (rtx reg, rtx *loc, rtx insn,
694 enum df_ref_type ref_type,
697 enum df_ref_class cl;
701 /* You cannot hack artificial refs. */
709 return df_ref_create_structure (cl, NULL, reg, loc, bb,
710 DF_INSN_INFO_GET (insn),
711 ref_type, ref_flags);
715 df_install_ref_incremental (df_ref ref)
717 struct df_reg_info **reg_info;
718 struct df_ref_info *ref_info;
720 df_ref **ref_rec_ptr;
721 unsigned int count = 0;
724 rtx insn = DF_REF_INSN (ref);
725 basic_block bb = BLOCK_FOR_INSN (insn);
727 if (DF_REF_REG_DEF_P (ref))
729 reg_info = df->def_regs;
730 ref_info = &df->def_info;
731 ref_rec_ptr = &DF_INSN_DEFS (insn);
732 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
734 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
736 reg_info = df->eq_use_regs;
737 ref_info = &df->use_info;
738 ref_rec_ptr = &DF_INSN_EQ_USES (insn);
739 switch (ref_info->ref_order)
741 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
742 case DF_REF_ORDER_BY_REG_WITH_NOTES:
743 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
747 add_to_table = false;
753 reg_info = df->use_regs;
754 ref_info = &df->use_info;
755 ref_rec_ptr = &DF_INSN_USES (insn);
756 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
759 /* Do not add if ref is not in the right blocks. */
760 if (add_to_table && df->analyze_subset)
761 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
763 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
766 switch (ref_info->ref_order)
768 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
769 case DF_REF_ORDER_BY_REG_WITH_NOTES:
770 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
771 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
774 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
778 ref_rec = *ref_rec_ptr;
785 ref_rec = *ref_rec_ptr;
788 ref_rec = XRESIZEVEC (df_ref, ref_rec, count+2);
789 *ref_rec_ptr = ref_rec;
790 ref_rec[count] = ref;
791 ref_rec[count+1] = NULL;
792 qsort (ref_rec, count + 1, sizeof (df_ref), df_ref_compare);
796 df_ref *ref_rec = XNEWVEC (df_ref, 2);
799 *ref_rec_ptr = ref_rec;
805 fprintf (dump_file, "adding ref ");
806 df_ref_debug (ref, dump_file);
809 /* By adding the ref directly, df_insn_rescan my not find any
810 differences even though the block will have changed. So we need
811 to mark the block dirty ourselves. */
812 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
813 df_set_bb_dirty (bb);
818 /*----------------------------------------------------------------------------
819 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
820 ----------------------------------------------------------------------------*/
823 df_free_ref (df_ref ref)
825 struct df_scan_problem_data *problem_data
826 = (struct df_scan_problem_data *) df_scan->problem_data;
828 switch (DF_REF_CLASS (ref))
831 pool_free (problem_data->ref_base_pool, ref);
834 case DF_REF_ARTIFICIAL:
835 pool_free (problem_data->ref_artificial_pool, ref);
839 pool_free (problem_data->ref_regular_pool, ref);
845 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
846 Also delete the def-use or use-def chain if it exists. */
849 df_reg_chain_unlink (df_ref ref)
851 df_ref next = DF_REF_NEXT_REG (ref);
852 df_ref prev = DF_REF_PREV_REG (ref);
853 int id = DF_REF_ID (ref);
854 struct df_reg_info *reg_info;
857 if (DF_REF_REG_DEF_P (ref))
859 int regno = DF_REF_REGNO (ref);
860 reg_info = DF_REG_DEF_GET (regno);
861 refs = df->def_info.refs;
865 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
867 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
868 switch (df->use_info.ref_order)
870 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
871 case DF_REF_ORDER_BY_REG_WITH_NOTES:
872 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
873 refs = df->use_info.refs;
881 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
882 refs = df->use_info.refs;
888 if (df->analyze_subset)
890 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
897 /* Delete any def-use or use-def chains that start here. It is
898 possible that there is trash in this field. This happens for
899 insns that have been deleted when rescanning has been deferred
900 and the chain problem has also been deleted. The chain tear down
901 code skips deleted insns. */
902 if (df_chain && DF_REF_CHAIN (ref))
903 df_chain_unlink (ref);
906 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
908 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
909 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
912 /* Unlink from the reg chain. If there is no prev, this is the
913 first of the list. If not, just join the next and prev. */
915 DF_REF_NEXT_REG (prev) = next;
918 gcc_assert (reg_info->reg_chain == ref);
919 reg_info->reg_chain = next;
922 DF_REF_PREV_REG (next) = prev;
928 /* Remove REF from VEC. */
931 df_ref_compress_rec (df_ref **vec_ptr, df_ref ref)
933 df_ref *vec = *vec_ptr;
937 while (*vec && *vec != ref)
949 *vec_ptr = df_null_ref_rec;
954 /* Unlink REF from all def-use/use-def chains, etc. */
957 df_ref_remove (df_ref ref)
962 fprintf (dump_file, "removing ref ");
963 df_ref_debug (ref, dump_file);
967 if (DF_REF_REG_DEF_P (ref))
969 if (DF_REF_IS_ARTIFICIAL (ref))
971 struct df_scan_bb_info *bb_info
972 = df_scan_get_bb_info (DF_REF_BBNO (ref));
973 df_ref_compress_rec (&bb_info->artificial_defs, ref);
977 unsigned int uid = DF_REF_INSN_UID (ref);
978 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
979 df_ref_compress_rec (&insn_rec->defs, ref);
984 if (DF_REF_IS_ARTIFICIAL (ref))
986 struct df_scan_bb_info *bb_info
987 = df_scan_get_bb_info (DF_REF_BBNO (ref));
988 df_ref_compress_rec (&bb_info->artificial_uses, ref);
992 unsigned int uid = DF_REF_INSN_UID (ref);
993 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
995 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
996 df_ref_compress_rec (&insn_rec->eq_uses, ref);
998 df_ref_compress_rec (&insn_rec->uses, ref);
1002 /* By deleting the ref directly, df_insn_rescan my not find any
1003 differences even though the block will have changed. So we need
1004 to mark the block dirty ourselves. */
1005 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
1006 df_set_bb_dirty (DF_REF_BB (ref));
1007 df_reg_chain_unlink (ref);
1011 /* Create the insn record for INSN. If there was one there, zero it
1014 struct df_insn_info *
1015 df_insn_create_insn_record (rtx insn)
1017 struct df_scan_problem_data *problem_data
1018 = (struct df_scan_problem_data *) df_scan->problem_data;
1019 struct df_insn_info *insn_rec;
1021 df_grow_insn_info ();
1022 insn_rec = DF_INSN_INFO_GET (insn);
1025 insn_rec = (struct df_insn_info *) pool_alloc (problem_data->insn_pool);
1026 DF_INSN_INFO_SET (insn, insn_rec);
1028 memset (insn_rec, 0, sizeof (struct df_insn_info));
1029 insn_rec->insn = insn;
1034 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
1037 df_ref_chain_delete_du_chain (df_ref *ref_rec)
1041 df_ref ref = *ref_rec;
1042 /* CHAIN is allocated by DF_CHAIN. So make sure to
1043 pass df_scan instance for the problem. */
1044 if (DF_REF_CHAIN (ref))
1045 df_chain_unlink (ref);
1051 /* Delete all refs in the ref chain. */
1054 df_ref_chain_delete (df_ref *ref_rec)
1056 df_ref *start = ref_rec;
1059 df_reg_chain_unlink (*ref_rec);
1063 /* If the list is empty, it has a special shared element that is not
1070 /* Delete the hardreg chain. */
1073 df_mw_hardreg_chain_delete (struct df_mw_hardreg **hardregs)
1075 struct df_scan_problem_data *problem_data;
1080 problem_data = (struct df_scan_problem_data *) df_scan->problem_data;
1084 pool_free (problem_data->mw_reg_pool, *hardregs);
1090 /* Delete all of the refs information from INSN. BB must be passed in
1091 except when called from df_process_deferred_rescans to mark the block
1095 df_insn_delete (basic_block bb, unsigned int uid)
1097 struct df_insn_info *insn_info = NULL;
1101 df_grow_bb_info (df_scan);
1102 df_grow_reg_info ();
1104 /* The block must be marked as dirty now, rather than later as in
1105 df_insn_rescan and df_notes_rescan because it may not be there at
1106 rescanning time and the mark would blow up. */
1108 df_set_bb_dirty (bb);
1110 insn_info = DF_INSN_UID_SAFE_GET (uid);
1112 /* The client has deferred rescanning. */
1113 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1117 bitmap_clear_bit (&df->insns_to_rescan, uid);
1118 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1119 bitmap_set_bit (&df->insns_to_delete, uid);
1122 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
1127 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
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 struct df_scan_problem_data *problem_data
1135 = (struct df_scan_problem_data *) df_scan->problem_data;
1137 /* In general, notes do not have the insn_info fields
1138 initialized. However, combine deletes insns by changing them
1139 to notes. How clever. So we cannot just check if it is a
1140 valid insn before short circuiting this code, we need to see
1141 if we actually initialized it. */
1142 if (insn_info->defs)
1144 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1148 df_ref_chain_delete_du_chain (insn_info->defs);
1149 df_ref_chain_delete_du_chain (insn_info->uses);
1150 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1153 df_ref_chain_delete (insn_info->defs);
1154 df_ref_chain_delete (insn_info->uses);
1155 df_ref_chain_delete (insn_info->eq_uses);
1156 df_scan_free_mws_vec (insn_info->mw_hardregs);
1158 pool_free (problem_data->insn_pool, insn_info);
1159 DF_INSN_UID_SET (uid, NULL);
1164 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
1167 df_free_collection_rec (struct df_collection_rec *collection_rec)
1170 struct df_scan_problem_data *problem_data
1171 = (struct df_scan_problem_data *) df_scan->problem_data;
1173 struct df_mw_hardreg *mw;
1175 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
1177 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
1179 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1181 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1182 pool_free (problem_data->mw_reg_pool, mw);
1184 collection_rec->def_vec.release ();
1185 collection_rec->use_vec.release ();
1186 collection_rec->eq_use_vec.release ();
1187 collection_rec->mw_vec.release ();
1190 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1193 df_insn_rescan (rtx insn)
1195 unsigned int uid = INSN_UID (insn);
1196 struct df_insn_info *insn_info = NULL;
1197 basic_block bb = BLOCK_FOR_INSN (insn);
1198 struct df_collection_rec collection_rec;
1200 if ((!df) || (!INSN_P (insn)))
1206 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1210 /* The client has disabled rescanning and plans to do it itself. */
1211 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1214 df_grow_bb_info (df_scan);
1215 df_grow_reg_info ();
1217 insn_info = DF_INSN_UID_SAFE_GET (uid);
1219 /* The client has deferred rescanning. */
1220 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1224 insn_info = df_insn_create_insn_record (insn);
1225 insn_info->defs = df_null_ref_rec;
1226 insn_info->uses = df_null_ref_rec;
1227 insn_info->eq_uses = df_null_ref_rec;
1228 insn_info->mw_hardregs = df_null_mw_rec;
1231 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1233 bitmap_clear_bit (&df->insns_to_delete, uid);
1234 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1235 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1239 vec_stack_alloc (df_ref, collection_rec.def_vec, 128);
1240 vec_stack_alloc (df_ref, collection_rec.use_vec, 32);
1241 vec_stack_alloc (df_ref, collection_rec.eq_use_vec, 32);
1242 vec_stack_alloc (df_mw_hardreg_ptr, collection_rec.mw_vec, 32);
1244 bitmap_clear_bit (&df->insns_to_delete, uid);
1245 bitmap_clear_bit (&df->insns_to_rescan, uid);
1246 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1250 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1251 /* If there's no change, return false. */
1254 df_free_collection_rec (&collection_rec);
1256 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1260 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1262 /* There's change - we need to delete the existing info.
1263 Since the insn isn't moved, we can salvage its LUID. */
1264 luid = DF_INSN_LUID (insn);
1265 df_insn_delete (NULL, uid);
1266 df_insn_create_insn_record (insn);
1267 DF_INSN_LUID (insn) = luid;
1271 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1272 df_insn_refs_collect (&collection_rec, bb, insn_info);
1274 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1277 df_refs_add_to_chains (&collection_rec, bb, insn);
1278 if (!DEBUG_INSN_P (insn))
1279 df_set_bb_dirty (bb);
1281 collection_rec.def_vec.release ();
1282 collection_rec.use_vec.release ();
1283 collection_rec.eq_use_vec.release ();
1284 collection_rec.mw_vec.release ();
1289 /* Same as df_insn_rescan, but don't mark the basic block as
1293 df_insn_rescan_debug_internal (rtx insn)
1295 unsigned int uid = INSN_UID (insn);
1296 struct df_insn_info *insn_info;
1298 gcc_assert (DEBUG_INSN_P (insn)
1299 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1304 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1309 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1311 bitmap_clear_bit (&df->insns_to_delete, uid);
1312 bitmap_clear_bit (&df->insns_to_rescan, uid);
1313 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1315 if (!insn_info->defs)
1318 if (insn_info->defs == df_null_ref_rec
1319 && insn_info->uses == df_null_ref_rec
1320 && insn_info->eq_uses == df_null_ref_rec
1321 && insn_info->mw_hardregs == df_null_mw_rec)
1324 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1328 df_ref_chain_delete_du_chain (insn_info->defs);
1329 df_ref_chain_delete_du_chain (insn_info->uses);
1330 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1333 df_ref_chain_delete (insn_info->defs);
1334 df_ref_chain_delete (insn_info->uses);
1335 df_ref_chain_delete (insn_info->eq_uses);
1336 df_scan_free_mws_vec (insn_info->mw_hardregs);
1338 insn_info->defs = df_null_ref_rec;
1339 insn_info->uses = df_null_ref_rec;
1340 insn_info->eq_uses = df_null_ref_rec;
1341 insn_info->mw_hardregs = df_null_mw_rec;
1347 /* Rescan all of the insns in the function. Note that the artificial
1348 uses and defs are not touched. This function will destroy def-se
1349 or use-def chains. */
1352 df_insn_rescan_all (void)
1354 bool no_insn_rescan = false;
1355 bool defer_insn_rescan = false;
1361 bitmap_initialize (&tmp, &df_bitmap_obstack);
1363 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1365 df_clear_flags (DF_NO_INSN_RESCAN);
1366 no_insn_rescan = true;
1369 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1371 df_clear_flags (DF_DEFER_INSN_RESCAN);
1372 defer_insn_rescan = true;
1375 bitmap_copy (&tmp, &df->insns_to_delete);
1376 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1378 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1380 df_insn_delete (NULL, uid);
1383 bitmap_clear (&tmp);
1384 bitmap_clear (&df->insns_to_delete);
1385 bitmap_clear (&df->insns_to_rescan);
1386 bitmap_clear (&df->insns_to_notes_rescan);
1391 FOR_BB_INSNS (bb, insn)
1393 df_insn_rescan (insn);
1398 df_set_flags (DF_NO_INSN_RESCAN);
1399 if (defer_insn_rescan)
1400 df_set_flags (DF_DEFER_INSN_RESCAN);
1404 /* Process all of the deferred rescans or deletions. */
1407 df_process_deferred_rescans (void)
1409 bool no_insn_rescan = false;
1410 bool defer_insn_rescan = false;
1415 bitmap_initialize (&tmp, &df_bitmap_obstack);
1417 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1419 df_clear_flags (DF_NO_INSN_RESCAN);
1420 no_insn_rescan = true;
1423 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1425 df_clear_flags (DF_DEFER_INSN_RESCAN);
1426 defer_insn_rescan = true;
1430 fprintf (dump_file, "starting the processing of deferred insns\n");
1432 bitmap_copy (&tmp, &df->insns_to_delete);
1433 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1435 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1437 df_insn_delete (NULL, uid);
1440 bitmap_copy (&tmp, &df->insns_to_rescan);
1441 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1443 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1445 df_insn_rescan (insn_info->insn);
1448 bitmap_copy (&tmp, &df->insns_to_notes_rescan);
1449 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1451 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1453 df_notes_rescan (insn_info->insn);
1457 fprintf (dump_file, "ending the processing of deferred insns\n");
1459 bitmap_clear (&tmp);
1460 bitmap_clear (&df->insns_to_delete);
1461 bitmap_clear (&df->insns_to_rescan);
1462 bitmap_clear (&df->insns_to_notes_rescan);
1465 df_set_flags (DF_NO_INSN_RESCAN);
1466 if (defer_insn_rescan)
1467 df_set_flags (DF_DEFER_INSN_RESCAN);
1469 /* If someone changed regs_ever_live during this pass, fix up the
1470 entry and exit blocks. */
1471 if (df->redo_entry_and_exit)
1473 df_update_entry_exit_and_calls ();
1474 df->redo_entry_and_exit = false;
1479 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1480 the uses if INCLUDE_USES. Include the eq_uses if
1484 df_count_refs (bool include_defs, bool include_uses,
1485 bool include_eq_uses)
1489 unsigned int m = df->regs_inited;
1491 for (regno = 0; regno < m; regno++)
1494 size += DF_REG_DEF_COUNT (regno);
1496 size += DF_REG_USE_COUNT (regno);
1497 if (include_eq_uses)
1498 size += DF_REG_EQ_USE_COUNT (regno);
1504 /* Take build ref table for either the uses or defs from the reg-use
1505 or reg-def chains. This version processes the refs in reg order
1506 which is likely to be best if processing the whole function. */
1509 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1512 bool include_eq_uses)
1514 unsigned int m = df->regs_inited;
1516 unsigned int offset = 0;
1519 if (df->changeable_flags & DF_NO_HARD_REGS)
1521 start = FIRST_PSEUDO_REGISTER;
1522 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1523 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1528 ref_info->total_size
1529 = df_count_refs (include_defs, include_uses, include_eq_uses);
1531 df_check_and_grow_ref_info (ref_info, 1);
1533 for (regno = start; regno < m; regno++)
1536 ref_info->begin[regno] = offset;
1539 df_ref ref = DF_REG_DEF_CHAIN (regno);
1542 ref_info->refs[offset] = ref;
1543 DF_REF_ID (ref) = offset++;
1545 ref = DF_REF_NEXT_REG (ref);
1546 gcc_checking_assert (offset < ref_info->refs_size);
1551 df_ref ref = DF_REG_USE_CHAIN (regno);
1554 ref_info->refs[offset] = ref;
1555 DF_REF_ID (ref) = offset++;
1557 ref = DF_REF_NEXT_REG (ref);
1558 gcc_checking_assert (offset < ref_info->refs_size);
1561 if (include_eq_uses)
1563 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1566 ref_info->refs[offset] = ref;
1567 DF_REF_ID (ref) = offset++;
1569 ref = DF_REF_NEXT_REG (ref);
1570 gcc_checking_assert (offset < ref_info->refs_size);
1573 ref_info->count[regno] = count;
1576 /* The bitmap size is not decremented when refs are deleted. So
1577 reset it now that we have squished out all of the empty
1579 ref_info->table_size = offset;
1583 /* Take build ref table for either the uses or defs from the reg-use
1584 or reg-def chains. This version processes the refs in insn order
1585 which is likely to be best if processing some segment of the
1589 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1592 bool include_eq_uses)
1595 unsigned int bb_index;
1596 unsigned int m = df->regs_inited;
1597 unsigned int offset = 0;
1600 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1602 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1603 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1605 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1606 df_check_and_grow_ref_info (ref_info, 1);
1608 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1610 basic_block bb = BASIC_BLOCK (bb_index);
1615 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1617 unsigned int regno = DF_REF_REGNO (*ref_rec);
1618 ref_info->count[regno]++;
1621 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1623 unsigned int regno = DF_REF_REGNO (*ref_rec);
1624 ref_info->count[regno]++;
1627 FOR_BB_INSNS (bb, insn)
1631 unsigned int uid = INSN_UID (insn);
1634 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1636 unsigned int regno = DF_REF_REGNO (*ref_rec);
1637 ref_info->count[regno]++;
1640 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1642 unsigned int regno = DF_REF_REGNO (*ref_rec);
1643 ref_info->count[regno]++;
1645 if (include_eq_uses)
1646 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1648 unsigned int regno = DF_REF_REGNO (*ref_rec);
1649 ref_info->count[regno]++;
1655 for (r = start; r < m; r++)
1657 ref_info->begin[r] = offset;
1658 offset += ref_info->count[r];
1659 ref_info->count[r] = 0;
1662 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1664 basic_block bb = BASIC_BLOCK (bb_index);
1669 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1671 df_ref ref = *ref_rec;
1672 unsigned int regno = DF_REF_REGNO (ref);
1676 = ref_info->begin[regno] + ref_info->count[regno]++;
1677 DF_REF_ID (ref) = id;
1678 ref_info->refs[id] = ref;
1682 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1684 df_ref ref = *ref_rec;
1685 unsigned int regno = DF_REF_REGNO (ref);
1689 = ref_info->begin[regno] + ref_info->count[regno]++;
1690 DF_REF_ID (ref) = id;
1691 ref_info->refs[id] = ref;
1695 FOR_BB_INSNS (bb, insn)
1699 unsigned int uid = INSN_UID (insn);
1702 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1704 df_ref ref = *ref_rec;
1705 unsigned int regno = DF_REF_REGNO (ref);
1709 = ref_info->begin[regno] + ref_info->count[regno]++;
1710 DF_REF_ID (ref) = id;
1711 ref_info->refs[id] = ref;
1715 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1717 df_ref ref = *ref_rec;
1718 unsigned int regno = DF_REF_REGNO (ref);
1722 = ref_info->begin[regno] + ref_info->count[regno]++;
1723 DF_REF_ID (ref) = id;
1724 ref_info->refs[id] = ref;
1727 if (include_eq_uses)
1728 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1730 df_ref ref = *ref_rec;
1731 unsigned int regno = DF_REF_REGNO (ref);
1735 = ref_info->begin[regno] + ref_info->count[regno]++;
1736 DF_REF_ID (ref) = id;
1737 ref_info->refs[id] = ref;
1744 /* The bitmap size is not decremented when refs are deleted. So
1745 reset it now that we have squished out all of the empty
1748 ref_info->table_size = offset;
1751 /* Take build ref table for either the uses or defs from the reg-use
1752 or reg-def chains. */
1755 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1758 bool include_eq_uses)
1760 if (df->analyze_subset)
1761 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1762 include_uses, include_eq_uses);
1764 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1765 include_uses, include_eq_uses);
1769 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1771 df_add_refs_to_table (unsigned int offset,
1772 struct df_ref_info *ref_info,
1777 df_ref ref = *ref_vec;
1778 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
1779 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1781 ref_info->refs[offset] = ref;
1782 DF_REF_ID (*ref_vec) = offset++;
1790 /* Count the number of refs in all of the insns of BB. Include the
1791 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1792 eq_uses if INCLUDE_EQ_USES. */
1795 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1796 struct df_ref_info *ref_info,
1797 bool include_defs, bool include_uses,
1798 bool include_eq_uses)
1803 offset = df_add_refs_to_table (offset, ref_info,
1804 df_get_artificial_defs (bb->index));
1806 offset = df_add_refs_to_table (offset, ref_info,
1807 df_get_artificial_uses (bb->index));
1809 FOR_BB_INSNS (bb, insn)
1812 unsigned int uid = INSN_UID (insn);
1814 offset = df_add_refs_to_table (offset, ref_info,
1815 DF_INSN_UID_DEFS (uid));
1817 offset = df_add_refs_to_table (offset, ref_info,
1818 DF_INSN_UID_USES (uid));
1819 if (include_eq_uses)
1820 offset = df_add_refs_to_table (offset, ref_info,
1821 DF_INSN_UID_EQ_USES (uid));
1827 /* Organize the refs by insn into the table in REF_INFO. If
1828 blocks_to_analyze is defined, use that set, otherwise the entire
1829 program. Include the defs if INCLUDE_DEFS. Include the uses if
1830 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1833 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1834 bool include_defs, bool include_uses,
1835 bool include_eq_uses)
1838 unsigned int offset = 0;
1840 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1841 df_check_and_grow_ref_info (ref_info, 1);
1842 if (df->blocks_to_analyze)
1847 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1849 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK (index), offset, ref_info,
1850 include_defs, include_uses,
1854 ref_info->table_size = offset;
1859 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1860 include_defs, include_uses,
1862 ref_info->table_size = offset;
1867 /* If the use refs in DF are not organized, reorganize them. */
1870 df_maybe_reorganize_use_refs (enum df_ref_order order)
1872 if (order == df->use_info.ref_order)
1877 case DF_REF_ORDER_BY_REG:
1878 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1881 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1882 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1885 case DF_REF_ORDER_BY_INSN:
1886 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1889 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1890 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1893 case DF_REF_ORDER_NO_TABLE:
1894 free (df->use_info.refs);
1895 df->use_info.refs = NULL;
1896 df->use_info.refs_size = 0;
1899 case DF_REF_ORDER_UNORDERED:
1900 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1905 df->use_info.ref_order = order;
1909 /* If the def refs in DF are not organized, reorganize them. */
1912 df_maybe_reorganize_def_refs (enum df_ref_order order)
1914 if (order == df->def_info.ref_order)
1919 case DF_REF_ORDER_BY_REG:
1920 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1923 case DF_REF_ORDER_BY_INSN:
1924 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1927 case DF_REF_ORDER_NO_TABLE:
1928 free (df->def_info.refs);
1929 df->def_info.refs = NULL;
1930 df->def_info.refs_size = 0;
1933 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1934 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1935 case DF_REF_ORDER_UNORDERED:
1936 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1941 df->def_info.ref_order = order;
1945 /* Change all of the basic block references in INSN to use the insn's
1946 current basic block. This function is called from routines that move
1947 instructions from one block to another. */
1950 df_insn_change_bb (rtx insn, basic_block new_bb)
1952 basic_block old_bb = BLOCK_FOR_INSN (insn);
1953 struct df_insn_info *insn_info;
1954 unsigned int uid = INSN_UID (insn);
1956 if (old_bb == new_bb)
1959 set_block_for_insn (insn, new_bb);
1965 fprintf (dump_file, "changing bb of uid %d\n", uid);
1967 insn_info = DF_INSN_UID_SAFE_GET (uid);
1968 if (insn_info == NULL)
1971 fprintf (dump_file, " unscanned insn\n");
1972 df_insn_rescan (insn);
1979 df_set_bb_dirty (new_bb);
1983 fprintf (dump_file, " from %d to %d\n",
1984 old_bb->index, new_bb->index);
1985 df_set_bb_dirty (old_bb);
1989 fprintf (dump_file, " to %d\n", new_bb->index);
1993 /* Helper function for df_ref_change_reg_with_loc. */
1996 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1997 struct df_reg_info *new_df,
1998 int new_regno, rtx loc)
2000 df_ref the_ref = old_df->reg_chain;
2004 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
2005 && DF_REF_LOC (the_ref)
2006 && (*DF_REF_LOC (the_ref) == loc))
2008 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
2009 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
2010 df_ref *ref_vec, *ref_vec_t;
2011 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
2012 unsigned int count = 0;
2014 DF_REF_REGNO (the_ref) = new_regno;
2015 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
2017 /* Pull the_ref out of the old regno chain. */
2019 DF_REF_NEXT_REG (prev_ref) = next_ref;
2021 old_df->reg_chain = next_ref;
2023 DF_REF_PREV_REG (next_ref) = prev_ref;
2026 /* Put the ref into the new regno chain. */
2027 DF_REF_PREV_REG (the_ref) = NULL;
2028 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
2029 if (new_df->reg_chain)
2030 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
2031 new_df->reg_chain = the_ref;
2033 if (DF_REF_BB (the_ref))
2034 df_set_bb_dirty (DF_REF_BB (the_ref));
2036 /* Need to sort the record again that the ref was in because
2037 the regno is a sorting key. First, find the right
2039 if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
2040 ref_vec = insn_info->eq_uses;
2042 ref_vec = insn_info->uses;
2044 fprintf (dump_file, "changing reg in insn %d\n",
2045 DF_REF_INSN_UID (the_ref));
2047 ref_vec_t = ref_vec;
2049 /* Find the length. */
2055 qsort (ref_vec, count, sizeof (df_ref ), df_ref_compare);
2060 the_ref = DF_REF_NEXT_REG (the_ref);
2065 /* Change the regno of all refs that contained LOC from OLD_REGNO to
2066 NEW_REGNO. Refs that do not match LOC are not changed which means
2067 that artificial refs are not changed since they have no loc. This
2068 call is to support the SET_REGNO macro. */
2071 df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
2073 if ((!df) || (old_regno == -1) || (old_regno == new_regno))
2076 df_grow_reg_info ();
2078 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
2079 DF_REG_DEF_GET (new_regno), new_regno, loc);
2080 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
2081 DF_REG_USE_GET (new_regno), new_regno, loc);
2082 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
2083 DF_REG_EQ_USE_GET (new_regno), new_regno, loc);
2087 /* Delete the mw_hardregs that point into the eq_notes. */
2090 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
2092 struct df_mw_hardreg **mw_vec = insn_info->mw_hardregs;
2093 unsigned int deleted = 0;
2094 unsigned int count = 0;
2095 struct df_scan_problem_data *problem_data
2096 = (struct df_scan_problem_data *) df_scan->problem_data;
2103 if ((*mw_vec)->flags & DF_REF_IN_NOTE)
2105 struct df_mw_hardreg **temp_vec = mw_vec;
2107 pool_free (problem_data->mw_reg_pool, *mw_vec);
2109 /* Shove the remaining ones down one to fill the gap. While
2110 this looks n**2, it is highly unusual to have any mw regs
2111 in eq_notes and the chances of more than one are almost
2115 *temp_vec = *(temp_vec + 1);
2129 df_scan_free_mws_vec (insn_info->mw_hardregs);
2130 insn_info->mw_hardregs = df_null_mw_rec;
2137 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
2140 df_notes_rescan (rtx insn)
2142 struct df_insn_info *insn_info;
2143 unsigned int uid = INSN_UID (insn);
2148 /* The client has disabled rescanning and plans to do it itself. */
2149 if (df->changeable_flags & DF_NO_INSN_RESCAN)
2152 /* Do nothing if the insn hasn't been emitted yet. */
2153 if (!BLOCK_FOR_INSN (insn))
2156 df_grow_bb_info (df_scan);
2157 df_grow_reg_info ();
2159 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID(insn));
2161 /* The client has deferred rescanning. */
2162 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
2166 insn_info = df_insn_create_insn_record (insn);
2167 insn_info->defs = df_null_ref_rec;
2168 insn_info->uses = df_null_ref_rec;
2169 insn_info->eq_uses = df_null_ref_rec;
2170 insn_info->mw_hardregs = df_null_mw_rec;
2173 bitmap_clear_bit (&df->insns_to_delete, uid);
2174 /* If the insn is set to be rescanned, it does not need to also
2175 be notes rescanned. */
2176 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
2177 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
2181 bitmap_clear_bit (&df->insns_to_delete, uid);
2182 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
2186 basic_block bb = BLOCK_FOR_INSN (insn);
2188 struct df_collection_rec collection_rec;
2189 unsigned int num_deleted;
2190 unsigned int mw_len;
2192 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
2193 vec_stack_alloc (df_ref, collection_rec.eq_use_vec, 32);
2194 vec_stack_alloc (df_mw_hardreg_ptr, collection_rec.mw_vec, 32);
2196 num_deleted = df_mw_hardreg_chain_delete_eq_uses (insn_info);
2197 df_ref_chain_delete (insn_info->eq_uses);
2198 insn_info->eq_uses = NULL;
2200 /* Process REG_EQUIV/REG_EQUAL notes */
2201 for (note = REG_NOTES (insn); note;
2202 note = XEXP (note, 1))
2204 switch (REG_NOTE_KIND (note))
2208 df_uses_record (&collection_rec,
2209 &XEXP (note, 0), DF_REF_REG_USE,
2210 bb, insn_info, DF_REF_IN_NOTE);
2216 /* Find some place to put any new mw_hardregs. */
2217 df_canonize_collection_rec (&collection_rec);
2218 mw_len = collection_rec.mw_vec.length ();
2221 unsigned int count = 0;
2222 struct df_mw_hardreg **mw_rec = insn_info->mw_hardregs;
2231 /* Append to the end of the existing record after
2232 expanding it if necessary. */
2233 if (mw_len > num_deleted)
2235 insn_info->mw_hardregs =
2236 XRESIZEVEC (struct df_mw_hardreg *,
2237 insn_info->mw_hardregs,
2238 count + 1 + mw_len);
2240 memcpy (&insn_info->mw_hardregs[count],
2241 collection_rec.mw_vec.address (),
2242 mw_len * sizeof (struct df_mw_hardreg *));
2243 insn_info->mw_hardregs[count + mw_len] = NULL;
2244 qsort (insn_info->mw_hardregs, count + mw_len,
2245 sizeof (struct df_mw_hardreg *), df_mw_compare);
2249 /* No vector there. */
2250 insn_info->mw_hardregs
2251 = XNEWVEC (struct df_mw_hardreg*, 1 + mw_len);
2252 memcpy (insn_info->mw_hardregs,
2253 collection_rec.mw_vec.address (),
2254 mw_len * sizeof (struct df_mw_hardreg *));
2255 insn_info->mw_hardregs[mw_len] = NULL;
2258 /* Get rid of the mw_rec so that df_refs_add_to_chains will
2260 collection_rec.mw_vec.release ();
2261 df_refs_add_to_chains (&collection_rec, bb, insn);
2262 collection_rec.eq_use_vec.release ();
2265 df_insn_rescan (insn);
2270 /*----------------------------------------------------------------------------
2271 Hard core instruction scanning code. No external interfaces here,
2272 just a lot of routines that look inside insns.
2273 ----------------------------------------------------------------------------*/
2276 /* Return true if the contents of two df_ref's are identical.
2277 It ignores DF_REF_MARKER. */
2280 df_ref_equal_p (df_ref ref1, df_ref ref2)
2288 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2289 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2290 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2291 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2292 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2293 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2294 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2295 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2298 switch (DF_REF_CLASS (ref1))
2300 case DF_REF_ARTIFICIAL:
2304 case DF_REF_REGULAR:
2305 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2314 /* Compare REF1 and REF2 for sorting. This is only called from places
2315 where all of the refs are of the same type, in the same insn, and
2316 have the same bb. So these fields are not checked. */
2319 df_ref_compare (const void *r1, const void *r2)
2321 const df_ref ref1 = *(const df_ref *)r1;
2322 const df_ref ref2 = *(const df_ref *)r2;
2327 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2328 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2330 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2331 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2333 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2334 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2336 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2337 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2339 /* Cannot look at the LOC field on artificial refs. */
2340 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2341 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2342 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2344 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2346 /* If two refs are identical except that one of them has is from
2347 a mw and one is not, we need to have the one with the mw
2349 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2350 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2351 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2352 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2358 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2362 df_swap_refs (vec<df_ref, va_stack> *ref_vec, int i, int j)
2364 df_ref tmp = (*ref_vec)[i];
2365 (*ref_vec)[i] = (*ref_vec)[j];
2366 (*ref_vec)[j] = tmp;
2369 /* Sort and compress a set of refs. */
2372 df_sort_and_compress_refs (vec<df_ref, va_stack> *ref_vec)
2376 unsigned int dist = 0;
2378 count = ref_vec->length ();
2380 /* If there are 1 or 0 elements, there is nothing to do. */
2383 else if (count == 2)
2385 df_ref r0 = (*ref_vec)[0];
2386 df_ref r1 = (*ref_vec)[1];
2387 if (df_ref_compare (&r0, &r1) > 0)
2388 df_swap_refs (ref_vec, 0, 1);
2392 for (i = 0; i < count - 1; i++)
2394 df_ref r0 = (*ref_vec)[i];
2395 df_ref r1 = (*ref_vec)[i + 1];
2396 if (df_ref_compare (&r0, &r1) >= 0)
2399 /* If the array is already strictly ordered,
2400 which is the most common case for large COUNT case
2401 (which happens for CALL INSNs),
2402 no need to sort and filter out duplicate.
2403 Simply return the count.
2404 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2405 of DF_REF_COMPARE. */
2408 ref_vec->qsort (df_ref_compare);
2411 for (i=0; i<count-dist; i++)
2413 /* Find the next ref that is not equal to the current ref. */
2414 while (i + dist + 1 < count
2415 && df_ref_equal_p ((*ref_vec)[i],
2416 (*ref_vec)[i + dist + 1]))
2418 df_free_ref ((*ref_vec)[i + dist + 1]);
2421 /* Copy it down to the next position. */
2422 if (dist && i + dist + 1 < count)
2423 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2427 ref_vec->truncate (count);
2431 /* Return true if the contents of two df_ref's are identical.
2432 It ignores DF_REF_MARKER. */
2435 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2439 return (mw1 == mw2) ||
2440 (mw1->mw_reg == mw2->mw_reg
2441 && mw1->type == mw2->type
2442 && mw1->flags == mw2->flags
2443 && mw1->start_regno == mw2->start_regno
2444 && mw1->end_regno == mw2->end_regno);
2448 /* Compare MW1 and MW2 for sorting. */
2451 df_mw_compare (const void *m1, const void *m2)
2453 const struct df_mw_hardreg *const mw1 = *(const struct df_mw_hardreg *const*)m1;
2454 const struct df_mw_hardreg *const mw2 = *(const struct df_mw_hardreg *const*)m2;
2459 if (mw1->type != mw2->type)
2460 return mw1->type - mw2->type;
2462 if (mw1->flags != mw2->flags)
2463 return mw1->flags - mw2->flags;
2465 if (mw1->start_regno != mw2->start_regno)
2466 return mw1->start_regno - mw2->start_regno;
2468 if (mw1->end_regno != mw2->end_regno)
2469 return mw1->end_regno - mw2->end_regno;
2471 if (mw1->mw_reg != mw2->mw_reg)
2472 return mw1->mw_order - mw2->mw_order;
2478 /* Sort and compress a set of refs. */
2481 df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_stack> *mw_vec)
2484 struct df_scan_problem_data *problem_data
2485 = (struct df_scan_problem_data *) df_scan->problem_data;
2487 unsigned int dist = 0;
2489 count = mw_vec->length ();
2492 else if (count == 2)
2494 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2495 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2496 if (df_mw_compare (&m0, &m1) > 0)
2498 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2499 (*mw_vec)[0] = (*mw_vec)[1];
2504 mw_vec->qsort (df_mw_compare);
2506 for (i=0; i<count-dist; i++)
2508 /* Find the next ref that is not equal to the current ref. */
2509 while (i + dist + 1 < count
2510 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2512 pool_free (problem_data->mw_reg_pool,
2513 (*mw_vec)[i + dist + 1]);
2516 /* Copy it down to the next position. */
2517 if (dist && i + dist + 1 < count)
2518 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2522 mw_vec->truncate (count);
2526 /* Sort and remove duplicates from the COLLECTION_REC. */
2529 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2531 df_sort_and_compress_refs (&collection_rec->def_vec);
2532 df_sort_and_compress_refs (&collection_rec->use_vec);
2533 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2534 df_sort_and_compress_mws (&collection_rec->mw_vec);
2538 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2541 df_install_ref (df_ref this_ref,
2542 struct df_reg_info *reg_info,
2543 struct df_ref_info *ref_info,
2546 unsigned int regno = DF_REF_REGNO (this_ref);
2547 /* Add the ref to the reg_{def,use,eq_use} chain. */
2548 df_ref head = reg_info->reg_chain;
2550 reg_info->reg_chain = this_ref;
2553 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2555 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2556 df->hard_regs_live_count[regno]++;
2559 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2560 && DF_REF_PREV_REG (this_ref) == NULL);
2562 DF_REF_NEXT_REG (this_ref) = head;
2564 /* We cannot actually link to the head of the chain. */
2565 DF_REF_PREV_REG (this_ref) = NULL;
2568 DF_REF_PREV_REG (head) = this_ref;
2572 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2573 df_check_and_grow_ref_info (ref_info, 1);
2574 DF_REF_ID (this_ref) = ref_info->table_size;
2575 /* Add the ref to the big array of defs. */
2576 ref_info->refs[ref_info->table_size] = this_ref;
2577 ref_info->table_size++;
2580 DF_REF_ID (this_ref) = -1;
2582 ref_info->total_size++;
2586 /* This function takes one of the groups of refs (defs, uses or
2587 eq_uses) and installs the entire group into the insn. It also adds
2588 each of these refs into the appropriate chains. */
2591 df_install_refs (basic_block bb,
2592 vec<df_ref, va_stack> old_vec,
2593 struct df_reg_info **reg_info,
2594 struct df_ref_info *ref_info,
2599 count = old_vec.length ();
2602 df_ref *new_vec = XNEWVEC (df_ref, count + 1);
2607 switch (ref_info->ref_order)
2609 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2610 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2611 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2612 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2613 add_to_table = true;
2615 case DF_REF_ORDER_UNORDERED:
2616 case DF_REF_ORDER_BY_REG:
2617 case DF_REF_ORDER_BY_INSN:
2618 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2619 add_to_table = !is_notes;
2622 add_to_table = false;
2626 /* Do not add if ref is not in the right blocks. */
2627 if (add_to_table && df->analyze_subset)
2628 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2630 FOR_EACH_VEC_ELT (old_vec, ix, this_ref)
2632 new_vec[ix] = this_ref;
2633 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2634 ref_info, add_to_table);
2637 new_vec[count] = NULL;
2641 return df_null_ref_rec;
2645 /* This function takes the mws installs the entire group into the
2648 static struct df_mw_hardreg **
2649 df_install_mws (vec<df_mw_hardreg_ptr, va_stack> old_vec)
2653 count = old_vec.length ();
2656 struct df_mw_hardreg **new_vec
2657 = XNEWVEC (struct df_mw_hardreg*, count + 1);
2658 memcpy (new_vec, old_vec.address (),
2659 sizeof (struct df_mw_hardreg*) * count);
2660 new_vec[count] = NULL;
2664 return df_null_mw_rec;
2668 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2669 chains and update other necessary information. */
2672 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2673 basic_block bb, rtx insn)
2677 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2678 /* If there is a vector in the collection rec, add it to the
2679 insn. A null rec is a signal that the caller will handle the
2681 if (collection_rec->def_vec.exists ())
2683 df_scan_free_ref_vec (insn_rec->defs);
2685 = df_install_refs (bb, collection_rec->def_vec,
2687 &df->def_info, false);
2689 if (collection_rec->use_vec.exists ())
2691 df_scan_free_ref_vec (insn_rec->uses);
2693 = df_install_refs (bb, collection_rec->use_vec,
2695 &df->use_info, false);
2697 if (collection_rec->eq_use_vec.exists ())
2699 df_scan_free_ref_vec (insn_rec->eq_uses);
2701 = df_install_refs (bb, collection_rec->eq_use_vec,
2703 &df->use_info, true);
2705 if (collection_rec->mw_vec.exists ())
2707 df_scan_free_mws_vec (insn_rec->mw_hardregs);
2708 insn_rec->mw_hardregs
2709 = df_install_mws (collection_rec->mw_vec);
2714 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2716 df_scan_free_ref_vec (bb_info->artificial_defs);
2717 bb_info->artificial_defs
2718 = df_install_refs (bb, collection_rec->def_vec,
2720 &df->def_info, false);
2721 df_scan_free_ref_vec (bb_info->artificial_uses);
2722 bb_info->artificial_uses
2723 = df_install_refs (bb, collection_rec->use_vec,
2725 &df->use_info, false);
2730 /* Allocate a ref and initialize its fields. */
2733 df_ref_create_structure (enum df_ref_class cl,
2734 struct df_collection_rec *collection_rec,
2736 basic_block bb, struct df_insn_info *info,
2737 enum df_ref_type ref_type,
2740 df_ref this_ref = NULL;
2741 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2742 struct df_scan_problem_data *problem_data
2743 = (struct df_scan_problem_data *) df_scan->problem_data;
2748 this_ref = (df_ref) pool_alloc (problem_data->ref_base_pool);
2749 gcc_checking_assert (loc == NULL);
2752 case DF_REF_ARTIFICIAL:
2753 this_ref = (df_ref) pool_alloc (problem_data->ref_artificial_pool);
2754 this_ref->artificial_ref.bb = bb;
2755 gcc_checking_assert (loc == NULL);
2758 case DF_REF_REGULAR:
2759 this_ref = (df_ref) pool_alloc (problem_data->ref_regular_pool);
2760 this_ref->regular_ref.loc = loc;
2761 gcc_checking_assert (loc);
2765 DF_REF_CLASS (this_ref) = cl;
2766 DF_REF_ID (this_ref) = -1;
2767 DF_REF_REG (this_ref) = reg;
2768 DF_REF_REGNO (this_ref) = regno;
2769 DF_REF_TYPE (this_ref) = ref_type;
2770 DF_REF_INSN_INFO (this_ref) = info;
2771 DF_REF_CHAIN (this_ref) = NULL;
2772 DF_REF_FLAGS (this_ref) = ref_flags;
2773 DF_REF_NEXT_REG (this_ref) = NULL;
2774 DF_REF_PREV_REG (this_ref) = NULL;
2775 DF_REF_ORDER (this_ref) = df->ref_order++;
2777 /* We need to clear this bit because fwprop, and in the future
2778 possibly other optimizations sometimes create new refs using ond
2779 refs as the model. */
2780 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2782 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2783 if (regno < FIRST_PSEUDO_REGISTER
2784 && !DF_REF_IS_ARTIFICIAL (this_ref)
2785 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2787 if (DF_REF_REG_DEF_P (this_ref))
2789 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2790 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2792 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2793 && (regno == FRAME_POINTER_REGNUM
2794 || regno == ARG_POINTER_REGNUM)))
2795 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2800 if (DF_REF_REG_DEF_P (this_ref))
2801 collection_rec->def_vec.safe_push (this_ref);
2802 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2803 collection_rec->eq_use_vec.safe_push (this_ref);
2805 collection_rec->use_vec.safe_push (this_ref);
2808 df_install_ref_incremental (this_ref);
2814 /* Create new references of type DF_REF_TYPE for each part of register REG
2815 at address LOC within INSN of BB. */
2819 df_ref_record (enum df_ref_class cl,
2820 struct df_collection_rec *collection_rec,
2822 basic_block bb, struct df_insn_info *insn_info,
2823 enum df_ref_type ref_type,
2828 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2830 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2831 if (regno < FIRST_PSEUDO_REGISTER)
2833 struct df_mw_hardreg *hardreg = NULL;
2834 struct df_scan_problem_data *problem_data
2835 = (struct df_scan_problem_data *) df_scan->problem_data;
2837 unsigned int endregno;
2840 if (GET_CODE (reg) == SUBREG)
2842 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2843 SUBREG_BYTE (reg), GET_MODE (reg));
2844 endregno = regno + subreg_nregs (reg);
2847 endregno = END_HARD_REGNO (reg);
2849 /* If this is a multiword hardreg, we create some extra
2850 datastructures that will enable us to easily build REG_DEAD
2851 and REG_UNUSED notes. */
2853 && (endregno != regno + 1) && insn_info)
2855 /* Sets to a subreg of a multiword register are partial.
2856 Sets to a non-subreg of a multiword register are not. */
2857 if (GET_CODE (reg) == SUBREG)
2858 ref_flags |= DF_REF_PARTIAL;
2859 ref_flags |= DF_REF_MW_HARDREG;
2861 hardreg = (struct df_mw_hardreg *) pool_alloc (problem_data->mw_reg_pool);
2862 hardreg->type = ref_type;
2863 hardreg->flags = ref_flags;
2864 hardreg->mw_reg = reg;
2865 hardreg->start_regno = regno;
2866 hardreg->end_regno = endregno - 1;
2867 hardreg->mw_order = df->ref_order++;
2868 collection_rec->mw_vec.safe_push (hardreg);
2871 for (i = regno; i < endregno; i++)
2873 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2874 bb, insn_info, ref_type, ref_flags);
2876 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2881 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2882 ref_type, ref_flags);
2887 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2888 covered by the outer mode is smaller than that covered by the inner mode,
2889 is a read-modify-write operation.
2890 This function returns true iff the SUBREG X is such a SUBREG. */
2893 df_read_modify_subreg_p (rtx x)
2895 unsigned int isize, osize;
2896 if (GET_CODE (x) != SUBREG)
2898 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2899 osize = GET_MODE_SIZE (GET_MODE (x));
2900 return isize > osize
2901 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2905 /* Process all the registers defined in the rtx pointed by LOC.
2906 Autoincrement/decrement definitions will be picked up by df_uses_record.
2907 Any change here has to be matched in df_find_hard_reg_defs_1. */
2910 df_def_record_1 (struct df_collection_rec *collection_rec,
2911 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2916 /* It is legal to have a set destination be a parallel. */
2917 if (GET_CODE (dst) == PARALLEL)
2920 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2922 rtx temp = XVECEXP (dst, 0, i);
2923 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2924 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2925 bb, insn_info, flags);
2930 if (GET_CODE (dst) == STRICT_LOW_PART)
2932 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2934 loc = &XEXP (dst, 0);
2938 if (GET_CODE (dst) == ZERO_EXTRACT)
2940 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2942 loc = &XEXP (dst, 0);
2946 /* At this point if we do not have a reg or a subreg, just return. */
2949 df_ref_record (DF_REF_REGULAR, collection_rec,
2950 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2952 /* We want to keep sp alive everywhere - by making all
2953 writes to sp also use of sp. */
2954 if (REGNO (dst) == STACK_POINTER_REGNUM)
2955 df_ref_record (DF_REF_BASE, collection_rec,
2956 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2958 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2960 if (df_read_modify_subreg_p (dst))
2961 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2963 flags |= DF_REF_SUBREG;
2965 df_ref_record (DF_REF_REGULAR, collection_rec,
2966 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2971 /* Process all the registers defined in the pattern rtx, X. Any change
2972 here has to be matched in df_find_hard_reg_defs. */
2975 df_defs_record (struct df_collection_rec *collection_rec,
2976 rtx x, basic_block bb, struct df_insn_info *insn_info,
2979 RTX_CODE code = GET_CODE (x);
2985 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2989 flags |= DF_REF_MUST_CLOBBER;
2990 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2994 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2995 bb, insn_info, DF_REF_CONDITIONAL);
2999 for (i = 0; i < XVECLEN (x, 0); i++)
3000 df_defs_record (collection_rec, XVECEXP (x, 0, i),
3001 bb, insn_info, flags);
3004 /* No DEFs to record in other cases */
3009 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
3010 destination of a set or clobber. This has to match the logic in
3011 df_defs_record_1. */
3014 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
3016 /* It is legal to have a set destination be a parallel. */
3017 if (GET_CODE (dst) == PARALLEL)
3020 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
3022 rtx temp = XVECEXP (dst, 0, i);
3023 gcc_assert (GET_CODE (temp) == EXPR_LIST);
3024 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
3029 if (GET_CODE (dst) == STRICT_LOW_PART)
3030 dst = XEXP (dst, 0);
3032 if (GET_CODE (dst) == ZERO_EXTRACT)
3033 dst = XEXP (dst, 0);
3035 /* At this point if we do not have a reg or a subreg, just return. */
3036 if (REG_P (dst) && HARD_REGISTER_P (dst))
3037 SET_HARD_REG_BIT (*defs, REGNO (dst));
3038 else if (GET_CODE (dst) == SUBREG
3039 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
3040 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
3043 /* Set bits in *DEFS for hard registers defined in the pattern X. This
3044 has to match the logic in df_defs_record. */
3047 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
3049 RTX_CODE code = GET_CODE (x);
3055 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
3059 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
3063 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
3067 for (i = 0; i < XVECLEN (x, 0); i++)
3068 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
3071 /* No DEFs to record in other cases */
3077 /* Process all the registers used in the rtx at address LOC. */
3080 df_uses_record (struct df_collection_rec *collection_rec,
3081 rtx *loc, enum df_ref_type ref_type,
3082 basic_block bb, struct df_insn_info *insn_info,
3092 code = GET_CODE (x);
3106 /* If we are clobbering a MEM, mark any registers inside the address
3108 if (MEM_P (XEXP (x, 0)))
3109 df_uses_record (collection_rec,
3110 &XEXP (XEXP (x, 0), 0),
3111 DF_REF_REG_MEM_STORE,
3115 /* If we're clobbering a REG then we have a def so ignore. */
3119 df_uses_record (collection_rec,
3120 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
3121 bb, insn_info, flags & DF_REF_IN_NOTE);
3125 /* While we're here, optimize this case. */
3126 flags |= DF_REF_PARTIAL;
3127 /* In case the SUBREG is not of a REG, do not optimize. */
3128 if (!REG_P (SUBREG_REG (x)))
3130 loc = &SUBREG_REG (x);
3131 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
3134 /* ... Fall through ... */
3137 df_ref_record (DF_REF_REGULAR, collection_rec,
3138 x, loc, bb, insn_info,
3145 df_uses_record (collection_rec,
3146 &XEXP (x, 1), ref_type, bb, insn_info, flags);
3147 df_uses_record (collection_rec,
3148 &XEXP (x, 2), ref_type, bb, insn_info, flags);
3150 /* If the parameters to the zero or sign extract are
3151 constants, strip them off and recurse, otherwise there is
3152 no information that we can gain from this operation. */
3153 if (code == ZERO_EXTRACT)
3154 flags |= DF_REF_ZERO_EXTRACT;
3156 flags |= DF_REF_SIGN_EXTRACT;
3158 df_uses_record (collection_rec,
3159 &XEXP (x, 0), ref_type, bb, insn_info, flags);
3166 rtx dst = SET_DEST (x);
3167 gcc_assert (!(flags & DF_REF_IN_NOTE));
3168 df_uses_record (collection_rec,
3169 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
3171 switch (GET_CODE (dst))
3174 if (df_read_modify_subreg_p (dst))
3176 df_uses_record (collection_rec, &SUBREG_REG (dst),
3177 DF_REF_REG_USE, bb, insn_info,
3178 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
3189 df_uses_record (collection_rec, &XEXP (dst, 0),
3190 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
3192 case STRICT_LOW_PART:
3194 rtx *temp = &XEXP (dst, 0);
3195 /* A strict_low_part uses the whole REG and not just the
3197 dst = XEXP (dst, 0);
3198 df_uses_record (collection_rec,
3199 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
3200 DF_REF_REG_USE, bb, insn_info,
3201 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
3206 df_uses_record (collection_rec, &XEXP (dst, 1),
3207 DF_REF_REG_USE, bb, insn_info, flags);
3208 df_uses_record (collection_rec, &XEXP (dst, 2),
3209 DF_REF_REG_USE, bb, insn_info, flags);
3210 if (GET_CODE (XEXP (dst,0)) == MEM)
3211 df_uses_record (collection_rec, &XEXP (dst, 0),
3212 DF_REF_REG_USE, bb, insn_info,
3215 df_uses_record (collection_rec, &XEXP (dst, 0),
3216 DF_REF_REG_USE, bb, insn_info,
3217 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
3232 case UNSPEC_VOLATILE:
3236 /* Traditional and volatile asm instructions must be
3237 considered to use and clobber all hard registers, all
3238 pseudo-registers and all of memory. So must TRAP_IF and
3239 UNSPEC_VOLATILE operations.
3241 Consider for instance a volatile asm that changes the fpu
3242 rounding mode. An insn should not be moved across this
3243 even if it only uses pseudo-regs because it might give an
3244 incorrectly rounded result.
3246 However, flow.c's liveness computation did *not* do this,
3247 giving the reasoning as " ?!? Unfortunately, marking all
3248 hard registers as live causes massive problems for the
3249 register allocator and marking all pseudos as live creates
3250 mountains of uninitialized variable warnings."
3252 In order to maintain the status quo with regard to liveness
3253 and uses, we do what flow.c did and just mark any regs we
3254 can find in ASM_OPERANDS as used. In global asm insns are
3255 scanned and regs_asm_clobbered is filled out.
3257 For all ASM_OPERANDS, we must traverse the vector of input
3258 operands. We can not just fall through here since then we
3259 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3260 which do not indicate traditional asms unlike their normal
3262 if (code == ASM_OPERANDS)
3266 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3267 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
3268 DF_REF_REG_USE, bb, insn_info, flags);
3275 df_uses_record (collection_rec,
3276 &PAT_VAR_LOCATION_LOC (x),
3277 DF_REF_REG_USE, bb, insn_info, flags);
3286 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3287 /* Catch the def of the register being modified. */
3288 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3291 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3293 /* ... Fall through to handle uses ... */
3299 /* Recursively scan the operands of this expression. */
3301 const char *fmt = GET_RTX_FORMAT (code);
3304 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3308 /* Tail recursive case: save a function call level. */
3314 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3315 bb, insn_info, flags);
3317 else if (fmt[i] == 'E')
3320 for (j = 0; j < XVECLEN (x, i); j++)
3321 df_uses_record (collection_rec,
3322 &XVECEXP (x, i, j), ref_type,
3323 bb, insn_info, flags);
3332 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3335 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3340 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3342 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3346 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3347 DF_REF_LOC (ref), DF_REF_BB (ref),
3348 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3349 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3350 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3356 /* Get call's extra defs and uses (track caller-saved registers). */
3359 df_get_call_refs (struct df_collection_rec *collection_rec,
3361 struct df_insn_info *insn_info,
3365 bool is_sibling_call;
3367 HARD_REG_SET defs_generated;
3369 CLEAR_HARD_REG_SET (defs_generated);
3370 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3371 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3373 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3375 if (i == STACK_POINTER_REGNUM)
3376 /* The stack ptr is used (honorarily) by a CALL insn. */
3377 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3378 NULL, bb, insn_info, DF_REF_REG_USE,
3379 DF_REF_CALL_STACK_USAGE | flags);
3380 else if (global_regs[i])
3382 /* Calls to const functions cannot access any global registers and
3383 calls to pure functions cannot set them. All other calls may
3384 reference any of the global registers, so they are recorded as
3386 if (!RTL_CONST_CALL_P (insn_info->insn))
3388 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3389 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3390 if (!RTL_PURE_CALL_P (insn_info->insn))
3391 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3392 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3395 else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
3396 /* no clobbers for regs that are the result of the call */
3397 && !TEST_HARD_REG_BIT (defs_generated, i)
3398 && (!is_sibling_call
3399 || !bitmap_bit_p (df->exit_block_uses, i)
3400 || refers_to_regno_p (i, i+1,
3401 crtl->return_rtx, NULL)))
3402 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3403 NULL, bb, insn_info, DF_REF_REG_DEF,
3404 DF_REF_MAY_CLOBBER | flags);
3407 /* Record the registers used to pass arguments, and explicitly
3408 noted as clobbered. */
3409 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3410 note = XEXP (note, 1))
3412 if (GET_CODE (XEXP (note, 0)) == USE)
3413 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3414 DF_REF_REG_USE, bb, insn_info, flags);
3415 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3417 if (REG_P (XEXP (XEXP (note, 0), 0)))
3419 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3420 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3421 df_defs_record (collection_rec, XEXP (note, 0), bb,
3425 df_uses_record (collection_rec, &XEXP (note, 0),
3426 DF_REF_REG_USE, bb, insn_info, flags);
3433 /* Collect all refs in the INSN. This function is free of any
3434 side-effect - it will create and return a lists of df_ref's in the
3435 COLLECTION_REC without putting those refs into existing ref chains
3439 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3440 basic_block bb, struct df_insn_info *insn_info)
3443 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3445 /* Clear out the collection record. */
3446 collection_rec->def_vec.truncate (0);
3447 collection_rec->use_vec.truncate (0);
3448 collection_rec->eq_use_vec.truncate (0);
3449 collection_rec->mw_vec.truncate (0);
3451 /* Process REG_EQUIV/REG_EQUAL notes. */
3452 for (note = REG_NOTES (insn_info->insn); note;
3453 note = XEXP (note, 1))
3455 switch (REG_NOTE_KIND (note))
3459 df_uses_record (collection_rec,
3460 &XEXP (note, 0), DF_REF_REG_USE,
3461 bb, insn_info, DF_REF_IN_NOTE);
3463 case REG_NON_LOCAL_GOTO:
3464 /* The frame ptr is used by a non-local goto. */
3465 df_ref_record (DF_REF_BASE, collection_rec,
3466 regno_reg_rtx[FRAME_POINTER_REGNUM],
3467 NULL, bb, insn_info,
3469 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3470 df_ref_record (DF_REF_BASE, collection_rec,
3471 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3472 NULL, bb, insn_info,
3481 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3482 uses from CALL_INSN_FUNCTION_USAGE. */
3483 if (CALL_P (insn_info->insn))
3484 df_get_call_refs (collection_rec, bb, insn_info,
3485 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3487 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3488 that a qsort on the defs is unnecessary in most cases. */
3489 df_defs_record (collection_rec,
3490 PATTERN (insn_info->insn), bb, insn_info, 0);
3492 /* Record the register uses. */
3493 df_uses_record (collection_rec,
3494 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3496 /* DF_REF_CONDITIONAL needs corresponding USES. */
3498 df_get_conditional_uses (collection_rec);
3500 df_canonize_collection_rec (collection_rec);
3503 /* Recompute the luids for the insns in BB. */
3506 df_recompute_luids (basic_block bb)
3511 df_grow_insn_info ();
3513 /* Scan the block an insn at a time from beginning to end. */
3514 FOR_BB_INSNS (bb, insn)
3516 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3517 /* Inserting labels does not always trigger the incremental
3521 gcc_assert (!INSN_P (insn));
3522 insn_info = df_insn_create_insn_record (insn);
3525 DF_INSN_INFO_LUID (insn_info) = luid;
3532 /* Collect all artificial refs at the block level for BB and add them
3533 to COLLECTION_REC. */
3536 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3538 collection_rec->def_vec.truncate (0);
3539 collection_rec->use_vec.truncate (0);
3540 collection_rec->eq_use_vec.truncate (0);
3541 collection_rec->mw_vec.truncate (0);
3543 if (bb->index == ENTRY_BLOCK)
3545 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3548 else if (bb->index == EXIT_BLOCK)
3550 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3554 #ifdef EH_RETURN_DATA_REGNO
3555 if (bb_has_eh_pred (bb))
3558 /* Mark the registers that will contain data for the handler. */
3561 unsigned regno = EH_RETURN_DATA_REGNO (i);
3562 if (regno == INVALID_REGNUM)
3564 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3565 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3570 /* Add the hard_frame_pointer if this block is the target of a
3572 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3573 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3574 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3576 /* Add the artificial uses. */
3577 if (bb->index >= NUM_FIXED_BLOCKS)
3581 bitmap au = bb_has_eh_pred (bb)
3582 ? &df->eh_block_artificial_uses
3583 : &df->regular_block_artificial_uses;
3585 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3587 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3588 bb, NULL, DF_REF_REG_USE, 0);
3592 df_canonize_collection_rec (collection_rec);
3596 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3599 df_bb_refs_record (int bb_index, bool scan_insns)
3601 basic_block bb = BASIC_BLOCK (bb_index);
3604 struct df_collection_rec collection_rec;
3609 df_grow_bb_info (df_scan);
3610 vec_stack_alloc (df_ref, collection_rec.def_vec, 128);
3611 vec_stack_alloc (df_ref, collection_rec.use_vec, 32);
3612 vec_stack_alloc (df_ref, collection_rec.eq_use_vec, 32);
3613 vec_stack_alloc (df_mw_hardreg_ptr, collection_rec.mw_vec, 32);
3616 /* Scan the block an insn at a time from beginning to end. */
3617 FOR_BB_INSNS (bb, insn)
3619 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3620 gcc_assert (!insn_info);
3622 insn_info = df_insn_create_insn_record (insn);
3625 /* Record refs within INSN. */
3626 DF_INSN_INFO_LUID (insn_info) = luid++;
3627 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3628 df_refs_add_to_chains (&collection_rec, bb, insn);
3630 DF_INSN_INFO_LUID (insn_info) = luid;
3633 /* Other block level artificial refs */
3634 df_bb_refs_collect (&collection_rec, bb);
3635 df_refs_add_to_chains (&collection_rec, bb, NULL);
3637 collection_rec.def_vec.release ();
3638 collection_rec.use_vec.release ();
3639 collection_rec.eq_use_vec.release ();
3640 collection_rec.mw_vec.release ();
3642 /* Now that the block has been processed, set the block as dirty so
3643 LR and LIVE will get it processed. */
3644 df_set_bb_dirty (bb);
3648 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3652 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3658 bitmap_clear (regular_block_artificial_uses);
3660 if (reload_completed)
3662 if (frame_pointer_needed)
3663 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3666 /* Before reload, there are a few registers that must be forced
3667 live everywhere -- which might not already be the case for
3668 blocks within infinite loops. */
3670 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3672 /* Any reference to any pseudo before reload is a potential
3673 reference of the frame pointer. */
3674 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3676 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3677 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3680 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3681 /* Pseudos with argument area equivalences may require
3682 reloading via the argument pointer. */
3683 if (fixed_regs[ARG_POINTER_REGNUM])
3684 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3687 /* Any constant, or pseudo with constant equivalences, may
3688 require reloading from memory using the pic register. */
3689 if (picreg != INVALID_REGNUM
3690 && fixed_regs[picreg])
3691 bitmap_set_bit (regular_block_artificial_uses, picreg);
3693 /* The all-important stack pointer must always be live. */
3694 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3697 /* EH_USES registers are used:
3698 1) at all insns that might throw (calls or with -fnon-call-exceptions
3701 3) to support backtraces and/or debugging, anywhere between their
3702 initialization and where they the saved registers are restored
3703 from them, including the cases where we don't reach the epilogue
3704 (noreturn call or infinite loop). */
3705 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3707 bitmap_set_bit (regular_block_artificial_uses, i);
3712 /* Get the artificial use set for an eh block. */
3715 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3717 bitmap_clear (eh_block_artificial_uses);
3719 /* The following code (down through the arg_pointer setting APPEARS
3720 to be necessary because there is nothing that actually
3721 describes what the exception handling code may actually need
3723 if (reload_completed)
3725 if (frame_pointer_needed)
3727 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3728 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3729 bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3732 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3733 if (fixed_regs[ARG_POINTER_REGNUM])
3734 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3741 /*----------------------------------------------------------------------------
3742 Specialized hard register scanning functions.
3743 ----------------------------------------------------------------------------*/
3746 /* Mark a register in SET. Hard registers in large modes get all
3747 of their component registers set as well. */
3750 df_mark_reg (rtx reg, void *vset)
3752 bitmap set = (bitmap) vset;
3753 int regno = REGNO (reg);
3755 gcc_assert (GET_MODE (reg) != BLKmode);
3757 if (regno < FIRST_PSEUDO_REGISTER)
3759 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3760 bitmap_set_range (set, regno, n);
3763 bitmap_set_bit (set, regno);
3767 /* Set the bit for regs that are considered being defined at the entry. */
3770 df_get_entry_block_def_set (bitmap entry_block_defs)
3775 bitmap_clear (entry_block_defs);
3777 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3780 bitmap_set_bit (entry_block_defs, i);
3781 if (FUNCTION_ARG_REGNO_P (i))
3782 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3785 /* The always important stack pointer. */
3786 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3788 /* Once the prologue has been generated, all of these registers
3789 should just show up in the first regular block. */
3790 if (HAVE_prologue && epilogue_completed)
3792 /* Defs for the callee saved registers are inserted so that the
3793 pushes have some defining location. */
3794 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3795 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3796 bitmap_set_bit (entry_block_defs, i);
3799 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3801 bitmap_set_bit (entry_block_defs, REGNO (r));
3803 /* If the function has an incoming STATIC_CHAIN, it has to show up
3804 in the entry def set. */
3805 r = targetm.calls.static_chain (current_function_decl, true);
3807 bitmap_set_bit (entry_block_defs, REGNO (r));
3809 if ((!reload_completed) || frame_pointer_needed)
3811 /* Any reference to any pseudo before reload is a potential
3812 reference of the frame pointer. */
3813 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3814 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3815 /* If they are different, also mark the hard frame pointer as live. */
3816 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3817 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3821 /* These registers are live everywhere. */
3822 if (!reload_completed)
3824 #ifdef PIC_OFFSET_TABLE_REGNUM
3825 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3828 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3829 /* Pseudos with argument area equivalences may require
3830 reloading via the argument pointer. */
3831 if (fixed_regs[ARG_POINTER_REGNUM])
3832 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3835 #ifdef PIC_OFFSET_TABLE_REGNUM
3836 /* Any constant, or pseudo with constant equivalences, may
3837 require reloading from memory using the pic register. */
3838 if (picreg != INVALID_REGNUM
3839 && fixed_regs[picreg])
3840 bitmap_set_bit (entry_block_defs, picreg);
3844 #ifdef INCOMING_RETURN_ADDR_RTX
3845 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3846 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3849 targetm.extra_live_on_entry (entry_block_defs);
3853 /* Return the (conservative) set of hard registers that are defined on
3854 entry to the function.
3855 It uses df->entry_block_defs to determine which register
3856 reference to include. */
3859 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3860 bitmap entry_block_defs)
3865 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3867 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3868 ENTRY_BLOCK_PTR, NULL, DF_REF_REG_DEF, 0);
3871 df_canonize_collection_rec (collection_rec);
3875 /* Record the (conservative) set of hard registers that are defined on
3876 entry to the function. */
3879 df_record_entry_block_defs (bitmap entry_block_defs)
3881 struct df_collection_rec collection_rec;
3882 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3883 vec_stack_alloc (df_ref, collection_rec.def_vec, FIRST_PSEUDO_REGISTER);
3884 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3886 /* Process bb_refs chain */
3887 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (ENTRY_BLOCK), NULL);
3888 collection_rec.def_vec.release ();
3892 /* Update the defs in the entry block. */
3895 df_update_entry_block_defs (void)
3898 bool changed = false;
3900 bitmap_initialize (&refs, &df_bitmap_obstack);
3901 df_get_entry_block_def_set (&refs);
3902 if (df->entry_block_defs)
3904 if (!bitmap_equal_p (df->entry_block_defs, &refs))
3906 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3907 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3908 df_ref_chain_delete (bb_info->artificial_defs);
3909 bb_info->artificial_defs = NULL;
3915 struct df_scan_problem_data *problem_data
3916 = (struct df_scan_problem_data *) df_scan->problem_data;
3918 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3924 df_record_entry_block_defs (&refs);
3925 bitmap_copy (df->entry_block_defs, &refs);
3926 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
3928 bitmap_clear (&refs);
3932 /* Set the bit for regs that are considered being used at the exit. */
3935 df_get_exit_block_use_set (bitmap exit_block_uses)
3938 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3940 bitmap_clear (exit_block_uses);
3942 /* Stack pointer is always live at the exit. */
3943 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3945 /* Mark the frame pointer if needed at the end of the function.
3946 If we end up eliminating it, it will be removed from the live
3947 list of each basic block by reload. */
3949 if ((!reload_completed) || frame_pointer_needed)
3951 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3952 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3953 /* If they are different, also mark the hard frame pointer as live. */
3954 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3955 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3959 /* Many architectures have a GP register even without flag_pic.
3960 Assume the pic register is not in use, or will be handled by
3961 other means, if it is not fixed. */
3962 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3963 && picreg != INVALID_REGNUM
3964 && fixed_regs[picreg])
3965 bitmap_set_bit (exit_block_uses, picreg);
3967 /* Mark all global registers, and all registers used by the
3968 epilogue as being live at the end of the function since they
3969 may be referenced by our caller. */
3970 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3971 if (global_regs[i] || EPILOGUE_USES (i))
3972 bitmap_set_bit (exit_block_uses, i);
3974 if (HAVE_epilogue && epilogue_completed)
3976 /* Mark all call-saved registers that we actually used. */
3977 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3978 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3979 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3980 bitmap_set_bit (exit_block_uses, i);
3983 #ifdef EH_RETURN_DATA_REGNO
3984 /* Mark the registers that will contain data for the handler. */
3985 if (reload_completed && crtl->calls_eh_return)
3988 unsigned regno = EH_RETURN_DATA_REGNO (i);
3989 if (regno == INVALID_REGNUM)
3991 bitmap_set_bit (exit_block_uses, regno);
3995 #ifdef EH_RETURN_STACKADJ_RTX
3996 if ((!HAVE_epilogue || ! epilogue_completed)
3997 && crtl->calls_eh_return)
3999 rtx tmp = EH_RETURN_STACKADJ_RTX;
4000 if (tmp && REG_P (tmp))
4001 df_mark_reg (tmp, exit_block_uses);
4005 #ifdef EH_RETURN_HANDLER_RTX
4006 if ((!HAVE_epilogue || ! epilogue_completed)
4007 && crtl->calls_eh_return)
4009 rtx tmp = EH_RETURN_HANDLER_RTX;
4010 if (tmp && REG_P (tmp))
4011 df_mark_reg (tmp, exit_block_uses);
4015 /* Mark function return value. */
4016 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
4020 /* Return the refs of hard registers that are used in the exit block.
4021 It uses df->exit_block_uses to determine register to include. */
4024 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
4029 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
4030 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
4031 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
4033 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4034 /* It is deliberate that this is not put in the exit block uses but
4035 I do not know why. */
4036 if (reload_completed
4037 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
4038 && bb_has_eh_pred (EXIT_BLOCK_PTR)
4039 && fixed_regs[ARG_POINTER_REGNUM])
4040 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
4041 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
4044 df_canonize_collection_rec (collection_rec);
4048 /* Record the set of hard registers that are used in the exit block.
4049 It uses df->exit_block_uses to determine which bit to include. */
4052 df_record_exit_block_uses (bitmap exit_block_uses)
4054 struct df_collection_rec collection_rec;
4055 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4056 vec_stack_alloc (df_ref, collection_rec.use_vec, FIRST_PSEUDO_REGISTER);
4057 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
4059 /* Process bb_refs chain */
4060 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (EXIT_BLOCK), NULL);
4061 collection_rec.use_vec.release ();
4065 /* Update the uses in the exit block. */
4068 df_update_exit_block_uses (void)
4071 bool changed = false;
4073 bitmap_initialize (&refs, &df_bitmap_obstack);
4074 df_get_exit_block_use_set (&refs);
4075 if (df->exit_block_uses)
4077 if (!bitmap_equal_p (df->exit_block_uses, &refs))
4079 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
4080 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
4081 df_ref_chain_delete (bb_info->artificial_uses);
4082 bb_info->artificial_uses = NULL;
4088 struct df_scan_problem_data *problem_data
4089 = (struct df_scan_problem_data *) df_scan->problem_data;
4091 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
4097 df_record_exit_block_uses (&refs);
4098 bitmap_copy (df->exit_block_uses,& refs);
4099 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
4101 bitmap_clear (&refs);
4104 static bool initialized = false;
4107 /* Initialize some platform specific structures. */
4110 df_hard_reg_init (void)
4112 #ifdef ELIMINABLE_REGS
4114 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
4119 /* Record which registers will be eliminated. We use this in
4121 CLEAR_HARD_REG_SET (elim_reg_set);
4123 #ifdef ELIMINABLE_REGS
4124 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
4125 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
4127 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
4134 /* Recompute the parts of scanning that are based on regs_ever_live
4135 because something changed in that array. */
4138 df_update_entry_exit_and_calls (void)
4142 df_update_entry_block_defs ();
4143 df_update_exit_block_uses ();
4145 /* The call insns need to be rescanned because there may be changes
4146 in the set of registers clobbered across the call. */
4150 FOR_BB_INSNS (bb, insn)
4152 if (INSN_P (insn) && CALL_P (insn))
4153 df_insn_rescan (insn);
4159 /* Return true if hard REG is actually used in the some instruction.
4160 There are a fair number of conditions that affect the setting of
4161 this array. See the comment in df.h for df->hard_regs_live_count
4162 for the conditions that this array is set. */
4165 df_hard_reg_used_p (unsigned int reg)
4167 return df->hard_regs_live_count[reg] != 0;
4171 /* A count of the number of times REG is actually used in the some
4172 instruction. There are a fair number of conditions that affect the
4173 setting of this array. See the comment in df.h for
4174 df->hard_regs_live_count for the conditions that this array is
4179 df_hard_reg_used_count (unsigned int reg)
4181 return df->hard_regs_live_count[reg];
4185 /* Get the value of regs_ever_live[REGNO]. */
4188 df_regs_ever_live_p (unsigned int regno)
4190 return regs_ever_live[regno];
4194 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
4195 to change, schedule that change for the next update. */
4198 df_set_regs_ever_live (unsigned int regno, bool value)
4200 if (regs_ever_live[regno] == value)
4203 regs_ever_live[regno] = value;
4205 df->redo_entry_and_exit = true;
4209 /* Compute "regs_ever_live" information from the underlying df
4210 information. Set the vector to all false if RESET. */
4213 df_compute_regs_ever_live (bool reset)
4216 bool changed = df->redo_entry_and_exit;
4219 memset (regs_ever_live, 0, sizeof (regs_ever_live));
4221 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4222 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
4224 regs_ever_live[i] = true;
4228 df_update_entry_exit_and_calls ();
4229 df->redo_entry_and_exit = false;
4233 /*----------------------------------------------------------------------------
4234 Dataflow ref information verification functions.
4236 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
4237 df_reg_chain_verify_unmarked (refs)
4238 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
4239 df_mws_verify (mw*, mw*, bool)
4240 df_insn_refs_verify (collection_rec, bb, insn, bool)
4241 df_bb_refs_verify (bb, refs, bool)
4243 df_exit_block_bitmap_verify (bool)
4244 df_entry_block_bitmap_verify (bool)
4246 ----------------------------------------------------------------------------*/
4249 /* Mark all refs in the reg chain. Verify that all of the registers
4250 are in the correct chain. */
4253 df_reg_chain_mark (df_ref refs, unsigned int regno,
4254 bool is_def, bool is_eq_use)
4256 unsigned int count = 0;
4258 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4260 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4262 /* If there are no def-use or use-def chains, make sure that all
4263 of the chains are clear. */
4265 gcc_assert (!DF_REF_CHAIN (ref));
4267 /* Check to make sure the ref is in the correct chain. */
4268 gcc_assert (DF_REF_REGNO (ref) == regno);
4270 gcc_assert (DF_REF_REG_DEF_P (ref));
4272 gcc_assert (!DF_REF_REG_DEF_P (ref));
4275 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4277 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4279 if (DF_REF_NEXT_REG (ref))
4280 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
4282 DF_REF_REG_MARK (ref);
4288 /* Verify that all of the registers in the chain are unmarked. */
4291 df_reg_chain_verify_unmarked (df_ref refs)
4294 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4295 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4299 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4302 df_refs_verify (vec<df_ref, va_stack> new_rec, df_ref *old_rec,
4308 FOR_EACH_VEC_ELT (new_rec, ix, new_ref)
4310 if (*old_rec == NULL || !df_ref_equal_p (new_ref, *old_rec))
4318 /* Abort if fail is called from the function level verifier. If
4319 that is the context, mark this reg as being seem. */
4322 gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
4323 DF_REF_REG_UNMARK (*old_rec);
4330 gcc_assert (*old_rec == NULL);
4332 return *old_rec == NULL;
4337 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4340 df_mws_verify (vec<df_mw_hardreg_ptr, va_stack> new_rec,
4341 struct df_mw_hardreg **old_rec,
4345 struct df_mw_hardreg *new_reg;
4347 FOR_EACH_VEC_ELT (new_rec, ix, new_reg)
4349 if (*old_rec == NULL || !df_mw_equal_p (new_reg, *old_rec))
4360 gcc_assert (*old_rec == NULL);
4362 return *old_rec == NULL;
4367 /* Return true if the existing insn refs information is complete and
4368 correct. Otherwise (i.e. if there's any missing or extra refs),
4369 return the correct df_ref chain in REFS_RETURN.
4371 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4372 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4373 verification mode instead of the whole function, so unmark
4376 If ABORT_IF_FAIL is set, this function never returns false. */
4379 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4384 bool ret1, ret2, ret3, ret4;
4385 unsigned int uid = INSN_UID (insn);
4386 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4388 df_insn_refs_collect (collection_rec, bb, insn_info);
4390 if (!DF_INSN_UID_DEFS (uid))
4392 /* The insn_rec was created but it was never filled out. */
4399 /* Unfortunately we cannot opt out early if one of these is not
4400 right because the marks will not get cleared. */
4401 ret1 = df_refs_verify (collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4403 ret2 = df_refs_verify (collection_rec->use_vec, DF_INSN_UID_USES (uid),
4405 ret3 = df_refs_verify (collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4407 ret4 = df_mws_verify (collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4409 return (ret1 && ret2 && ret3 && ret4);
4413 /* Return true if all refs in the basic block are correct and complete.
4414 Due to df_ref_chain_verify, it will cause all refs
4415 that are verified to have DF_REF_MARK bit set. */
4418 df_bb_verify (basic_block bb)
4421 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4422 struct df_collection_rec collection_rec;
4424 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4425 vec_stack_alloc (df_ref, collection_rec.def_vec, 128);
4426 vec_stack_alloc (df_ref, collection_rec.use_vec, 32);
4427 vec_stack_alloc (df_ref, collection_rec.eq_use_vec, 32);
4428 vec_stack_alloc (df_mw_hardreg_ptr, collection_rec.mw_vec, 32);
4430 gcc_assert (bb_info);
4432 /* Scan the block, one insn at a time, from beginning to end. */
4433 FOR_BB_INSNS_REVERSE (bb, insn)
4437 df_insn_refs_verify (&collection_rec, bb, insn, true);
4438 df_free_collection_rec (&collection_rec);
4441 /* Do the artificial defs and uses. */
4442 df_bb_refs_collect (&collection_rec, bb);
4443 df_refs_verify (collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4444 df_refs_verify (collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4445 df_free_collection_rec (&collection_rec);
4451 /* Returns true if the entry block has correct and complete df_ref set.
4452 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4455 df_entry_block_bitmap_verify (bool abort_if_fail)
4457 bitmap_head entry_block_defs;
4460 bitmap_initialize (&entry_block_defs, &df_bitmap_obstack);
4461 df_get_entry_block_def_set (&entry_block_defs);
4463 is_eq = bitmap_equal_p (&entry_block_defs, df->entry_block_defs);
4465 if (!is_eq && abort_if_fail)
4467 fprintf (stderr, "entry_block_defs = ");
4468 df_print_regset (stderr, &entry_block_defs);
4469 fprintf (stderr, "df->entry_block_defs = ");
4470 df_print_regset (stderr, df->entry_block_defs);
4474 bitmap_clear (&entry_block_defs);
4480 /* Returns true if the exit block has correct and complete df_ref set.
4481 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4484 df_exit_block_bitmap_verify (bool abort_if_fail)
4486 bitmap_head exit_block_uses;
4489 bitmap_initialize (&exit_block_uses, &df_bitmap_obstack);
4490 df_get_exit_block_use_set (&exit_block_uses);
4492 is_eq = bitmap_equal_p (&exit_block_uses, df->exit_block_uses);
4494 if (!is_eq && abort_if_fail)
4496 fprintf (stderr, "exit_block_uses = ");
4497 df_print_regset (stderr, &exit_block_uses);
4498 fprintf (stderr, "df->exit_block_uses = ");
4499 df_print_regset (stderr, df->exit_block_uses);
4503 bitmap_clear (&exit_block_uses);
4509 /* Return true if df_ref information for all insns in all blocks are
4510 correct and complete. */
4513 df_scan_verify (void)
4517 bitmap_head regular_block_artificial_uses;
4518 bitmap_head eh_block_artificial_uses;
4523 /* Verification is a 4 step process. */
4525 /* (1) All of the refs are marked by going through the reg chains. */
4526 for (i = 0; i < DF_REG_SIZE (df); i++)
4528 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4529 == DF_REG_DEF_COUNT(i));
4530 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4531 == DF_REG_USE_COUNT(i));
4532 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4533 == DF_REG_EQ_USE_COUNT(i));
4536 /* (2) There are various bitmaps whose value may change over the
4537 course of the compilation. This step recomputes them to make
4538 sure that they have not slipped out of date. */
4539 bitmap_initialize (®ular_block_artificial_uses, &df_bitmap_obstack);
4540 bitmap_initialize (&eh_block_artificial_uses, &df_bitmap_obstack);
4542 df_get_regular_block_artificial_uses (®ular_block_artificial_uses);
4543 df_get_eh_block_artificial_uses (&eh_block_artificial_uses);
4545 bitmap_ior_into (&eh_block_artificial_uses,
4546 ®ular_block_artificial_uses);
4548 /* Check artificial_uses bitmaps didn't change. */
4549 gcc_assert (bitmap_equal_p (®ular_block_artificial_uses,
4550 &df->regular_block_artificial_uses));
4551 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses,
4552 &df->eh_block_artificial_uses));
4554 bitmap_clear (®ular_block_artificial_uses);
4555 bitmap_clear (&eh_block_artificial_uses);
4557 /* Verify entry block and exit block. These only verify the bitmaps,
4558 the refs are verified in df_bb_verify. */
4559 df_entry_block_bitmap_verify (true);
4560 df_exit_block_bitmap_verify (true);
4562 /* (3) All of the insns in all of the blocks are traversed and the
4563 marks are cleared both in the artificial refs attached to the
4564 blocks and the real refs inside the insns. It is a failure to
4565 clear a mark that has not been set as this means that the ref in
4566 the block or insn was not in the reg chain. */
4571 /* (4) See if all reg chains are traversed a second time. This time
4572 a check is made that the marks are clear. A set mark would be a
4573 from a reg that is not in any insn or basic block. */
4575 for (i = 0; i < DF_REG_SIZE (df); i++)
4577 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4578 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4579 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));