1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 2008 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "alloc-pool.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
45 #include "target-def.h"
47 #include "tree-pass.h"
50 #define HAVE_epilogue 0
53 #define HAVE_prologue 0
55 #ifndef HAVE_sibcall_epilogue
56 #define HAVE_sibcall_epilogue 0
60 #define EPILOGUE_USES(REGNO) 0
63 /* The following two macros free the vecs that hold either the refs or
64 the mw refs. They are a little tricky because the vec has 0
65 elements is special and is not to be freed. */
66 #define df_scan_free_ref_vec(V) \
72 #define df_scan_free_mws_vec(V) \
78 /* The bitmap_obstack is used to hold some static variables that
79 should not be reset after each function is compiled. */
81 static bitmap_obstack persistent_obstack;
83 /* The set of hard registers in eliminables[i].from. */
85 static HARD_REG_SET elim_reg_set;
87 /* This is a bitmap copy of regs_invalidated_by_call so that we can
88 easily add it into bitmaps, etc. */
90 bitmap df_invalidated_by_call = NULL;
92 /* Initialize ur_in and ur_out as if all hard registers were partially
95 struct df_collection_rec
98 unsigned int next_def;
100 unsigned int next_use;
102 unsigned int next_eq_use;
103 struct df_mw_hardreg **mw_vec;
104 unsigned int next_mw;
107 static df_ref df_null_ref_rec[1];
108 static struct df_mw_hardreg * df_null_mw_rec[1];
110 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
112 basic_block, struct df_insn_info *,
113 enum df_ref_type, enum df_ref_flags,
114 int, int, enum machine_mode);
115 static void df_def_record_1 (struct df_collection_rec *, rtx,
116 basic_block, struct df_insn_info *,
118 static void df_defs_record (struct df_collection_rec *, rtx,
119 basic_block, struct df_insn_info *,
121 static void df_uses_record (enum df_ref_class, struct df_collection_rec *,
122 rtx *, enum df_ref_type,
123 basic_block, struct df_insn_info *,
125 int, int, enum machine_mode);
127 static df_ref df_ref_create_structure (enum df_ref_class,
128 struct df_collection_rec *, rtx, rtx *,
129 basic_block, struct df_insn_info *,
130 enum df_ref_type, enum df_ref_flags,
131 int, int, enum machine_mode);
133 static void df_insn_refs_collect (struct df_collection_rec*,
134 basic_block, struct df_insn_info *);
135 static void df_canonize_collection_rec (struct df_collection_rec *);
137 static void df_get_regular_block_artificial_uses (bitmap);
138 static void df_get_eh_block_artificial_uses (bitmap);
140 static void df_record_entry_block_defs (bitmap);
141 static void df_record_exit_block_uses (bitmap);
142 static void df_get_exit_block_use_set (bitmap);
143 static void df_get_entry_block_def_set (bitmap);
144 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
145 static void df_ref_chain_delete_du_chain (df_ref *);
146 static void df_ref_chain_delete (df_ref *);
148 static void df_refs_add_to_chains (struct df_collection_rec *,
151 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block, rtx, bool);
152 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
153 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
154 static void df_install_ref (df_ref, struct df_reg_info *,
155 struct df_ref_info *, bool);
157 static int df_ref_compare (const void *, const void *);
158 static int df_mw_compare (const void *, const void *);
160 /* Indexed by hardware reg number, is true if that register is ever
161 used in the current function.
163 In df-scan.c, this is set up to record the hard regs used
164 explicitly. Reload adds in the hard regs used for holding pseudo
165 regs. Final uses it to generate the code in the function prologue
166 and epilogue to save and restore registers as needed. */
168 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
170 /*----------------------------------------------------------------------------
171 SCANNING DATAFLOW PROBLEM
173 There are several ways in which scanning looks just like the other
174 dataflow problems. It shares the all the mechanisms for local info
175 as well as basic block info. Where it differs is when and how often
176 it gets run. It also has no need for the iterative solver.
177 ----------------------------------------------------------------------------*/
179 /* Problem data for the scanning dataflow function. */
180 struct df_scan_problem_data
182 alloc_pool ref_base_pool;
183 alloc_pool ref_artificial_pool;
184 alloc_pool ref_regular_pool;
185 alloc_pool ref_extract_pool;
186 alloc_pool insn_pool;
188 alloc_pool mw_reg_pool;
189 bitmap_obstack reg_bitmaps;
190 bitmap_obstack insn_bitmaps;
193 typedef struct df_scan_bb_info *df_scan_bb_info_t;
196 /* Internal function to shut down the scanning problem. */
198 df_scan_free_internal (void)
200 struct df_scan_problem_data *problem_data
201 = (struct df_scan_problem_data *) df_scan->problem_data;
205 /* The vectors that hold the refs are not pool allocated because
206 they come in many sizes. This makes them impossible to delete
208 for (i = 0; i < DF_INSN_SIZE(); i++)
210 struct df_insn_info *insn_info = DF_INSN_UID_GET(i);
211 /* Skip the insns that have no insn_info or have been
215 df_scan_free_ref_vec (insn_info->defs);
216 df_scan_free_ref_vec (insn_info->uses);
217 df_scan_free_ref_vec (insn_info->eq_uses);
218 df_scan_free_mws_vec (insn_info->mw_hardregs);
224 unsigned int bb_index = bb->index;
225 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
228 df_scan_free_ref_vec (bb_info->artificial_defs);
229 df_scan_free_ref_vec (bb_info->artificial_uses);
233 free (df->def_info.refs);
234 free (df->def_info.begin);
235 free (df->def_info.count);
236 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
238 free (df->use_info.refs);
239 free (df->use_info.begin);
240 free (df->use_info.count);
241 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
247 free (df->eq_use_regs);
248 df->eq_use_regs = NULL;
256 free (df_scan->block_info);
257 df_scan->block_info = NULL;
258 df_scan->block_info_size = 0;
260 BITMAP_FREE (df->hardware_regs_used);
261 BITMAP_FREE (df->regular_block_artificial_uses);
262 BITMAP_FREE (df->eh_block_artificial_uses);
263 BITMAP_FREE (df->entry_block_defs);
264 BITMAP_FREE (df->exit_block_uses);
265 BITMAP_FREE (df->insns_to_delete);
266 BITMAP_FREE (df->insns_to_rescan);
267 BITMAP_FREE (df->insns_to_notes_rescan);
269 free_alloc_pool (df_scan->block_pool);
270 free_alloc_pool (problem_data->ref_base_pool);
271 free_alloc_pool (problem_data->ref_artificial_pool);
272 free_alloc_pool (problem_data->ref_regular_pool);
273 free_alloc_pool (problem_data->ref_extract_pool);
274 free_alloc_pool (problem_data->insn_pool);
275 free_alloc_pool (problem_data->reg_pool);
276 free_alloc_pool (problem_data->mw_reg_pool);
277 bitmap_obstack_release (&problem_data->reg_bitmaps);
278 bitmap_obstack_release (&problem_data->insn_bitmaps);
279 free (df_scan->problem_data);
283 /* Set basic block info. */
286 df_scan_set_bb_info (unsigned int index,
287 struct df_scan_bb_info *bb_info)
289 gcc_assert (df_scan);
290 df_grow_bb_info (df_scan);
291 df_scan->block_info[index] = (void *) bb_info;
295 /* Free basic block info. */
298 df_scan_free_bb_info (basic_block bb, void *vbb_info)
300 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
301 unsigned int bb_index = bb->index;
305 FOR_BB_INSNS (bb, insn)
308 /* Record defs within INSN. */
309 df_insn_delete (bb, INSN_UID (insn));
312 if (bb_index < df_scan->block_info_size)
313 bb_info = df_scan_get_bb_info (bb_index);
315 /* Get rid of any artificial uses or defs. */
316 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
317 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
318 df_ref_chain_delete (bb_info->artificial_defs);
319 df_ref_chain_delete (bb_info->artificial_uses);
320 bb_info->artificial_defs = NULL;
321 bb_info->artificial_uses = NULL;
322 pool_free (df_scan->block_pool, bb_info);
327 /* Allocate the problem data for the scanning problem. This should be
328 called when the problem is created or when the entire function is to
331 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
333 struct df_scan_problem_data *problem_data;
334 unsigned int insn_num = get_max_uid () + 1;
335 unsigned int block_size = 400;
338 /* Given the number of pools, this is really faster than tearing
340 if (df_scan->problem_data)
341 df_scan_free_internal ();
344 = create_alloc_pool ("df_scan_block pool",
345 sizeof (struct df_scan_bb_info),
348 problem_data = XNEW (struct df_scan_problem_data);
349 df_scan->problem_data = problem_data;
350 df_scan->computed = true;
352 problem_data->ref_base_pool
353 = create_alloc_pool ("df_scan ref base",
354 sizeof (struct df_base_ref), block_size);
355 problem_data->ref_artificial_pool
356 = create_alloc_pool ("df_scan ref artificial",
357 sizeof (struct df_artificial_ref), block_size);
358 problem_data->ref_regular_pool
359 = create_alloc_pool ("df_scan ref regular",
360 sizeof (struct df_regular_ref), block_size);
361 problem_data->ref_extract_pool
362 = create_alloc_pool ("df_scan ref extract",
363 sizeof (struct df_extract_ref), block_size);
364 problem_data->insn_pool
365 = create_alloc_pool ("df_scan insn",
366 sizeof (struct df_insn_info), block_size);
367 problem_data->reg_pool
368 = create_alloc_pool ("df_scan reg",
369 sizeof (struct df_reg_info), block_size);
370 problem_data->mw_reg_pool
371 = create_alloc_pool ("df_scan mw_reg",
372 sizeof (struct df_mw_hardreg), block_size);
374 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
375 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
377 insn_num += insn_num / 4;
380 df_grow_insn_info ();
381 df_grow_bb_info (df_scan);
385 unsigned int bb_index = bb->index;
386 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
389 bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
390 df_scan_set_bb_info (bb_index, bb_info);
392 bb_info->artificial_defs = NULL;
393 bb_info->artificial_uses = NULL;
396 df->hardware_regs_used = BITMAP_ALLOC (&problem_data->reg_bitmaps);
397 df->regular_block_artificial_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
398 df->eh_block_artificial_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
399 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
400 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
401 df->insns_to_delete = BITMAP_ALLOC (&problem_data->insn_bitmaps);
402 df->insns_to_rescan = BITMAP_ALLOC (&problem_data->insn_bitmaps);
403 df->insns_to_notes_rescan = BITMAP_ALLOC (&problem_data->insn_bitmaps);
404 df_scan->optional_p = false;
408 /* Free all of the data associated with the scan problem. */
413 if (df_scan->problem_data)
414 df_scan_free_internal ();
416 if (df->blocks_to_analyze)
418 BITMAP_FREE (df->blocks_to_analyze);
419 df->blocks_to_analyze = NULL;
425 /* Dump the preamble for DF_SCAN dump. */
427 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
438 fprintf (file, ";; invalidated by call \t");
439 df_print_regset (file, df_invalidated_by_call);
440 fprintf (file, ";; hardware regs used \t");
441 df_print_regset (file, df->hardware_regs_used);
442 fprintf (file, ";; regular block artificial uses \t");
443 df_print_regset (file, df->regular_block_artificial_uses);
444 fprintf (file, ";; eh block artificial uses \t");
445 df_print_regset (file, df->eh_block_artificial_uses);
446 fprintf (file, ";; entry block defs \t");
447 df_print_regset (file, df->entry_block_defs);
448 fprintf (file, ";; exit block uses \t");
449 df_print_regset (file, df->exit_block_uses);
450 fprintf (file, ";; regs ever live \t");
451 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
452 if (df_regs_ever_live_p (i))
453 fprintf (file, " %d[%s]", i, reg_names[i]);
454 fprintf (file, "\n;; ref usage \t");
456 for (i = 0; i < (int)df->regs_inited; i++)
457 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
459 const char * sep = "";
461 fprintf (file, "r%d={", i);
462 if (DF_REG_DEF_COUNT (i))
464 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
466 dcount += DF_REG_DEF_COUNT (i);
468 if (DF_REG_USE_COUNT (i))
470 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
472 ucount += DF_REG_USE_COUNT (i);
474 if (DF_REG_EQ_USE_COUNT (i))
476 fprintf (file, "%s%dd", sep, DF_REG_EQ_USE_COUNT (i));
477 ecount += DF_REG_EQ_USE_COUNT (i);
479 fprintf (file, "} ");
483 FOR_BB_INSNS (bb, insn)
492 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de} in %d{%d regular + %d call} insns.\n",
493 dcount + ucount + ecount, dcount, ucount, ecount, icount + ccount, icount, ccount);
496 /* Dump the bb_info for a given basic block. */
498 df_scan_start_block (basic_block bb, FILE *file)
500 struct df_scan_bb_info *bb_info
501 = df_scan_get_bb_info (bb->index);
505 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
506 df_refs_chain_dump (bb_info->artificial_defs, true, file);
507 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
508 df_refs_chain_dump (bb_info->artificial_uses, true, file);
509 fprintf (file, "\n");
514 FOR_BB_INSNS (bb, insn)
516 df_insn_debug (insn, false, file);
521 static struct df_problem problem_SCAN =
523 DF_SCAN, /* Problem id. */
524 DF_NONE, /* Direction. */
525 df_scan_alloc, /* Allocate the problem specific data. */
526 NULL, /* Reset global information. */
527 df_scan_free_bb_info, /* Free basic block info. */
528 NULL, /* Local compute function. */
529 NULL, /* Init the solution specific data. */
530 NULL, /* Iterative solver. */
531 NULL, /* Confluence operator 0. */
532 NULL, /* Confluence operator n. */
533 NULL, /* Transfer function. */
534 NULL, /* Finalize function. */
535 df_scan_free, /* Free all of the problem information. */
536 NULL, /* Remove this problem from the stack of dataflow problems. */
537 df_scan_start_dump, /* Debugging. */
538 df_scan_start_block, /* Debugging start block. */
539 NULL, /* Debugging end block. */
540 NULL, /* Incremental solution verify start. */
541 NULL, /* Incremental solution verify end. */
542 NULL, /* Dependent problem. */
543 TV_DF_SCAN, /* Timing variable. */
544 false /* Reset blocks on dropping out of blocks_to_analyze. */
548 /* Create a new DATAFLOW instance and add it to an existing instance
549 of DF. The returned structure is what is used to get at the
553 df_scan_add_problem (void)
555 df_add_problem (&problem_SCAN);
559 /*----------------------------------------------------------------------------
560 Storage Allocation Utilities
561 ----------------------------------------------------------------------------*/
564 /* First, grow the reg_info information. If the current size is less than
565 the number of pseudos, grow to 25% more than the number of
568 Second, assure that all of the slots up to max_reg_num have been
569 filled with reg_info structures. */
572 df_grow_reg_info (void)
574 unsigned int max_reg = max_reg_num ();
575 unsigned int new_size = max_reg;
576 struct df_scan_problem_data *problem_data
577 = (struct df_scan_problem_data *) df_scan->problem_data;
580 if (df->regs_size < new_size)
582 new_size += new_size / 4;
583 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
584 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
585 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
587 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
588 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
589 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
590 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
591 df->regs_size = new_size;
594 for (i = df->regs_inited; i < max_reg; i++)
596 struct df_reg_info *reg_info;
598 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
599 memset (reg_info, 0, sizeof (struct df_reg_info));
600 df->def_regs[i] = reg_info;
601 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
602 memset (reg_info, 0, sizeof (struct df_reg_info));
603 df->use_regs[i] = reg_info;
604 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
605 memset (reg_info, 0, sizeof (struct df_reg_info));
606 df->eq_use_regs[i] = reg_info;
607 df->def_info.begin[i] = 0;
608 df->def_info.count[i] = 0;
609 df->use_info.begin[i] = 0;
610 df->use_info.count[i] = 0;
613 df->regs_inited = max_reg;
617 /* Grow the ref information. */
620 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
622 if (ref_info->refs_size < new_size)
624 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
625 memset (ref_info->refs + ref_info->refs_size, 0,
626 (new_size - ref_info->refs_size) *sizeof (df_ref));
627 ref_info->refs_size = new_size;
632 /* Check and grow the ref information if necessary. This routine
633 guarantees total_size + BITMAP_ADDEND amount of entries in refs
634 array. It updates ref_info->refs_size only and does not change
635 ref_info->total_size. */
638 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
639 unsigned bitmap_addend)
641 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
643 int new_size = ref_info->total_size + bitmap_addend;
644 new_size += ref_info->total_size / 4;
645 df_grow_ref_info (ref_info, new_size);
650 /* Grow the ref information. If the current size is less than the
651 number of instructions, grow to 25% more than the number of
655 df_grow_insn_info (void)
657 unsigned int new_size = get_max_uid () + 1;
658 if (DF_INSN_SIZE () < new_size)
660 new_size += new_size / 4;
661 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
662 memset (df->insns + df->insns_size, 0,
663 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
664 DF_INSN_SIZE () = new_size;
671 /*----------------------------------------------------------------------------
672 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
673 ----------------------------------------------------------------------------*/
675 /* Rescan all of the block_to_analyze or all of the blocks in the
676 function if df_set_blocks if blocks_to_analyze is NULL; */
679 df_scan_blocks (void)
683 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
684 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
686 df_get_regular_block_artificial_uses (df->regular_block_artificial_uses);
687 df_get_eh_block_artificial_uses (df->eh_block_artificial_uses);
689 bitmap_ior_into (df->eh_block_artificial_uses,
690 df->regular_block_artificial_uses);
692 /* ENTRY and EXIT blocks have special defs/uses. */
693 df_get_entry_block_def_set (df->entry_block_defs);
694 df_record_entry_block_defs (df->entry_block_defs);
695 df_get_exit_block_use_set (df->exit_block_uses);
696 df_record_exit_block_uses (df->exit_block_uses);
697 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
698 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
703 unsigned int bb_index = bb->index;
704 df_bb_refs_record (bb_index, true);
709 /* Create a new ref of type DF_REF_TYPE for register REG at address
710 LOC within INSN of BB. This function is only used externally.
712 If the REF_FLAGS field contain DF_REF_SIGN_EXTRACT or
713 DF_REF_ZERO_EXTRACT. WIDTH, OFFSET and MODE are used to access the
714 fields if they were constants. Otherwise they should be -1 if
715 those flags were set. */
718 df_ref_create (rtx reg, rtx *loc, rtx insn,
720 enum df_ref_type ref_type,
721 enum df_ref_flags ref_flags,
722 int width, int offset, enum machine_mode mode)
725 struct df_reg_info **reg_info;
726 struct df_ref_info *ref_info;
728 df_ref **ref_rec_ptr;
729 unsigned int count = 0;
731 enum df_ref_class cl;
735 /* You cannot hack artificial refs. */
738 if (width != -1 || offset != -1)
744 ref = df_ref_create_structure (cl, NULL, reg, loc, bb, DF_INSN_INFO_GET (insn),
746 width, offset, mode);
748 if (DF_REF_REG_DEF_P (ref))
750 reg_info = df->def_regs;
751 ref_info = &df->def_info;
752 ref_rec_ptr = &DF_INSN_DEFS (insn);
753 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
755 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
757 reg_info = df->eq_use_regs;
758 ref_info = &df->use_info;
759 ref_rec_ptr = &DF_INSN_EQ_USES (insn);
760 switch (ref_info->ref_order)
762 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
763 case DF_REF_ORDER_BY_REG_WITH_NOTES:
764 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
768 add_to_table = false;
774 reg_info = df->use_regs;
775 ref_info = &df->use_info;
776 ref_rec_ptr = &DF_INSN_USES (insn);
777 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
780 /* Do not add if ref is not in the right blocks. */
781 if (add_to_table && df->analyze_subset)
782 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
784 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
787 switch (ref_info->ref_order)
789 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
790 case DF_REF_ORDER_BY_REG_WITH_NOTES:
791 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
792 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
795 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
799 ref_rec = *ref_rec_ptr;
806 ref_rec = *ref_rec_ptr;
809 ref_rec = XRESIZEVEC (df_ref, ref_rec, count+2);
810 *ref_rec_ptr = ref_rec;
811 ref_rec[count] = ref;
812 ref_rec[count+1] = NULL;
813 qsort (ref_rec, count + 1, sizeof (df_ref), df_ref_compare);
817 df_ref *ref_rec = XNEWVEC (df_ref, 2);
820 *ref_rec_ptr = ref_rec;
826 fprintf (dump_file, "adding ref ");
827 df_ref_debug (ref, dump_file);
830 /* By adding the ref directly, df_insn_rescan my not find any
831 differences even though the block will have changed. So we need
832 to mark the block dirty ourselves. */
833 df_set_bb_dirty (bb);
840 /*----------------------------------------------------------------------------
841 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
842 ----------------------------------------------------------------------------*/
845 df_free_ref (df_ref ref)
847 struct df_scan_problem_data *problem_data
848 = (struct df_scan_problem_data *) df_scan->problem_data;
850 switch (DF_REF_CLASS (ref))
853 pool_free (problem_data->ref_base_pool, ref);
856 case DF_REF_ARTIFICIAL:
857 pool_free (problem_data->ref_artificial_pool, ref);
861 pool_free (problem_data->ref_regular_pool, ref);
865 pool_free (problem_data->ref_extract_pool, ref);
871 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
872 Also delete the def-use or use-def chain if it exists. */
875 df_reg_chain_unlink (df_ref ref)
877 df_ref next = DF_REF_NEXT_REG (ref);
878 df_ref prev = DF_REF_PREV_REG (ref);
879 int id = DF_REF_ID (ref);
880 struct df_reg_info *reg_info;
883 if (DF_REF_REG_DEF_P (ref))
885 int regno = DF_REF_REGNO (ref);
886 reg_info = DF_REG_DEF_GET (regno);
887 refs = df->def_info.refs;
891 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
893 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
894 switch (df->use_info.ref_order)
896 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
897 case DF_REF_ORDER_BY_REG_WITH_NOTES:
898 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
899 refs = df->use_info.refs;
907 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
908 refs = df->use_info.refs;
914 if (df->analyze_subset)
916 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
923 /* Delete any def-use or use-def chains that start here. It is
924 possible that there is trash in this field. This happens for
925 insns that have been deleted when rescanning has been deferred
926 and the chain problem has also been deleted. The chain tear down
927 code skips deleted insns. */
928 if (df_chain && DF_REF_CHAIN (ref))
929 df_chain_unlink (ref);
932 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
934 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
935 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
938 /* Unlink from the reg chain. If there is no prev, this is the
939 first of the list. If not, just join the next and prev. */
941 DF_REF_NEXT_REG (prev) = next;
944 gcc_assert (reg_info->reg_chain == ref);
945 reg_info->reg_chain = next;
948 DF_REF_PREV_REG (next) = prev;
954 /* Remove REF from VEC. */
957 df_ref_compress_rec (df_ref **vec_ptr, df_ref ref)
959 df_ref *vec = *vec_ptr;
963 while (*vec && *vec != ref)
975 *vec_ptr = df_null_ref_rec;
980 /* Unlink REF from all def-use/use-def chains, etc. */
983 df_ref_remove (df_ref ref)
988 fprintf (dump_file, "removing ref ");
989 df_ref_debug (ref, dump_file);
993 if (DF_REF_REG_DEF_P (ref))
995 if (DF_REF_IS_ARTIFICIAL (ref))
997 struct df_scan_bb_info *bb_info
998 = df_scan_get_bb_info (DF_REF_BBNO (ref));
999 df_ref_compress_rec (&bb_info->artificial_defs, ref);
1003 unsigned int uid = DF_REF_INSN_UID (ref);
1004 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
1005 df_ref_compress_rec (&insn_rec->defs, ref);
1010 if (DF_REF_IS_ARTIFICIAL (ref))
1012 struct df_scan_bb_info *bb_info
1013 = df_scan_get_bb_info (DF_REF_BBNO (ref));
1014 df_ref_compress_rec (&bb_info->artificial_uses, ref);
1018 unsigned int uid = DF_REF_INSN_UID (ref);
1019 struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
1021 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
1022 df_ref_compress_rec (&insn_rec->eq_uses, ref);
1024 df_ref_compress_rec (&insn_rec->uses, ref);
1028 /* By deleting the ref directly, df_insn_rescan my not find any
1029 differences even though the block will have changed. So we need
1030 to mark the block dirty ourselves. */
1031 df_set_bb_dirty (DF_REF_BB (ref));
1032 df_reg_chain_unlink (ref);
1036 /* Create the insn record for INSN. If there was one there, zero it
1039 struct df_insn_info *
1040 df_insn_create_insn_record (rtx insn)
1042 struct df_scan_problem_data *problem_data
1043 = (struct df_scan_problem_data *) df_scan->problem_data;
1044 struct df_insn_info *insn_rec;
1046 df_grow_insn_info ();
1047 insn_rec = DF_INSN_INFO_GET (insn);
1050 insn_rec = (struct df_insn_info *) pool_alloc (problem_data->insn_pool);
1051 DF_INSN_INFO_SET (insn, insn_rec);
1053 memset (insn_rec, 0, sizeof (struct df_insn_info));
1054 insn_rec->insn = insn;
1059 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
1062 df_ref_chain_delete_du_chain (df_ref *ref_rec)
1066 df_ref ref = *ref_rec;
1067 /* CHAIN is allocated by DF_CHAIN. So make sure to
1068 pass df_scan instance for the problem. */
1069 if (DF_REF_CHAIN (ref))
1070 df_chain_unlink (ref);
1076 /* Delete all refs in the ref chain. */
1079 df_ref_chain_delete (df_ref *ref_rec)
1081 df_ref *start = ref_rec;
1084 df_reg_chain_unlink (*ref_rec);
1088 /* If the list is empty, it has a special shared element that is not
1095 /* Delete the hardreg chain. */
1098 df_mw_hardreg_chain_delete (struct df_mw_hardreg **hardregs)
1100 struct df_scan_problem_data *problem_data;
1105 problem_data = (struct df_scan_problem_data *) df_scan->problem_data;
1109 pool_free (problem_data->mw_reg_pool, *hardregs);
1115 /* Delete all of the refs information from INSN. BB must be passed in
1116 except when called from df_process_deferred_rescans to mark the block
1120 df_insn_delete (basic_block bb, unsigned int uid)
1122 struct df_insn_info *insn_info = NULL;
1126 df_grow_bb_info (df_scan);
1127 df_grow_reg_info ();
1129 /* The block must be marked as dirty now, rather than later as in
1130 df_insn_rescan and df_notes_rescan because it may not be there at
1131 rescanning time and the mark would blow up. */
1133 df_set_bb_dirty (bb);
1135 insn_info = DF_INSN_UID_SAFE_GET (uid);
1137 /* The client has deferred rescanning. */
1138 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1142 bitmap_clear_bit (df->insns_to_rescan, uid);
1143 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1144 bitmap_set_bit (df->insns_to_delete, uid);
1147 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
1152 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
1154 bitmap_clear_bit (df->insns_to_delete, uid);
1155 bitmap_clear_bit (df->insns_to_rescan, uid);
1156 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1159 struct df_scan_problem_data *problem_data
1160 = (struct df_scan_problem_data *) df_scan->problem_data;
1162 /* In general, notes do not have the insn_info fields
1163 initialized. However, combine deletes insns by changing them
1164 to notes. How clever. So we cannot just check if it is a
1165 valid insn before short circuiting this code, we need to see
1166 if we actually initialized it. */
1167 if (insn_info->defs)
1169 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1173 df_ref_chain_delete_du_chain (insn_info->defs);
1174 df_ref_chain_delete_du_chain (insn_info->uses);
1175 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1178 df_ref_chain_delete (insn_info->defs);
1179 df_ref_chain_delete (insn_info->uses);
1180 df_ref_chain_delete (insn_info->eq_uses);
1182 pool_free (problem_data->insn_pool, insn_info);
1183 DF_INSN_UID_SET (uid, NULL);
1188 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
1191 df_free_collection_rec (struct df_collection_rec *collection_rec)
1193 struct df_scan_problem_data *problem_data
1194 = (struct df_scan_problem_data *) df_scan->problem_data;
1196 struct df_mw_hardreg **mw;
1198 if (collection_rec->def_vec)
1199 for (ref = collection_rec->def_vec; *ref; ref++)
1201 if (collection_rec->use_vec)
1202 for (ref = collection_rec->use_vec; *ref; ref++)
1204 if (collection_rec->eq_use_vec)
1205 for (ref = collection_rec->eq_use_vec; *ref; ref++)
1207 if (collection_rec->mw_vec)
1208 for (mw = collection_rec->mw_vec; *mw; mw++)
1209 pool_free (problem_data->mw_reg_pool, *mw);
1213 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1216 df_insn_rescan (rtx insn)
1218 unsigned int uid = INSN_UID (insn);
1219 struct df_insn_info *insn_info = NULL;
1220 basic_block bb = BLOCK_FOR_INSN (insn);
1221 struct df_collection_rec collection_rec;
1222 collection_rec.def_vec = XALLOCAVEC (df_ref, 1000);
1223 collection_rec.use_vec = XALLOCAVEC (df_ref, 1000);
1224 collection_rec.eq_use_vec = XALLOCAVEC (df_ref, 1000);
1225 collection_rec.mw_vec = XALLOCAVEC (struct df_mw_hardreg *, 100);
1227 if ((!df) || (!INSN_P (insn)))
1233 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1237 /* The client has disabled rescanning and plans to do it itself. */
1238 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1241 df_grow_bb_info (df_scan);
1242 df_grow_reg_info ();
1244 insn_info = DF_INSN_UID_SAFE_GET (uid);
1246 /* The client has deferred rescanning. */
1247 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1251 insn_info = df_insn_create_insn_record (insn);
1252 insn_info->defs = df_null_ref_rec;
1253 insn_info->uses = df_null_ref_rec;
1254 insn_info->eq_uses = df_null_ref_rec;
1255 insn_info->mw_hardregs = df_null_mw_rec;
1258 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1260 bitmap_clear_bit (df->insns_to_delete, uid);
1261 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1262 bitmap_set_bit (df->insns_to_rescan, INSN_UID (insn));
1266 bitmap_clear_bit (df->insns_to_delete, uid);
1267 bitmap_clear_bit (df->insns_to_rescan, uid);
1268 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1271 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1272 /* If there's no change, return false. */
1275 df_free_collection_rec (&collection_rec);
1277 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1281 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1283 /* There's change - we need to delete the existing info. */
1284 df_insn_delete (NULL, uid);
1285 df_insn_create_insn_record (insn);
1289 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1290 df_insn_refs_collect (&collection_rec, bb, insn_info);
1292 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1295 df_refs_add_to_chains (&collection_rec, bb, insn);
1296 df_set_bb_dirty (bb);
1301 /* Rescan all of the insns in the function. Note that the artificial
1302 uses and defs are not touched. This function will destroy def-se
1303 or use-def chains. */
1306 df_insn_rescan_all (void)
1308 bool no_insn_rescan = false;
1309 bool defer_insn_rescan = false;
1313 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1315 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1317 df_clear_flags (DF_NO_INSN_RESCAN);
1318 no_insn_rescan = true;
1321 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1323 df_clear_flags (DF_DEFER_INSN_RESCAN);
1324 defer_insn_rescan = true;
1327 bitmap_copy (tmp, df->insns_to_delete);
1328 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1330 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1332 df_insn_delete (NULL, uid);
1336 bitmap_clear (df->insns_to_delete);
1337 bitmap_clear (df->insns_to_rescan);
1338 bitmap_clear (df->insns_to_notes_rescan);
1343 FOR_BB_INSNS (bb, insn)
1345 df_insn_rescan (insn);
1350 df_set_flags (DF_NO_INSN_RESCAN);
1351 if (defer_insn_rescan)
1352 df_set_flags (DF_DEFER_INSN_RESCAN);
1356 /* Process all of the deferred rescans or deletions. */
1359 df_process_deferred_rescans (void)
1361 bool no_insn_rescan = false;
1362 bool defer_insn_rescan = false;
1365 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1367 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1369 df_clear_flags (DF_NO_INSN_RESCAN);
1370 no_insn_rescan = true;
1373 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1375 df_clear_flags (DF_DEFER_INSN_RESCAN);
1376 defer_insn_rescan = true;
1380 fprintf (dump_file, "starting the processing of deferred insns\n");
1382 bitmap_copy (tmp, df->insns_to_delete);
1383 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1385 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1387 df_insn_delete (NULL, uid);
1390 bitmap_copy (tmp, df->insns_to_rescan);
1391 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1393 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1395 df_insn_rescan (insn_info->insn);
1398 bitmap_copy (tmp, df->insns_to_notes_rescan);
1399 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1401 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1403 df_notes_rescan (insn_info->insn);
1407 fprintf (dump_file, "ending the processing of deferred insns\n");
1410 bitmap_clear (df->insns_to_delete);
1411 bitmap_clear (df->insns_to_rescan);
1412 bitmap_clear (df->insns_to_notes_rescan);
1415 df_set_flags (DF_NO_INSN_RESCAN);
1416 if (defer_insn_rescan)
1417 df_set_flags (DF_DEFER_INSN_RESCAN);
1419 /* If someone changed regs_ever_live during this pass, fix up the
1420 entry and exit blocks. */
1421 if (df->redo_entry_and_exit)
1423 df_update_entry_exit_and_calls ();
1424 df->redo_entry_and_exit = false;
1429 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1430 the uses if INCLUDE_USES. Include the eq_uses if
1434 df_count_refs (bool include_defs, bool include_uses,
1435 bool include_eq_uses)
1439 unsigned int m = df->regs_inited;
1441 for (regno = 0; regno < m; regno++)
1444 size += DF_REG_DEF_COUNT (regno);
1446 size += DF_REG_USE_COUNT (regno);
1447 if (include_eq_uses)
1448 size += DF_REG_EQ_USE_COUNT (regno);
1454 /* Take build ref table for either the uses or defs from the reg-use
1455 or reg-def chains. This version processes the refs in reg order
1456 which is likely to be best if processing the whole function. */
1459 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1462 bool include_eq_uses)
1464 unsigned int m = df->regs_inited;
1466 unsigned int offset = 0;
1469 if (df->changeable_flags & DF_NO_HARD_REGS)
1471 start = FIRST_PSEUDO_REGISTER;
1472 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1473 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1478 ref_info->total_size
1479 = df_count_refs (include_defs, include_uses, include_eq_uses);
1481 df_check_and_grow_ref_info (ref_info, 1);
1483 for (regno = start; regno < m; regno++)
1486 ref_info->begin[regno] = offset;
1489 df_ref ref = DF_REG_DEF_CHAIN (regno);
1492 ref_info->refs[offset] = ref;
1493 DF_REF_ID (ref) = offset++;
1495 ref = DF_REF_NEXT_REG (ref);
1496 gcc_assert (offset < ref_info->refs_size);
1501 df_ref ref = DF_REG_USE_CHAIN (regno);
1504 ref_info->refs[offset] = ref;
1505 DF_REF_ID (ref) = offset++;
1507 ref = DF_REF_NEXT_REG (ref);
1508 gcc_assert (offset < ref_info->refs_size);
1511 if (include_eq_uses)
1513 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1516 ref_info->refs[offset] = ref;
1517 DF_REF_ID (ref) = offset++;
1519 ref = DF_REF_NEXT_REG (ref);
1520 gcc_assert (offset < ref_info->refs_size);
1523 ref_info->count[regno] = count;
1526 /* The bitmap size is not decremented when refs are deleted. So
1527 reset it now that we have squished out all of the empty
1529 ref_info->table_size = offset;
1533 /* Take build ref table for either the uses or defs from the reg-use
1534 or reg-def chains. This version processes the refs in insn order
1535 which is likely to be best if processing some segment of the
1539 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1542 bool include_eq_uses)
1545 unsigned int bb_index;
1546 unsigned int m = df->regs_inited;
1547 unsigned int offset = 0;
1550 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1552 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1553 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1555 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1556 df_check_and_grow_ref_info (ref_info, 1);
1558 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1560 basic_block bb = BASIC_BLOCK (bb_index);
1565 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1567 unsigned int regno = DF_REF_REGNO (*ref_rec);
1568 ref_info->count[regno]++;
1571 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1573 unsigned int regno = DF_REF_REGNO (*ref_rec);
1574 ref_info->count[regno]++;
1577 FOR_BB_INSNS (bb, insn)
1581 unsigned int uid = INSN_UID (insn);
1584 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1586 unsigned int regno = DF_REF_REGNO (*ref_rec);
1587 ref_info->count[regno]++;
1590 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1592 unsigned int regno = DF_REF_REGNO (*ref_rec);
1593 ref_info->count[regno]++;
1595 if (include_eq_uses)
1596 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1598 unsigned int regno = DF_REF_REGNO (*ref_rec);
1599 ref_info->count[regno]++;
1605 for (r = start; r < m; r++)
1607 ref_info->begin[r] = offset;
1608 offset += ref_info->count[r];
1609 ref_info->count[r] = 0;
1612 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1614 basic_block bb = BASIC_BLOCK (bb_index);
1619 for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1621 df_ref ref = *ref_rec;
1622 unsigned int regno = DF_REF_REGNO (ref);
1626 = ref_info->begin[regno] + ref_info->count[regno]++;
1627 DF_REF_ID (ref) = id;
1628 ref_info->refs[id] = ref;
1632 for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1634 df_ref ref = *ref_rec;
1635 unsigned int regno = DF_REF_REGNO (ref);
1639 = ref_info->begin[regno] + ref_info->count[regno]++;
1640 DF_REF_ID (ref) = id;
1641 ref_info->refs[id] = ref;
1645 FOR_BB_INSNS (bb, insn)
1649 unsigned int uid = INSN_UID (insn);
1652 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1654 df_ref ref = *ref_rec;
1655 unsigned int regno = DF_REF_REGNO (ref);
1659 = ref_info->begin[regno] + ref_info->count[regno]++;
1660 DF_REF_ID (ref) = id;
1661 ref_info->refs[id] = ref;
1665 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1667 df_ref ref = *ref_rec;
1668 unsigned int regno = DF_REF_REGNO (ref);
1672 = ref_info->begin[regno] + ref_info->count[regno]++;
1673 DF_REF_ID (ref) = id;
1674 ref_info->refs[id] = ref;
1677 if (include_eq_uses)
1678 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1680 df_ref ref = *ref_rec;
1681 unsigned int regno = DF_REF_REGNO (ref);
1685 = ref_info->begin[regno] + ref_info->count[regno]++;
1686 DF_REF_ID (ref) = id;
1687 ref_info->refs[id] = ref;
1694 /* The bitmap size is not decremented when refs are deleted. So
1695 reset it now that we have squished out all of the empty
1698 ref_info->table_size = offset;
1701 /* Take build ref table for either the uses or defs from the reg-use
1702 or reg-def chains. */
1705 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1708 bool include_eq_uses)
1710 if (df->analyze_subset)
1711 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1712 include_uses, include_eq_uses);
1714 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1715 include_uses, include_eq_uses);
1719 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1721 df_add_refs_to_table (unsigned int offset,
1722 struct df_ref_info *ref_info,
1727 df_ref ref = *ref_vec;
1728 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
1729 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1731 ref_info->refs[offset] = ref;
1732 DF_REF_ID (*ref_vec) = offset++;
1740 /* Count the number of refs in all of the insns of BB. Include the
1741 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1742 eq_uses if INCLUDE_EQ_USES. */
1745 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1746 struct df_ref_info *ref_info,
1747 bool include_defs, bool include_uses,
1748 bool include_eq_uses)
1753 offset = df_add_refs_to_table (offset, ref_info,
1754 df_get_artificial_defs (bb->index));
1756 offset = df_add_refs_to_table (offset, ref_info,
1757 df_get_artificial_uses (bb->index));
1759 FOR_BB_INSNS (bb, insn)
1762 unsigned int uid = INSN_UID (insn);
1764 offset = df_add_refs_to_table (offset, ref_info,
1765 DF_INSN_UID_DEFS (uid));
1767 offset = df_add_refs_to_table (offset, ref_info,
1768 DF_INSN_UID_USES (uid));
1769 if (include_eq_uses)
1770 offset = df_add_refs_to_table (offset, ref_info,
1771 DF_INSN_UID_EQ_USES (uid));
1777 /* Organize the refs by insn into the table in REF_INFO. If
1778 blocks_to_analyze is defined, use that set, otherwise the entire
1779 program. Include the defs if INCLUDE_DEFS. Include the uses if
1780 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1783 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1784 bool include_defs, bool include_uses,
1785 bool include_eq_uses)
1788 unsigned int offset = 0;
1790 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1791 df_check_and_grow_ref_info (ref_info, 1);
1792 if (df->blocks_to_analyze)
1797 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1799 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK (index), offset, ref_info,
1800 include_defs, include_uses,
1804 ref_info->table_size = offset;
1809 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1810 include_defs, include_uses,
1812 ref_info->table_size = offset;
1817 /* If the use refs in DF are not organized, reorganize them. */
1820 df_maybe_reorganize_use_refs (enum df_ref_order order)
1822 if (order == df->use_info.ref_order)
1827 case DF_REF_ORDER_BY_REG:
1828 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1831 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1832 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1835 case DF_REF_ORDER_BY_INSN:
1836 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1839 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1840 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1843 case DF_REF_ORDER_NO_TABLE:
1844 free (df->use_info.refs);
1845 df->use_info.refs = NULL;
1846 df->use_info.refs_size = 0;
1849 case DF_REF_ORDER_UNORDERED:
1850 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1855 df->use_info.ref_order = order;
1859 /* If the def refs in DF are not organized, reorganize them. */
1862 df_maybe_reorganize_def_refs (enum df_ref_order order)
1864 if (order == df->def_info.ref_order)
1869 case DF_REF_ORDER_BY_REG:
1870 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1873 case DF_REF_ORDER_BY_INSN:
1874 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1877 case DF_REF_ORDER_NO_TABLE:
1878 free (df->def_info.refs);
1879 df->def_info.refs = NULL;
1880 df->def_info.refs_size = 0;
1883 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1884 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1885 case DF_REF_ORDER_UNORDERED:
1886 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1891 df->def_info.ref_order = order;
1895 /* Change all of the basic block references in INSN to use the insn's
1896 current basic block. This function is called from routines that move
1897 instructions from one block to another. */
1900 df_insn_change_bb (rtx insn, basic_block new_bb)
1902 basic_block old_bb = BLOCK_FOR_INSN (insn);
1903 struct df_insn_info *insn_info;
1904 unsigned int uid = INSN_UID (insn);
1906 if (old_bb == new_bb)
1909 set_block_for_insn (insn, new_bb);
1915 fprintf (dump_file, "changing bb of uid %d\n", uid);
1917 insn_info = DF_INSN_UID_SAFE_GET (uid);
1918 if (insn_info == NULL)
1921 fprintf (dump_file, " unscanned insn\n");
1922 df_insn_rescan (insn);
1929 df_set_bb_dirty (new_bb);
1933 fprintf (dump_file, " from %d to %d\n",
1934 old_bb->index, new_bb->index);
1935 df_set_bb_dirty (old_bb);
1939 fprintf (dump_file, " to %d\n", new_bb->index);
1943 /* Helper function for df_ref_change_reg_with_loc. */
1946 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1947 struct df_reg_info *new_df,
1948 int new_regno, rtx loc)
1950 df_ref the_ref = old_df->reg_chain;
1954 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1955 && (DF_REF_LOC (the_ref))
1956 && (*DF_REF_LOC (the_ref) == loc))
1958 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1959 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1960 df_ref *ref_vec, *ref_vec_t;
1961 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1962 unsigned int count = 0;
1964 DF_REF_REGNO (the_ref) = new_regno;
1965 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1967 /* Pull the_ref out of the old regno chain. */
1969 DF_REF_NEXT_REG (prev_ref) = next_ref;
1971 old_df->reg_chain = next_ref;
1973 DF_REF_PREV_REG (next_ref) = prev_ref;
1976 /* Put the ref into the new regno chain. */
1977 DF_REF_PREV_REG (the_ref) = NULL;
1978 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1979 if (new_df->reg_chain)
1980 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1981 new_df->reg_chain = the_ref;
1983 if (DF_REF_BB (the_ref))
1984 df_set_bb_dirty (DF_REF_BB (the_ref));
1986 /* Need to sort the record again that the ref was in because
1987 the regno is a sorting key. First, find the right
1989 if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1990 ref_vec = insn_info->eq_uses;
1992 ref_vec = insn_info->uses;
1994 fprintf (dump_file, "changing reg in insn %d\n",
1995 DF_REF_INSN_UID (the_ref));
1997 ref_vec_t = ref_vec;
1999 /* Find the length. */
2005 qsort (ref_vec, count, sizeof (df_ref ), df_ref_compare);
2010 the_ref = DF_REF_NEXT_REG (the_ref);
2015 /* Change the regno of all refs that contained LOC from OLD_REGNO to
2016 NEW_REGNO. Refs that do not match LOC are not changed which means
2017 that artificial refs are not changed since they have no loc. This
2018 call is to support the SET_REGNO macro. */
2021 df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
2023 if ((!df) || (old_regno == -1) || (old_regno == new_regno))
2026 df_grow_reg_info ();
2028 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
2029 DF_REG_DEF_GET (new_regno), new_regno, loc);
2030 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
2031 DF_REG_USE_GET (new_regno), new_regno, loc);
2032 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
2033 DF_REG_EQ_USE_GET (new_regno), new_regno, loc);
2037 /* Delete the mw_hardregs that point into the eq_notes. */
2040 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
2042 struct df_mw_hardreg **mw_vec = insn_info->mw_hardregs;
2043 unsigned int deleted = 0;
2044 unsigned int count = 0;
2045 struct df_scan_problem_data *problem_data
2046 = (struct df_scan_problem_data *) df_scan->problem_data;
2053 if ((*mw_vec)->flags & DF_REF_IN_NOTE)
2055 struct df_mw_hardreg **temp_vec = mw_vec;
2057 pool_free (problem_data->mw_reg_pool, *mw_vec);
2059 /* Shove the remaining ones down one to fill the gap. While
2060 this looks n**2, it is highly unusual to have any mw regs
2061 in eq_notes and the chances of more than one are almost
2065 *temp_vec = *(temp_vec + 1);
2079 df_scan_free_mws_vec (insn_info->mw_hardregs);
2080 insn_info->mw_hardregs = df_null_mw_rec;
2087 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
2090 df_notes_rescan (rtx insn)
2092 struct df_insn_info *insn_info;
2093 unsigned int uid = INSN_UID (insn);
2098 /* The client has disabled rescanning and plans to do it itself. */
2099 if (df->changeable_flags & DF_NO_INSN_RESCAN)
2102 /* Do nothing if the insn hasn't been emitted yet. */
2103 if (!BLOCK_FOR_INSN (insn))
2106 df_grow_bb_info (df_scan);
2107 df_grow_reg_info ();
2109 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID(insn));
2111 /* The client has deferred rescanning. */
2112 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
2116 insn_info = df_insn_create_insn_record (insn);
2117 insn_info->defs = df_null_ref_rec;
2118 insn_info->uses = df_null_ref_rec;
2119 insn_info->eq_uses = df_null_ref_rec;
2120 insn_info->mw_hardregs = df_null_mw_rec;
2123 bitmap_clear_bit (df->insns_to_delete, uid);
2124 /* If the insn is set to be rescanned, it does not need to also
2125 be notes rescanned. */
2126 if (!bitmap_bit_p (df->insns_to_rescan, uid))
2127 bitmap_set_bit (df->insns_to_notes_rescan, INSN_UID (insn));
2131 bitmap_clear_bit (df->insns_to_delete, uid);
2132 bitmap_clear_bit (df->insns_to_notes_rescan, uid);
2136 basic_block bb = BLOCK_FOR_INSN (insn);
2138 struct df_collection_rec collection_rec;
2139 unsigned int num_deleted;
2141 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
2142 collection_rec.eq_use_vec = XALLOCAVEC (df_ref, 1000);
2143 collection_rec.mw_vec = XALLOCAVEC (struct df_mw_hardreg *, 1000);
2145 num_deleted = df_mw_hardreg_chain_delete_eq_uses (insn_info);
2146 df_ref_chain_delete (insn_info->eq_uses);
2147 insn_info->eq_uses = NULL;
2149 /* Process REG_EQUIV/REG_EQUAL notes */
2150 for (note = REG_NOTES (insn); note;
2151 note = XEXP (note, 1))
2153 switch (REG_NOTE_KIND (note))
2157 df_uses_record (DF_REF_REGULAR, &collection_rec,
2158 &XEXP (note, 0), DF_REF_REG_USE,
2159 bb, insn_info, DF_REF_IN_NOTE, -1, -1, 0);
2165 /* Find some place to put any new mw_hardregs. */
2166 df_canonize_collection_rec (&collection_rec);
2167 if (collection_rec.next_mw)
2169 unsigned int count = 0;
2170 struct df_mw_hardreg **mw_rec = insn_info->mw_hardregs;
2179 /* Append to the end of the existing record after
2180 expanding it if necessary. */
2181 if (collection_rec.next_mw > num_deleted)
2183 insn_info->mw_hardregs =
2184 XRESIZEVEC (struct df_mw_hardreg *,
2185 insn_info->mw_hardregs,
2186 count + 1 + collection_rec.next_mw);
2188 memcpy (&insn_info->mw_hardregs[count], collection_rec.mw_vec,
2189 (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2190 qsort (insn_info->mw_hardregs, count + collection_rec.next_mw,
2191 sizeof (struct df_mw_hardreg *), df_mw_compare);
2195 /* No vector there. */
2196 insn_info->mw_hardregs
2197 = XNEWVEC (struct df_mw_hardreg*,
2198 count + 1 + collection_rec.next_mw);
2199 memcpy (insn_info->mw_hardregs, collection_rec.mw_vec,
2200 (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2203 /* Get rid of the mw_rec so that df_refs_add_to_chains will
2205 collection_rec.mw_vec = NULL;
2206 collection_rec.next_mw = 0;
2207 df_refs_add_to_chains (&collection_rec, bb, insn);
2210 df_insn_rescan (insn);
2215 /*----------------------------------------------------------------------------
2216 Hard core instruction scanning code. No external interfaces here,
2217 just a lot of routines that look inside insns.
2218 ----------------------------------------------------------------------------*/
2221 /* Return true if the contents of two df_ref's are identical.
2222 It ignores DF_REF_MARKER. */
2225 df_ref_equal_p (df_ref ref1, df_ref ref2)
2233 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2234 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2235 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2236 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2237 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2238 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2239 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2240 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2243 switch (DF_REF_CLASS (ref1))
2245 case DF_REF_ARTIFICIAL:
2249 case DF_REF_EXTRACT:
2250 if ((DF_REF_EXTRACT_OFFSET (ref1) != DF_REF_EXTRACT_OFFSET (ref2))
2251 || (DF_REF_EXTRACT_WIDTH (ref1) != DF_REF_EXTRACT_WIDTH (ref2))
2252 || (DF_REF_EXTRACT_MODE (ref1) != DF_REF_EXTRACT_MODE (ref2)))
2256 case DF_REF_REGULAR:
2257 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2266 /* Compare REF1 and REF2 for sorting. This is only called from places
2267 where all of the refs are of the same type, in the same insn, and
2268 have the same bb. So these fields are not checked. */
2271 df_ref_compare (const void *r1, const void *r2)
2273 const df_ref ref1 = *(const df_ref *)r1;
2274 const df_ref ref2 = *(const df_ref *)r2;
2279 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2280 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2282 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2283 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2285 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2286 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2288 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2289 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2291 /* Cannot look at the LOC field on artificial refs. */
2292 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2293 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2294 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2296 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2298 /* If two refs are identical except that one of them has is from
2299 a mw and one is not, we need to have the one with the mw
2301 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2302 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2303 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2304 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2310 /* The classes are the same at this point so it is safe to only look
2312 if (DF_REF_CLASS (ref1) == DF_REF_EXTRACT)
2314 if (DF_REF_EXTRACT_OFFSET (ref1) != DF_REF_EXTRACT_OFFSET (ref2))
2315 return DF_REF_EXTRACT_OFFSET (ref1) - DF_REF_EXTRACT_OFFSET (ref2);
2316 if (DF_REF_EXTRACT_WIDTH (ref1) != DF_REF_EXTRACT_WIDTH (ref2))
2317 return DF_REF_EXTRACT_WIDTH (ref1) - DF_REF_EXTRACT_WIDTH (ref2);
2318 if (DF_REF_EXTRACT_MODE (ref1) != DF_REF_EXTRACT_MODE (ref2))
2319 return DF_REF_EXTRACT_MODE (ref1) - DF_REF_EXTRACT_MODE (ref2);
2325 df_swap_refs (df_ref *ref_vec, int i, int j)
2327 df_ref tmp = ref_vec[i];
2328 ref_vec[i] = ref_vec[j];
2332 /* Sort and compress a set of refs. */
2335 df_sort_and_compress_refs (df_ref *ref_vec, unsigned int count)
2338 unsigned int dist = 0;
2340 ref_vec[count] = NULL;
2341 /* If there are 1 or 0 elements, there is nothing to do. */
2344 else if (count == 2)
2346 if (df_ref_compare (&ref_vec[0], &ref_vec[1]) > 0)
2347 df_swap_refs (ref_vec, 0, 1);
2351 for (i = 0; i < count - 1; i++)
2352 if (df_ref_compare (&ref_vec[i], &ref_vec[i+1]) >= 0)
2354 /* If the array is already strictly ordered,
2355 which is the most common case for large COUNT case
2356 (which happens for CALL INSNs),
2357 no need to sort and filter out duplicate.
2358 Simply return the count.
2359 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2360 of DF_REF_COMPARE. */
2363 qsort (ref_vec, count, sizeof (df_ref), df_ref_compare);
2366 for (i=0; i<count-dist; i++)
2368 /* Find the next ref that is not equal to the current ref. */
2369 while (df_ref_equal_p (ref_vec[i], ref_vec[i + dist + 1]))
2371 df_free_ref (ref_vec[i + dist + 1]);
2374 /* Copy it down to the next position. */
2376 ref_vec[i+1] = ref_vec[i + dist + 1];
2380 ref_vec[count] = NULL;
2385 /* Return true if the contents of two df_ref's are identical.
2386 It ignores DF_REF_MARKER. */
2389 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2393 return (mw1 == mw2) ||
2394 (mw1->mw_reg == mw2->mw_reg
2395 && mw1->type == mw2->type
2396 && mw1->flags == mw2->flags
2397 && mw1->start_regno == mw2->start_regno
2398 && mw1->end_regno == mw2->end_regno);
2402 /* Compare MW1 and MW2 for sorting. */
2405 df_mw_compare (const void *m1, const void *m2)
2407 const struct df_mw_hardreg *const mw1 = *(const struct df_mw_hardreg *const*)m1;
2408 const struct df_mw_hardreg *const mw2 = *(const struct df_mw_hardreg *const*)m2;
2413 if (mw1->type != mw2->type)
2414 return mw1->type - mw2->type;
2416 if (mw1->flags != mw2->flags)
2417 return mw1->flags - mw2->flags;
2419 if (mw1->start_regno != mw2->start_regno)
2420 return mw1->start_regno - mw2->start_regno;
2422 if (mw1->end_regno != mw2->end_regno)
2423 return mw1->end_regno - mw2->end_regno;
2425 if (mw1->mw_reg != mw2->mw_reg)
2426 return mw1->mw_order - mw2->mw_order;
2432 /* Sort and compress a set of refs. */
2435 df_sort_and_compress_mws (struct df_mw_hardreg **mw_vec, unsigned int count)
2437 struct df_scan_problem_data *problem_data
2438 = (struct df_scan_problem_data *) df_scan->problem_data;
2440 unsigned int dist = 0;
2441 mw_vec[count] = NULL;
2445 else if (count == 2)
2447 if (df_mw_compare (&mw_vec[0], &mw_vec[1]) > 0)
2449 struct df_mw_hardreg *tmp = mw_vec[0];
2450 mw_vec[0] = mw_vec[1];
2455 qsort (mw_vec, count, sizeof (struct df_mw_hardreg *), df_mw_compare);
2457 for (i=0; i<count-dist; i++)
2459 /* Find the next ref that is not equal to the current ref. */
2460 while (df_mw_equal_p (mw_vec[i], mw_vec[i + dist + 1]))
2462 pool_free (problem_data->mw_reg_pool, mw_vec[i + dist + 1]);
2465 /* Copy it down to the next position. */
2467 mw_vec[i+1] = mw_vec[i + dist + 1];
2471 mw_vec[count] = NULL;
2476 /* Sort and remove duplicates from the COLLECTION_REC. */
2479 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2481 if (collection_rec->def_vec)
2482 collection_rec->next_def
2483 = df_sort_and_compress_refs (collection_rec->def_vec,
2484 collection_rec->next_def);
2485 if (collection_rec->use_vec)
2486 collection_rec->next_use
2487 = df_sort_and_compress_refs (collection_rec->use_vec,
2488 collection_rec->next_use);
2489 if (collection_rec->eq_use_vec)
2490 collection_rec->next_eq_use
2491 = df_sort_and_compress_refs (collection_rec->eq_use_vec,
2492 collection_rec->next_eq_use);
2493 if (collection_rec->mw_vec)
2494 collection_rec->next_mw
2495 = df_sort_and_compress_mws (collection_rec->mw_vec,
2496 collection_rec->next_mw);
2500 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2503 df_install_ref (df_ref this_ref,
2504 struct df_reg_info *reg_info,
2505 struct df_ref_info *ref_info,
2508 unsigned int regno = DF_REF_REGNO (this_ref);
2509 /* Add the ref to the reg_{def,use,eq_use} chain. */
2510 df_ref head = reg_info->reg_chain;
2512 reg_info->reg_chain = this_ref;
2515 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2517 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2518 df->hard_regs_live_count[regno]++;
2521 gcc_assert (DF_REF_NEXT_REG (this_ref) == NULL);
2522 gcc_assert (DF_REF_PREV_REG (this_ref) == NULL);
2524 DF_REF_NEXT_REG (this_ref) = head;
2526 /* We cannot actually link to the head of the chain. */
2527 DF_REF_PREV_REG (this_ref) = NULL;
2530 DF_REF_PREV_REG (head) = this_ref;
2534 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2535 df_check_and_grow_ref_info (ref_info, 1);
2536 DF_REF_ID (this_ref) = ref_info->table_size;
2537 /* Add the ref to the big array of defs. */
2538 ref_info->refs[ref_info->table_size] = this_ref;
2539 ref_info->table_size++;
2542 DF_REF_ID (this_ref) = -1;
2544 ref_info->total_size++;
2548 /* This function takes one of the groups of refs (defs, uses or
2549 eq_uses) and installs the entire group into the insn. It also adds
2550 each of these refs into the appropriate chains. */
2553 df_install_refs (basic_block bb,
2554 df_ref *old_vec, unsigned int count,
2555 struct df_reg_info **reg_info,
2556 struct df_ref_info *ref_info,
2562 df_ref *new_vec = XNEWVEC (df_ref, count + 1);
2565 switch (ref_info->ref_order)
2567 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2568 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2569 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2570 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2571 add_to_table = true;
2573 case DF_REF_ORDER_UNORDERED:
2574 case DF_REF_ORDER_BY_REG:
2575 case DF_REF_ORDER_BY_INSN:
2576 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2577 add_to_table = !is_notes;
2580 add_to_table = false;
2584 /* Do not add if ref is not in the right blocks. */
2585 if (add_to_table && df->analyze_subset)
2586 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2588 for (i = 0; i < count; i++)
2590 df_ref this_ref = old_vec[i];
2591 new_vec[i] = this_ref;
2592 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2593 ref_info, add_to_table);
2596 new_vec[count] = NULL;
2600 return df_null_ref_rec;
2604 /* This function takes the mws installs the entire group into the
2607 static struct df_mw_hardreg **
2608 df_install_mws (struct df_mw_hardreg **old_vec, unsigned int count)
2612 struct df_mw_hardreg **new_vec
2613 = XNEWVEC (struct df_mw_hardreg*, count + 1);
2614 memcpy (new_vec, old_vec,
2615 sizeof (struct df_mw_hardreg*) * (count + 1));
2619 return df_null_mw_rec;
2623 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2624 chains and update other necessary information. */
2627 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2628 basic_block bb, rtx insn)
2632 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2633 /* If there is a vector in the collection rec, add it to the
2634 insn. A null rec is a signal that the caller will handle the
2636 if (collection_rec->def_vec)
2638 df_scan_free_ref_vec (insn_rec->defs);
2640 = df_install_refs (bb, collection_rec->def_vec,
2641 collection_rec->next_def,
2643 &df->def_info, false);
2645 if (collection_rec->use_vec)
2647 df_scan_free_ref_vec (insn_rec->uses);
2649 = df_install_refs (bb, collection_rec->use_vec,
2650 collection_rec->next_use,
2652 &df->use_info, false);
2654 if (collection_rec->eq_use_vec)
2656 df_scan_free_ref_vec (insn_rec->eq_uses);
2658 = df_install_refs (bb, collection_rec->eq_use_vec,
2659 collection_rec->next_eq_use,
2661 &df->use_info, true);
2663 if (collection_rec->mw_vec)
2665 df_scan_free_mws_vec (insn_rec->mw_hardregs);
2666 insn_rec->mw_hardregs
2667 = df_install_mws (collection_rec->mw_vec,
2668 collection_rec->next_mw);
2673 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2675 df_scan_free_ref_vec (bb_info->artificial_defs);
2676 bb_info->artificial_defs
2677 = df_install_refs (bb, collection_rec->def_vec,
2678 collection_rec->next_def,
2680 &df->def_info, false);
2681 df_scan_free_ref_vec (bb_info->artificial_uses);
2682 bb_info->artificial_uses
2683 = df_install_refs (bb, collection_rec->use_vec,
2684 collection_rec->next_use,
2686 &df->use_info, false);
2691 /* Allocate a ref and initialize its fields.
2693 If the REF_FLAGS field contain DF_REF_SIGN_EXTRACT or
2694 DF_REF_ZERO_EXTRACT. WIDTH, OFFSET and MODE are used to access the fields
2695 if they were constants. Otherwise they should be -1 if those flags
2699 df_ref_create_structure (enum df_ref_class cl,
2700 struct df_collection_rec *collection_rec,
2702 basic_block bb, struct df_insn_info *info,
2703 enum df_ref_type ref_type,
2704 enum df_ref_flags ref_flags,
2705 int width, int offset, enum machine_mode mode)
2707 df_ref this_ref = NULL;
2708 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2709 struct df_scan_problem_data *problem_data
2710 = (struct df_scan_problem_data *) df_scan->problem_data;
2715 this_ref = (df_ref) pool_alloc (problem_data->ref_base_pool);
2716 gcc_assert (loc == NULL);
2719 case DF_REF_ARTIFICIAL:
2720 this_ref = (df_ref) pool_alloc (problem_data->ref_artificial_pool);
2721 this_ref->artificial_ref.bb = bb;
2722 gcc_assert (loc == NULL);
2725 case DF_REF_REGULAR:
2726 this_ref = (df_ref) pool_alloc (problem_data->ref_regular_pool);
2727 this_ref->regular_ref.loc = loc;
2731 case DF_REF_EXTRACT:
2732 this_ref = (df_ref) pool_alloc (problem_data->ref_extract_pool);
2733 DF_REF_EXTRACT_WIDTH (this_ref) = width;
2734 DF_REF_EXTRACT_OFFSET (this_ref) = offset;
2735 DF_REF_EXTRACT_MODE (this_ref) = mode;
2736 this_ref->regular_ref.loc = loc;
2741 DF_REF_CLASS (this_ref) = cl;
2742 DF_REF_ID (this_ref) = -1;
2743 DF_REF_REG (this_ref) = reg;
2744 DF_REF_REGNO (this_ref) = regno;
2745 DF_REF_TYPE (this_ref) = ref_type;
2746 DF_REF_INSN_INFO (this_ref) = info;
2747 DF_REF_CHAIN (this_ref) = NULL;
2748 DF_REF_FLAGS (this_ref) = ref_flags;
2749 DF_REF_NEXT_REG (this_ref) = NULL;
2750 DF_REF_PREV_REG (this_ref) = NULL;
2751 DF_REF_ORDER (this_ref) = df->ref_order++;
2753 /* We need to clear this bit because fwprop, and in the future
2754 possibly other optimizations sometimes create new refs using ond
2755 refs as the model. */
2756 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2758 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2759 if ((regno < FIRST_PSEUDO_REGISTER)
2760 && (!DF_REF_IS_ARTIFICIAL (this_ref)))
2762 if (DF_REF_REG_DEF_P (this_ref))
2764 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2765 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2767 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2768 && (regno == FRAME_POINTER_REGNUM
2769 || regno == ARG_POINTER_REGNUM)))
2770 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2775 if (DF_REF_REG_DEF_P (this_ref))
2776 collection_rec->def_vec[collection_rec->next_def++] = this_ref;
2777 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2778 collection_rec->eq_use_vec[collection_rec->next_eq_use++] = this_ref;
2780 collection_rec->use_vec[collection_rec->next_use++] = this_ref;
2787 /* Create new references of type DF_REF_TYPE for each part of register REG
2788 at address LOC within INSN of BB.
2790 If the REF_FLAGS field contain DF_REF_SIGN_EXTRACT or
2791 DF_REF_ZERO_EXTRACT. WIDTH, OFFSET and MODE are used to access the
2792 fields if they were constants. Otherwise they should be -1 if
2793 those flags were set. */
2797 df_ref_record (enum df_ref_class cl,
2798 struct df_collection_rec *collection_rec,
2800 basic_block bb, struct df_insn_info *insn_info,
2801 enum df_ref_type ref_type,
2802 enum df_ref_flags ref_flags,
2803 int width, int offset, enum machine_mode mode)
2807 gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2809 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2810 if (regno < FIRST_PSEUDO_REGISTER)
2812 struct df_mw_hardreg *hardreg = NULL;
2813 struct df_scan_problem_data *problem_data
2814 = (struct df_scan_problem_data *) df_scan->problem_data;
2816 unsigned int endregno;
2819 if (GET_CODE (reg) == SUBREG)
2821 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2822 SUBREG_BYTE (reg), GET_MODE (reg));
2823 endregno = regno + subreg_nregs (reg);
2826 endregno = END_HARD_REGNO (reg);
2828 /* If this is a multiword hardreg, we create some extra
2829 datastructures that will enable us to easily build REG_DEAD
2830 and REG_UNUSED notes. */
2831 if ((endregno != regno + 1) && insn_info)
2833 /* Sets to a subreg of a multiword register are partial.
2834 Sets to a non-subreg of a multiword register are not. */
2835 if (GET_CODE (reg) == SUBREG)
2836 ref_flags |= DF_REF_PARTIAL;
2837 ref_flags |= DF_REF_MW_HARDREG;
2839 hardreg = (struct df_mw_hardreg *) pool_alloc (problem_data->mw_reg_pool);
2840 hardreg->type = ref_type;
2841 hardreg->flags = ref_flags;
2842 hardreg->mw_reg = reg;
2843 hardreg->start_regno = regno;
2844 hardreg->end_regno = endregno - 1;
2845 hardreg->mw_order = df->ref_order++;
2846 collection_rec->mw_vec[collection_rec->next_mw++] = hardreg;
2849 for (i = regno; i < endregno; i++)
2851 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2852 bb, insn_info, ref_type, ref_flags,
2853 width, offset, mode);
2855 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2860 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2861 ref_type, ref_flags, width, offset, mode);
2866 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2867 covered by the outer mode is smaller than that covered by the inner mode,
2868 is a read-modify-write operation.
2869 This function returns true iff the SUBREG X is such a SUBREG. */
2872 df_read_modify_subreg_p (rtx x)
2874 unsigned int isize, osize;
2875 if (GET_CODE (x) != SUBREG)
2877 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2878 osize = GET_MODE_SIZE (GET_MODE (x));
2879 return isize > osize
2880 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2884 /* Process all the registers defined in the rtx, X.
2885 Autoincrement/decrement definitions will be picked up by
2889 df_def_record_1 (struct df_collection_rec *collection_rec,
2890 rtx x, basic_block bb, struct df_insn_info *insn_info,
2891 enum df_ref_flags flags)
2897 enum machine_mode mode = 0;
2898 enum df_ref_class cl = DF_REF_REGULAR;
2900 /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
2902 if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
2905 loc = &SET_DEST (x);
2908 /* It is legal to have a set destination be a parallel. */
2909 if (GET_CODE (dst) == PARALLEL)
2913 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2915 rtx temp = XVECEXP (dst, 0, i);
2916 if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
2917 || GET_CODE (temp) == SET)
2918 df_def_record_1 (collection_rec,
2919 temp, bb, insn_info,
2920 GET_CODE (temp) == CLOBBER
2921 ? flags | DF_REF_MUST_CLOBBER : flags);
2926 if (GET_CODE (dst) == STRICT_LOW_PART)
2928 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2930 loc = &XEXP (dst, 0);
2934 if (GET_CODE (dst) == ZERO_EXTRACT)
2936 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2938 if (GET_CODE (XEXP (dst, 1)) == CONST_INT
2939 && GET_CODE (XEXP (dst, 2)) == CONST_INT)
2941 width = INTVAL (XEXP (dst, 1));
2942 offset = INTVAL (XEXP (dst, 2));
2943 mode = GET_MODE (dst);
2944 cl = DF_REF_EXTRACT;
2947 loc = &XEXP (dst, 0);
2951 /* At this point if we do not have a reg or a subreg, just return. */
2954 df_ref_record (cl, collection_rec,
2955 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags,
2956 width, offset, mode);
2958 /* We want to keep sp alive everywhere - by making all
2959 writes to sp also use of sp. */
2960 if (REGNO (dst) == STACK_POINTER_REGNUM)
2961 df_ref_record (DF_REF_BASE, collection_rec,
2962 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags,
2963 width, offset, mode);
2965 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2967 if (df_read_modify_subreg_p (dst))
2968 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2970 flags |= DF_REF_SUBREG;
2972 df_ref_record (cl, collection_rec,
2973 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags,
2974 width, offset, mode);
2979 /* Process all the registers defined in the pattern rtx, X. */
2982 df_defs_record (struct df_collection_rec *collection_rec,
2983 rtx x, basic_block bb, struct df_insn_info *insn_info,
2984 enum df_ref_flags flags)
2986 RTX_CODE code = GET_CODE (x);
2988 if (code == SET || code == CLOBBER)
2990 /* Mark the single def within the pattern. */
2991 enum df_ref_flags clobber_flags = flags;
2992 clobber_flags |= (code == CLOBBER) ? DF_REF_MUST_CLOBBER : 0;
2993 df_def_record_1 (collection_rec, x, bb, insn_info, clobber_flags);
2995 else if (code == COND_EXEC)
2997 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2998 bb, insn_info, DF_REF_CONDITIONAL);
3000 else if (code == PARALLEL)
3004 /* Mark the multiple defs within the pattern. */
3005 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3006 df_defs_record (collection_rec, XVECEXP (x, 0, i), bb, insn_info, flags);
3011 /* Process all the registers used in the rtx at address LOC.
3013 If the REF_FLAGS field contain DF_REF_SIGN_EXTRACT or
3014 DF_REF_ZERO_EXTRACT. WIDTH, OFFSET and MODE are used to access the
3015 fields if they were constants. Otherwise they should be -1 if
3016 those flags were set. */
3019 df_uses_record (enum df_ref_class cl, struct df_collection_rec *collection_rec,
3020 rtx *loc, enum df_ref_type ref_type,
3021 basic_block bb, struct df_insn_info *insn_info,
3022 enum df_ref_flags flags,
3023 int width, int offset, enum machine_mode mode)
3032 code = GET_CODE (x);
3049 /* If we are clobbering a MEM, mark any registers inside the address
3051 if (MEM_P (XEXP (x, 0)))
3052 df_uses_record (cl, collection_rec,
3053 &XEXP (XEXP (x, 0), 0),
3054 DF_REF_REG_MEM_STORE,
3056 flags, width, offset, mode);
3058 /* If we're clobbering a REG then we have a def so ignore. */
3062 df_uses_record (cl, collection_rec,
3063 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
3064 bb, insn_info, flags & DF_REF_IN_NOTE,
3065 width, offset, mode);
3069 /* While we're here, optimize this case. */
3070 flags |= DF_REF_PARTIAL;
3071 /* In case the SUBREG is not of a REG, do not optimize. */
3072 if (!REG_P (SUBREG_REG (x)))
3074 loc = &SUBREG_REG (x);
3075 df_uses_record (cl, collection_rec, loc, ref_type, bb, insn_info, flags,
3076 width, offset, mode);
3079 /* ... Fall through ... */
3082 df_ref_record (cl, collection_rec,
3083 x, loc, bb, insn_info,
3085 width, offset, mode);
3091 /* If the parameters to the zero or sign extract are
3092 constants, strip them off and recurse, otherwise there is
3093 no information that we can gain from this operation. */
3094 if (GET_CODE (XEXP (x, 1)) == CONST_INT
3095 && GET_CODE (XEXP (x, 2)) == CONST_INT)
3097 width = INTVAL (XEXP (x, 1));
3098 offset = INTVAL (XEXP (x, 2));
3099 mode = GET_MODE (x);
3101 if (code == ZERO_EXTRACT)
3102 flags |= DF_REF_ZERO_EXTRACT;
3104 flags |= DF_REF_SIGN_EXTRACT;
3106 df_uses_record (DF_REF_EXTRACT, collection_rec,
3107 &XEXP (x, 0), ref_type, bb, insn_info, flags,
3108 width, offset, mode);
3116 rtx dst = SET_DEST (x);
3117 gcc_assert (!(flags & DF_REF_IN_NOTE));
3118 df_uses_record (cl, collection_rec,
3119 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags,
3120 width, offset, mode);
3122 switch (GET_CODE (dst))
3125 if (df_read_modify_subreg_p (dst))
3127 df_uses_record (cl, collection_rec, &SUBREG_REG (dst),
3128 DF_REF_REG_USE, bb, insn_info,
3129 flags | DF_REF_READ_WRITE | DF_REF_SUBREG,
3130 width, offset, mode);
3141 df_uses_record (cl, collection_rec, &XEXP (dst, 0),
3142 DF_REF_REG_MEM_STORE, bb, insn_info, flags,
3143 width, offset, mode);
3145 case STRICT_LOW_PART:
3147 rtx *temp = &XEXP (dst, 0);
3148 /* A strict_low_part uses the whole REG and not just the
3150 dst = XEXP (dst, 0);
3151 df_uses_record (cl, collection_rec,
3152 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
3153 DF_REF_REG_USE, bb, insn_info,
3154 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART,
3155 width, offset, mode);
3160 if (GET_CODE (XEXP (dst, 1)) == CONST_INT
3161 && GET_CODE (XEXP (dst, 2)) == CONST_INT)
3163 width = INTVAL (XEXP (dst, 1));
3164 offset = INTVAL (XEXP (dst, 2));
3165 mode = GET_MODE (dst);
3166 df_uses_record (DF_REF_EXTRACT, collection_rec, &XEXP (dst, 0),
3167 DF_REF_REG_USE, bb, insn_info,
3168 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT,
3169 width, offset, mode);
3173 df_uses_record (cl, collection_rec, &XEXP (dst, 1),
3174 DF_REF_REG_USE, bb, insn_info, flags,
3175 width, offset, mode);
3176 df_uses_record (cl, collection_rec, &XEXP (dst, 2),
3177 DF_REF_REG_USE, bb, insn_info, flags,
3178 width, offset, mode);
3179 df_uses_record (cl, collection_rec, &XEXP (dst, 0),
3180 DF_REF_REG_USE, bb, insn_info,
3181 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT,
3182 width, offset, mode);
3198 case UNSPEC_VOLATILE:
3202 /* Traditional and volatile asm instructions must be
3203 considered to use and clobber all hard registers, all
3204 pseudo-registers and all of memory. So must TRAP_IF and
3205 UNSPEC_VOLATILE operations.
3207 Consider for instance a volatile asm that changes the fpu
3208 rounding mode. An insn should not be moved across this
3209 even if it only uses pseudo-regs because it might give an
3210 incorrectly rounded result.
3212 However, flow.c's liveness computation did *not* do this,
3213 giving the reasoning as " ?!? Unfortunately, marking all
3214 hard registers as live causes massive problems for the
3215 register allocator and marking all pseudos as live creates
3216 mountains of uninitialized variable warnings."
3218 In order to maintain the status quo with regard to liveness
3219 and uses, we do what flow.c did and just mark any regs we
3220 can find in ASM_OPERANDS as used. In global asm insns are
3221 scanned and regs_asm_clobbered is filled out.
3223 For all ASM_OPERANDS, we must traverse the vector of input
3224 operands. We can not just fall through here since then we
3225 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3226 which do not indicate traditional asms unlike their normal
3228 if (code == ASM_OPERANDS)
3232 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3233 df_uses_record (cl, collection_rec, &ASM_OPERANDS_INPUT (x, j),
3234 DF_REF_REG_USE, bb, insn_info, flags,
3235 width, offset, mode);
3247 /* Catch the def of the register being modified. */
3248 df_ref_record (cl, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3251 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY,
3252 width, offset, mode);
3254 /* ... Fall through to handle uses ... */
3260 /* Recursively scan the operands of this expression. */
3262 const char *fmt = GET_RTX_FORMAT (code);
3265 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3269 /* Tail recursive case: save a function call level. */
3275 df_uses_record (cl, collection_rec, &XEXP (x, i), ref_type,
3276 bb, insn_info, flags,
3277 width, offset, mode);
3279 else if (fmt[i] == 'E')
3282 for (j = 0; j < XVECLEN (x, i); j++)
3283 df_uses_record (cl, collection_rec,
3284 &XVECEXP (x, i, j), ref_type,
3285 bb, insn_info, flags,
3286 width, offset, mode);
3295 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3298 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3301 for (i = 0; i < collection_rec->next_def; i++)
3303 df_ref ref = collection_rec->def_vec[i];
3304 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3308 enum machine_mode mode = 0;
3311 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
3313 width = DF_REF_EXTRACT_WIDTH (ref);
3314 offset = DF_REF_EXTRACT_OFFSET (ref);
3315 mode = DF_REF_EXTRACT_MODE (ref);
3318 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3319 DF_REF_LOC (ref), DF_REF_BB (ref),
3320 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3321 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL,
3322 width, offset, mode);
3323 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3329 /* Get call's extra defs and uses. */
3332 df_get_call_refs (struct df_collection_rec * collection_rec,
3334 struct df_insn_info *insn_info,
3335 enum df_ref_flags flags)
3340 bool is_sibling_call;
3342 bitmap defs_generated = BITMAP_ALLOC (&df_bitmap_obstack);
3344 /* Do not generate clobbers for registers that are the result of the
3345 call. This causes ordering problems in the chain building code
3346 depending on which def is seen first. */
3347 for (i=0; i<collection_rec->next_def; i++)
3349 df_ref def = collection_rec->def_vec[i];
3350 bitmap_set_bit (defs_generated, DF_REF_REGNO (def));
3353 /* Record the registers used to pass arguments, and explicitly
3354 noted as clobbered. */
3355 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3356 note = XEXP (note, 1))
3358 if (GET_CODE (XEXP (note, 0)) == USE)
3359 df_uses_record (DF_REF_REGULAR, collection_rec, &XEXP (XEXP (note, 0), 0),
3360 DF_REF_REG_USE, bb, insn_info, flags, -1, -1, 0);
3361 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3363 if (REG_P (XEXP (XEXP (note, 0), 0)))
3365 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3366 if (!bitmap_bit_p (defs_generated, regno))
3367 df_defs_record (collection_rec, XEXP (note, 0), bb,
3371 df_uses_record (DF_REF_REGULAR, collection_rec, &XEXP (note, 0),
3372 DF_REF_REG_USE, bb, insn_info, flags, -1, -1, 0);
3376 /* The stack ptr is used (honorarily) by a CALL insn. */
3377 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[STACK_POINTER_REGNUM],
3378 NULL, bb, insn_info, DF_REF_REG_USE,
3379 DF_REF_CALL_STACK_USAGE | flags,
3382 /* Calls may also reference any of the global registers,
3383 so they are recorded as used. */
3384 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3387 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3388 NULL, bb, insn_info, DF_REF_REG_USE, flags, -1, -1, 0);
3389 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3390 NULL, bb, insn_info, DF_REF_REG_DEF, flags, -1, -1, 0);
3393 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3394 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, ui, bi)
3396 if (!global_regs[ui]
3397 && (!bitmap_bit_p (defs_generated, ui))
3398 && (!is_sibling_call
3399 || !bitmap_bit_p (df->exit_block_uses, ui)
3400 || refers_to_regno_p (ui, ui+1,
3401 crtl->return_rtx, NULL)))
3402 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[ui],
3403 NULL, bb, insn_info, DF_REF_REG_DEF,
3404 DF_REF_MAY_CLOBBER | flags,
3408 BITMAP_FREE (defs_generated);
3412 /* Collect all refs in the INSN. This function is free of any
3413 side-effect - it will create and return a lists of df_ref's in the
3414 COLLECTION_REC without putting those refs into existing ref chains
3418 df_insn_refs_collect (struct df_collection_rec* collection_rec,
3419 basic_block bb, struct df_insn_info *insn_info)
3422 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3424 /* Clear out the collection record. */
3425 collection_rec->next_def = 0;
3426 collection_rec->next_use = 0;
3427 collection_rec->next_eq_use = 0;
3428 collection_rec->next_mw = 0;
3430 /* Record register defs. */
3431 df_defs_record (collection_rec, PATTERN (insn_info->insn), bb, insn_info, 0);
3433 /* Process REG_EQUIV/REG_EQUAL notes. */
3434 for (note = REG_NOTES (insn_info->insn); note;
3435 note = XEXP (note, 1))
3437 switch (REG_NOTE_KIND (note))
3441 df_uses_record (DF_REF_REGULAR, collection_rec,
3442 &XEXP (note, 0), DF_REF_REG_USE,
3443 bb, insn_info, DF_REF_IN_NOTE, -1, -1, 0);
3445 case REG_NON_LOCAL_GOTO:
3446 /* The frame ptr is used by a non-local goto. */
3447 df_ref_record (DF_REF_BASE, collection_rec,
3448 regno_reg_rtx[FRAME_POINTER_REGNUM],
3449 NULL, bb, insn_info,
3450 DF_REF_REG_USE, 0, -1, -1, 0);
3451 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3452 df_ref_record (DF_REF_BASE, collection_rec,
3453 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3454 NULL, bb, insn_info,
3455 DF_REF_REG_USE, 0, -1, -1, 0);
3463 if (CALL_P (insn_info->insn))
3464 df_get_call_refs (collection_rec, bb, insn_info,
3465 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3467 /* Record the register uses. */
3468 df_uses_record (DF_REF_REGULAR, collection_rec,
3469 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0,
3472 /* DF_REF_CONDITIONAL needs corresponding USES. */
3474 df_get_conditional_uses (collection_rec);
3476 df_canonize_collection_rec (collection_rec);
3479 /* Recompute the luids for the insns in BB. */
3482 df_recompute_luids (basic_block bb)
3487 df_grow_insn_info ();
3489 /* Scan the block an insn at a time from beginning to end. */
3490 FOR_BB_INSNS (bb, insn)
3492 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3493 /* Inserting labels does not always trigger the incremental
3497 gcc_assert (!INSN_P (insn));
3498 insn_info = df_insn_create_insn_record (insn);
3501 DF_INSN_INFO_LUID (insn_info) = luid;
3508 /* Returns true if the function entry needs to
3509 define the static chain register. */
3512 df_need_static_chain_reg (struct function *fun)
3514 tree fun_context = decl_function_context (fun->decl);
3516 && DECL_NO_STATIC_CHAIN (fun_context) == false;
3520 /* Collect all artificial refs at the block level for BB and add them
3521 to COLLECTION_REC. */
3524 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3526 collection_rec->next_def = 0;
3527 collection_rec->next_use = 0;
3528 collection_rec->next_eq_use = 0;
3529 collection_rec->next_mw = 0;
3531 if (bb->index == ENTRY_BLOCK)
3533 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3536 else if (bb->index == EXIT_BLOCK)
3538 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3542 #ifdef EH_RETURN_DATA_REGNO
3543 if (bb_has_eh_pred (bb))
3546 /* Mark the registers that will contain data for the handler. */
3549 unsigned regno = EH_RETURN_DATA_REGNO (i);
3550 if (regno == INVALID_REGNUM)
3552 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3553 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP, -1, -1, 0);
3558 /* Add the hard_frame_pointer if this block is the target of a
3560 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3561 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3562 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP, -1, -1, 0);
3564 /* Add the artificial uses. */
3565 if (bb->index >= NUM_FIXED_BLOCKS)
3569 bitmap au = bb_has_eh_pred (bb)
3570 ? df->eh_block_artificial_uses
3571 : df->regular_block_artificial_uses;
3573 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3575 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3576 bb, NULL, DF_REF_REG_USE, 0, -1, -1, 0);
3580 df_canonize_collection_rec (collection_rec);
3584 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3587 df_bb_refs_record (int bb_index, bool scan_insns)
3589 basic_block bb = BASIC_BLOCK (bb_index);
3592 struct df_scan_bb_info *bb_info;
3593 struct df_collection_rec collection_rec;
3594 collection_rec.def_vec = XALLOCAVEC (df_ref, 1000);
3595 collection_rec.use_vec = XALLOCAVEC (df_ref, 1000);
3596 collection_rec.eq_use_vec = XALLOCAVEC (df_ref, 1000);
3597 collection_rec.mw_vec = XALLOCAVEC (struct df_mw_hardreg *, 100);
3602 bb_info = df_scan_get_bb_info (bb_index);
3604 /* Need to make sure that there is a record in the basic block info. */
3607 bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
3608 df_scan_set_bb_info (bb_index, bb_info);
3609 bb_info->artificial_defs = NULL;
3610 bb_info->artificial_uses = NULL;
3614 /* Scan the block an insn at a time from beginning to end. */
3615 FOR_BB_INSNS (bb, insn)
3617 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3618 gcc_assert (!insn_info);
3620 insn_info = df_insn_create_insn_record (insn);
3623 /* Record refs within INSN. */
3624 DF_INSN_INFO_LUID (insn_info) = luid++;
3625 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3626 df_refs_add_to_chains (&collection_rec, bb, insn);
3628 DF_INSN_INFO_LUID (insn_info) = luid;
3631 /* Other block level artificial refs */
3632 df_bb_refs_collect (&collection_rec, bb);
3633 df_refs_add_to_chains (&collection_rec, bb, NULL);
3635 /* Now that the block has been processed, set the block as dirty so
3636 LR and LIVE will get it processed. */
3637 df_set_bb_dirty (bb);
3641 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3645 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3651 bitmap_clear (regular_block_artificial_uses);
3653 if (reload_completed)
3655 if (frame_pointer_needed)
3656 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3659 /* Before reload, there are a few registers that must be forced
3660 live everywhere -- which might not already be the case for
3661 blocks within infinite loops. */
3663 /* Any reference to any pseudo before reload is a potential
3664 reference of the frame pointer. */
3665 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3667 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3668 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3671 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3672 /* Pseudos with argument area equivalences may require
3673 reloading via the argument pointer. */
3674 if (fixed_regs[ARG_POINTER_REGNUM])
3675 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3678 /* Any constant, or pseudo with constant equivalences, may
3679 require reloading from memory using the pic register. */
3680 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3681 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3682 bitmap_set_bit (regular_block_artificial_uses, PIC_OFFSET_TABLE_REGNUM);
3684 /* The all-important stack pointer must always be live. */
3685 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3688 /* EH_USES registers are used:
3689 1) at all insns that might throw (calls or with -fnon-call-exceptions
3692 3) to support backtraces and/or debugging, anywhere between their
3693 initialization and where they the saved registers are restored
3694 from them, including the cases where we don't reach the epilogue
3695 (noreturn call or infinite loop). */
3696 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3698 bitmap_set_bit (regular_block_artificial_uses, i);
3703 /* Get the artificial use set for an eh block. */
3706 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3708 bitmap_clear (eh_block_artificial_uses);
3710 /* The following code (down thru the arg_pointer setting APPEARS
3711 to be necessary because there is nothing that actually
3712 describes what the exception handling code may actually need
3714 if (reload_completed)
3716 if (frame_pointer_needed)
3718 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3719 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3720 bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3723 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3724 if (fixed_regs[ARG_POINTER_REGNUM])
3725 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3732 /*----------------------------------------------------------------------------
3733 Specialized hard register scanning functions.
3734 ----------------------------------------------------------------------------*/
3737 /* Mark a register in SET. Hard registers in large modes get all
3738 of their component registers set as well. */
3741 df_mark_reg (rtx reg, void *vset)
3743 bitmap set = (bitmap) vset;
3744 int regno = REGNO (reg);
3746 gcc_assert (GET_MODE (reg) != BLKmode);
3748 bitmap_set_bit (set, regno);
3749 if (regno < FIRST_PSEUDO_REGISTER)
3751 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3753 bitmap_set_bit (set, regno + n);
3758 /* Set the bit for regs that are considered being defined at the entry. */
3761 df_get_entry_block_def_set (bitmap entry_block_defs)
3766 bitmap_clear (entry_block_defs);
3768 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3770 if (FUNCTION_ARG_REGNO_P (i))
3771 #ifdef INCOMING_REGNO
3772 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3774 bitmap_set_bit (entry_block_defs, i);
3778 /* The always important stack pointer. */
3779 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3781 /* Once the prologue has been generated, all of these registers
3782 should just show up in the first regular block. */
3783 if (HAVE_prologue && epilogue_completed)
3785 /* Defs for the callee saved registers are inserted so that the
3786 pushes have some defining location. */
3787 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3788 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3789 bitmap_set_bit (entry_block_defs, i);
3793 /* If STATIC_CHAIN_INCOMING_REGNUM == STATIC_CHAIN_REGNUM
3794 only STATIC_CHAIN_REGNUM is defined. If they are different,
3795 we only care about the STATIC_CHAIN_INCOMING_REGNUM. */
3796 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3797 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3799 #ifdef STATIC_CHAIN_REGNUM
3800 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3805 r = targetm.calls.struct_value_rtx (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 FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
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 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3825 /* Pseudos with argument area equivalences may require
3826 reloading via the argument pointer. */
3827 if (fixed_regs[ARG_POINTER_REGNUM])
3828 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3831 #ifdef PIC_OFFSET_TABLE_REGNUM
3832 /* Any constant, or pseudo with constant equivalences, may
3833 require reloading from memory using the pic register. */
3834 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3835 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3836 bitmap_set_bit (entry_block_defs, PIC_OFFSET_TABLE_REGNUM);
3840 #ifdef INCOMING_RETURN_ADDR_RTX
3841 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3842 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3845 targetm.live_on_entry (entry_block_defs);
3847 /* If the function has an incoming STATIC_CHAIN,
3848 it has to show up in the entry def set. */
3849 if (df_need_static_chain_reg (cfun))
3851 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3852 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3854 #ifdef STATIC_CHAIN_REGNUM
3855 bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3862 /* Return the (conservative) set of hard registers that are defined on
3863 entry to the function.
3864 It uses df->entry_block_defs to determine which register
3865 reference to include. */
3868 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3869 bitmap entry_block_defs)
3874 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3876 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3877 ENTRY_BLOCK_PTR, NULL, DF_REF_REG_DEF, 0, -1, -1, 0);
3880 df_canonize_collection_rec (collection_rec);
3884 /* Record the (conservative) set of hard registers that are defined on
3885 entry to the function. */
3888 df_record_entry_block_defs (bitmap entry_block_defs)
3890 struct df_collection_rec collection_rec;
3891 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3892 collection_rec.def_vec = XALLOCAVEC (df_ref, FIRST_PSEUDO_REGISTER);
3894 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3896 /* Process bb_refs chain */
3897 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (ENTRY_BLOCK), NULL);
3901 /* Update the defs in the entry block. */
3904 df_update_entry_block_defs (void)
3906 bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3907 bool changed = false;
3909 df_get_entry_block_def_set (refs);
3910 if (df->entry_block_defs)
3912 if (!bitmap_equal_p (df->entry_block_defs, refs))
3914 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3915 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3916 df_ref_chain_delete (bb_info->artificial_defs);
3917 bb_info->artificial_defs = NULL;
3923 struct df_scan_problem_data *problem_data
3924 = (struct df_scan_problem_data *) df_scan->problem_data;
3925 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3931 df_record_entry_block_defs (refs);
3932 bitmap_copy (df->entry_block_defs, refs);
3933 df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
3939 /* Set the bit for regs that are considered being used at the exit. */
3942 df_get_exit_block_use_set (bitmap exit_block_uses)
3946 bitmap_clear (exit_block_uses);
3948 /* Stack pointer is always live at the exit. */
3949 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3951 /* Mark the frame pointer if needed at the end of the function.
3952 If we end up eliminating it, it will be removed from the live
3953 list of each basic block by reload. */
3955 if ((!reload_completed) || frame_pointer_needed)
3957 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3958 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3959 /* If they are different, also mark the hard frame pointer as live. */
3960 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3961 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3965 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3966 /* Many architectures have a GP register even without flag_pic.
3967 Assume the pic register is not in use, or will be handled by
3968 other means, if it is not fixed. */
3969 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3970 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3971 bitmap_set_bit (exit_block_uses, PIC_OFFSET_TABLE_REGNUM);
3974 /* Mark all global registers, and all registers used by the
3975 epilogue as being live at the end of the function since they
3976 may be referenced by our caller. */
3977 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3978 if (global_regs[i] || EPILOGUE_USES (i))
3979 bitmap_set_bit (exit_block_uses, i);
3981 if (HAVE_epilogue && epilogue_completed)
3983 /* Mark all call-saved registers that we actually used. */
3984 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3985 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3986 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3987 bitmap_set_bit (exit_block_uses, i);
3990 #ifdef EH_RETURN_DATA_REGNO
3991 /* Mark the registers that will contain data for the handler. */
3992 if (reload_completed && crtl->calls_eh_return)
3995 unsigned regno = EH_RETURN_DATA_REGNO (i);
3996 if (regno == INVALID_REGNUM)
3998 bitmap_set_bit (exit_block_uses, regno);
4002 #ifdef EH_RETURN_STACKADJ_RTX
4003 if ((!HAVE_epilogue || ! epilogue_completed)
4004 && crtl->calls_eh_return)
4006 rtx tmp = EH_RETURN_STACKADJ_RTX;
4007 if (tmp && REG_P (tmp))
4008 df_mark_reg (tmp, exit_block_uses);
4012 #ifdef EH_RETURN_HANDLER_RTX
4013 if ((!HAVE_epilogue || ! epilogue_completed)
4014 && crtl->calls_eh_return)
4016 rtx tmp = EH_RETURN_HANDLER_RTX;
4017 if (tmp && REG_P (tmp))
4018 df_mark_reg (tmp, exit_block_uses);
4022 /* Mark function return value. */
4023 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
4027 /* Return the refs of hard registers that are used in the exit block.
4028 It uses df->exit_block_uses to determine register to include. */
4031 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
4036 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
4037 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
4038 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0, -1, -1, 0);
4040 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4041 /* It is deliberate that this is not put in the exit block uses but
4042 I do not know why. */
4043 if (reload_completed
4044 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
4045 && bb_has_eh_pred (EXIT_BLOCK_PTR)
4046 && fixed_regs[ARG_POINTER_REGNUM])
4047 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
4048 EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0, -1, -1, 0);
4051 df_canonize_collection_rec (collection_rec);
4055 /* Record the set of hard registers that are used in the exit block.
4056 It uses df->exit_block_uses to determine which bit to include. */
4059 df_record_exit_block_uses (bitmap exit_block_uses)
4061 struct df_collection_rec collection_rec;
4062 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4063 collection_rec.use_vec = XALLOCAVEC (df_ref, FIRST_PSEUDO_REGISTER);
4065 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
4067 /* Process bb_refs chain */
4068 df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (EXIT_BLOCK), NULL);
4072 /* Update the uses in the exit block. */
4075 df_update_exit_block_uses (void)
4077 bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
4078 bool changed = false;
4080 df_get_exit_block_use_set (refs);
4081 if (df->exit_block_uses)
4083 if (!bitmap_equal_p (df->exit_block_uses, refs))
4085 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
4086 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
4087 df_ref_chain_delete (bb_info->artificial_uses);
4088 bb_info->artificial_uses = NULL;
4094 struct df_scan_problem_data *problem_data
4095 = (struct df_scan_problem_data *) df_scan->problem_data;
4096 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
4102 df_record_exit_block_uses (refs);
4103 bitmap_copy (df->exit_block_uses, refs);
4104 df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
4109 static bool initialized = false;
4112 /* Initialize some platform specific structures. */
4115 df_hard_reg_init (void)
4118 #ifdef ELIMINABLE_REGS
4119 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
4124 bitmap_obstack_initialize (&persistent_obstack);
4126 /* Record which registers will be eliminated. We use this in
4128 CLEAR_HARD_REG_SET (elim_reg_set);
4130 #ifdef ELIMINABLE_REGS
4131 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
4132 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
4134 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
4137 df_invalidated_by_call = BITMAP_ALLOC (&persistent_obstack);
4139 /* Inconveniently, this is only readily available in hard reg set
4141 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
4142 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
4143 bitmap_set_bit (df_invalidated_by_call, i);
4149 /* Recompute the parts of scanning that are based on regs_ever_live
4150 because something changed in that array. */
4153 df_update_entry_exit_and_calls (void)
4157 df_update_entry_block_defs ();
4158 df_update_exit_block_uses ();
4160 /* The call insns need to be rescanned because there may be changes
4161 in the set of registers clobbered across the call. */
4165 FOR_BB_INSNS (bb, insn)
4167 if (INSN_P (insn) && CALL_P (insn))
4168 df_insn_rescan (insn);
4174 /* Return true if hard REG is actually used in the some instruction.
4175 There are a fair number of conditions that affect the setting of
4176 this array. See the comment in df.h for df->hard_regs_live_count
4177 for the conditions that this array is set. */
4180 df_hard_reg_used_p (unsigned int reg)
4183 return df->hard_regs_live_count[reg] != 0;
4187 /* A count of the number of times REG is actually used in the some
4188 instruction. There are a fair number of conditions that affect the
4189 setting of this array. See the comment in df.h for
4190 df->hard_regs_live_count for the conditions that this array is
4195 df_hard_reg_used_count (unsigned int reg)
4198 return df->hard_regs_live_count[reg];
4202 /* Get the value of regs_ever_live[REGNO]. */
4205 df_regs_ever_live_p (unsigned int regno)
4207 return regs_ever_live[regno];
4211 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
4212 to change, schedule that change for the next update. */
4215 df_set_regs_ever_live (unsigned int regno, bool value)
4217 if (regs_ever_live[regno] == value)
4220 regs_ever_live[regno] = value;
4222 df->redo_entry_and_exit = true;
4226 /* Compute "regs_ever_live" information from the underlying df
4227 information. Set the vector to all false if RESET. */
4230 df_compute_regs_ever_live (bool reset)
4233 bool changed = df->redo_entry_and_exit;
4236 memset (regs_ever_live, 0, sizeof (regs_ever_live));
4238 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4239 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
4241 regs_ever_live[i] = true;
4245 df_update_entry_exit_and_calls ();
4246 df->redo_entry_and_exit = false;
4250 /*----------------------------------------------------------------------------
4251 Dataflow ref information verification functions.
4253 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
4254 df_reg_chain_verify_unmarked (refs)
4255 df_refs_verify (ref*, ref*, bool)
4256 df_mws_verify (mw*, mw*, bool)
4257 df_insn_refs_verify (collection_rec, bb, insn, bool)
4258 df_bb_refs_verify (bb, refs, bool)
4260 df_exit_block_bitmap_verify (bool)
4261 df_entry_block_bitmap_verify (bool)
4263 ----------------------------------------------------------------------------*/
4266 /* Mark all refs in the reg chain. Verify that all of the registers
4267 are in the correct chain. */
4270 df_reg_chain_mark (df_ref refs, unsigned int regno,
4271 bool is_def, bool is_eq_use)
4273 unsigned int count = 0;
4275 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4277 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4279 /* If there are no def-use or use-def chains, make sure that all
4280 of the chains are clear. */
4282 gcc_assert (!DF_REF_CHAIN (ref));
4284 /* Check to make sure the ref is in the correct chain. */
4285 gcc_assert (DF_REF_REGNO (ref) == regno);
4287 gcc_assert (DF_REF_REG_DEF_P (ref));
4289 gcc_assert (!DF_REF_REG_DEF_P (ref));
4292 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4294 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4296 if (DF_REF_NEXT_REG (ref))
4297 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
4299 DF_REF_REG_MARK (ref);
4305 /* Verify that all of the registers in the chain are unmarked. */
4308 df_reg_chain_verify_unmarked (df_ref refs)
4311 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4312 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4316 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4319 df_refs_verify (df_ref *new_rec, df_ref *old_rec,
4322 while ((*new_rec) && (*old_rec))
4324 if (!df_ref_equal_p (*new_rec, *old_rec))
4332 /* Abort if fail is called from the function level verifier. If
4333 that is the context, mark this reg as being seem. */
4336 gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
4337 DF_REF_REG_UNMARK (*old_rec);
4345 gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4347 return ((*new_rec == NULL) && (*old_rec == NULL));
4352 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4355 df_mws_verify (struct df_mw_hardreg **new_rec, struct df_mw_hardreg **old_rec,
4358 while ((*new_rec) && (*old_rec))
4360 if (!df_mw_equal_p (*new_rec, *old_rec))
4372 gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4374 return ((*new_rec == NULL) && (*old_rec == NULL));
4379 /* Return true if the existing insn refs information is complete and
4380 correct. Otherwise (i.e. if there's any missing or extra refs),
4381 return the correct df_ref chain in REFS_RETURN.
4383 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4384 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4385 verification mode instead of the whole function, so unmark
4388 If ABORT_IF_FAIL is set, this function never returns false. */
4391 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4396 bool ret1, ret2, ret3, ret4;
4397 unsigned int uid = INSN_UID (insn);
4398 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4400 df_insn_refs_collect (collection_rec, bb, insn_info);
4402 if (!DF_INSN_UID_DEFS (uid))
4404 /* The insn_rec was created but it was never filled out. */
4411 /* Unfortunately we cannot opt out early if one of these is not
4412 right because the marks will not get cleared. */
4413 ret1 = df_refs_verify (collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4415 ret2 = df_refs_verify (collection_rec->use_vec, DF_INSN_UID_USES (uid),
4417 ret3 = df_refs_verify (collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4419 ret4 = df_mws_verify (collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4421 return (ret1 && ret2 && ret3 && ret4);
4425 /* Return true if all refs in the basic block are correct and complete.
4426 Due to df_ref_chain_verify, it will cause all refs
4427 that are verified to have DF_REF_MARK bit set. */
4430 df_bb_verify (basic_block bb)
4433 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4434 struct df_collection_rec collection_rec;
4436 memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4437 collection_rec.def_vec = XALLOCAVEC (df_ref, 1000);
4438 collection_rec.use_vec = XALLOCAVEC (df_ref, 1000);
4439 collection_rec.eq_use_vec = XALLOCAVEC (df_ref, 1000);
4440 collection_rec.mw_vec = XALLOCAVEC (struct df_mw_hardreg *, 100);
4442 gcc_assert (bb_info);
4444 /* Scan the block, one insn at a time, from beginning to end. */
4445 FOR_BB_INSNS_REVERSE (bb, insn)
4449 df_insn_refs_verify (&collection_rec, bb, insn, true);
4450 df_free_collection_rec (&collection_rec);
4453 /* Do the artificial defs and uses. */
4454 df_bb_refs_collect (&collection_rec, bb);
4455 df_refs_verify (collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4456 df_refs_verify (collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4457 df_free_collection_rec (&collection_rec);
4463 /* Returns true if the entry block has correct and complete df_ref set.
4464 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4467 df_entry_block_bitmap_verify (bool abort_if_fail)
4469 bitmap entry_block_defs = BITMAP_ALLOC (&df_bitmap_obstack);
4472 df_get_entry_block_def_set (entry_block_defs);
4474 is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4476 if (!is_eq && abort_if_fail)
4478 print_current_pass (stderr);
4479 fprintf (stderr, "entry_block_defs = ");
4480 df_print_regset (stderr, entry_block_defs);
4481 fprintf (stderr, "df->entry_block_defs = ");
4482 df_print_regset (stderr, df->entry_block_defs);
4486 BITMAP_FREE (entry_block_defs);
4492 /* Returns true if the exit block has correct and complete df_ref set.
4493 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4496 df_exit_block_bitmap_verify (bool abort_if_fail)
4498 bitmap exit_block_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4501 df_get_exit_block_use_set (exit_block_uses);
4503 is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4505 if (!is_eq && abort_if_fail)
4507 print_current_pass (stderr);
4508 fprintf (stderr, "exit_block_uses = ");
4509 df_print_regset (stderr, exit_block_uses);
4510 fprintf (stderr, "df->exit_block_uses = ");
4511 df_print_regset (stderr, df->exit_block_uses);
4515 BITMAP_FREE (exit_block_uses);
4521 /* Return true if df_ref information for all insns in all blocks are
4522 correct and complete. */
4525 df_scan_verify (void)
4529 bitmap regular_block_artificial_uses;
4530 bitmap eh_block_artificial_uses;
4535 /* Verification is a 4 step process. */
4537 /* (1) All of the refs are marked by going thru the reg chains. */
4538 for (i = 0; i < DF_REG_SIZE (df); i++)
4540 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4541 == DF_REG_DEF_COUNT(i));
4542 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4543 == DF_REG_USE_COUNT(i));
4544 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4545 == DF_REG_EQ_USE_COUNT(i));
4548 /* (2) There are various bitmaps whose value may change over the
4549 course of the compilation. This step recomputes them to make
4550 sure that they have not slipped out of date. */
4551 regular_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4552 eh_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4554 df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4555 df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4557 bitmap_ior_into (eh_block_artificial_uses,
4558 regular_block_artificial_uses);
4560 /* Check artificial_uses bitmaps didn't change. */
4561 gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4562 df->regular_block_artificial_uses));
4563 gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4564 df->eh_block_artificial_uses));
4566 BITMAP_FREE (regular_block_artificial_uses);
4567 BITMAP_FREE (eh_block_artificial_uses);
4569 /* Verify entry block and exit block. These only verify the bitmaps,
4570 the refs are verified in df_bb_verify. */
4571 df_entry_block_bitmap_verify (true);
4572 df_exit_block_bitmap_verify (true);
4574 /* (3) All of the insns in all of the blocks are traversed and the
4575 marks are cleared both in the artificial refs attached to the
4576 blocks and the real refs inside the insns. It is a failure to
4577 clear a mark that has not been set as this means that the ref in
4578 the block or insn was not in the reg chain. */
4583 /* (4) See if all reg chains are traversed a second time. This time
4584 a check is made that the marks are clear. A set mark would be a
4585 from a reg that is not in any insn or basic block. */
4587 for (i = 0; i < DF_REG_SIZE (df); i++)
4589 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4590 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4591 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));