* config/i386/i386.c (ix86_adjust_stack_and_probe_stack_clash): New.
[official-gcc.git] / gcc / df-scan.c
blob8ab3d716ea2975ed687e1e3cf61ab3233e378f63
1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999-2017 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "backend.h"
28 #include "target.h"
29 #include "rtl.h"
30 #include "tree.h"
31 #include "df.h"
32 #include "memmodel.h"
33 #include "tm_p.h"
34 #include "regs.h"
35 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
36 #include "dumpfile.h"
39 /* The set of hard registers in eliminables[i].from. */
41 static HARD_REG_SET elim_reg_set;
43 /* Initialize ur_in and ur_out as if all hard registers were partially
44 available. */
46 struct df_collection_rec
48 auto_vec<df_ref, 128> def_vec;
49 auto_vec<df_ref, 32> use_vec;
50 auto_vec<df_ref, 32> eq_use_vec;
51 auto_vec<df_mw_hardreg *, 32> mw_vec;
54 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
55 rtx, rtx *,
56 basic_block, struct df_insn_info *,
57 enum df_ref_type, int ref_flags);
58 static void df_def_record_1 (struct df_collection_rec *, rtx *,
59 basic_block, struct df_insn_info *,
60 int ref_flags);
61 static void df_defs_record (struct df_collection_rec *, rtx,
62 basic_block, struct df_insn_info *,
63 int ref_flags);
64 static void df_uses_record (struct df_collection_rec *,
65 rtx *, enum df_ref_type,
66 basic_block, struct df_insn_info *,
67 int ref_flags);
69 static void df_install_ref_incremental (df_ref);
70 static void df_insn_refs_collect (struct df_collection_rec*,
71 basic_block, struct df_insn_info *);
72 static void df_canonize_collection_rec (struct df_collection_rec *);
74 static void df_get_regular_block_artificial_uses (bitmap);
75 static void df_get_eh_block_artificial_uses (bitmap);
77 static void df_record_entry_block_defs (bitmap);
78 static void df_record_exit_block_uses (bitmap);
79 static void df_get_exit_block_use_set (bitmap);
80 static void df_get_entry_block_def_set (bitmap);
81 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
82 static void df_ref_chain_delete_du_chain (df_ref);
83 static void df_ref_chain_delete (df_ref);
85 static void df_refs_add_to_chains (struct df_collection_rec *,
86 basic_block, rtx_insn *, unsigned int);
88 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block,
89 rtx_insn *, bool);
90 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
91 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
92 static void df_install_ref (df_ref, struct df_reg_info *,
93 struct df_ref_info *, bool);
95 static int df_ref_compare (df_ref, df_ref);
96 static int df_ref_ptr_compare (const void *, const void *);
97 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
98 static int df_mw_ptr_compare (const void *, const void *);
100 static void df_insn_info_delete (unsigned int);
102 /* Indexed by hardware reg number, is true if that register is ever
103 used in the current function.
105 In df-scan.c, this is set up to record the hard regs used
106 explicitly. Reload adds in the hard regs used for holding pseudo
107 regs. Final uses it to generate the code in the function prologue
108 and epilogue to save and restore registers as needed. */
110 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
112 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
113 static const unsigned int copy_defs = 0x1;
114 static const unsigned int copy_uses = 0x2;
115 static const unsigned int copy_eq_uses = 0x4;
116 static const unsigned int copy_mw = 0x8;
117 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
118 | copy_mw;
120 /*----------------------------------------------------------------------------
121 SCANNING DATAFLOW PROBLEM
123 There are several ways in which scanning looks just like the other
124 dataflow problems. It shares the all the mechanisms for local info
125 as well as basic block info. Where it differs is when and how often
126 it gets run. It also has no need for the iterative solver.
127 ----------------------------------------------------------------------------*/
129 /* Problem data for the scanning dataflow function. */
130 struct df_scan_problem_data
132 object_allocator<df_base_ref> *ref_base_pool;
133 object_allocator<df_artificial_ref> *ref_artificial_pool;
134 object_allocator<df_regular_ref> *ref_regular_pool;
135 object_allocator<df_insn_info> *insn_pool;
136 object_allocator<df_reg_info> *reg_pool;
137 object_allocator<df_mw_hardreg> *mw_reg_pool;
139 bitmap_obstack reg_bitmaps;
140 bitmap_obstack insn_bitmaps;
143 /* Internal function to shut down the scanning problem. */
144 static void
145 df_scan_free_internal (void)
147 struct df_scan_problem_data *problem_data
148 = (struct df_scan_problem_data *) df_scan->problem_data;
150 free (df->def_info.refs);
151 free (df->def_info.begin);
152 free (df->def_info.count);
153 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
155 free (df->use_info.refs);
156 free (df->use_info.begin);
157 free (df->use_info.count);
158 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
160 free (df->def_regs);
161 df->def_regs = NULL;
162 free (df->use_regs);
163 df->use_regs = NULL;
164 free (df->eq_use_regs);
165 df->eq_use_regs = NULL;
166 df->regs_size = 0;
167 DF_REG_SIZE (df) = 0;
169 free (df->insns);
170 df->insns = NULL;
171 DF_INSN_SIZE () = 0;
173 free (df_scan->block_info);
174 df_scan->block_info = NULL;
175 df_scan->block_info_size = 0;
177 bitmap_clear (&df->hardware_regs_used);
178 bitmap_clear (&df->regular_block_artificial_uses);
179 bitmap_clear (&df->eh_block_artificial_uses);
180 BITMAP_FREE (df->entry_block_defs);
181 BITMAP_FREE (df->exit_block_uses);
182 bitmap_clear (&df->insns_to_delete);
183 bitmap_clear (&df->insns_to_rescan);
184 bitmap_clear (&df->insns_to_notes_rescan);
186 delete problem_data->ref_base_pool;
187 delete problem_data->ref_artificial_pool;
188 delete problem_data->ref_regular_pool;
189 delete problem_data->insn_pool;
190 delete problem_data->reg_pool;
191 delete problem_data->mw_reg_pool;
192 bitmap_obstack_release (&problem_data->reg_bitmaps);
193 bitmap_obstack_release (&problem_data->insn_bitmaps);
194 free (df_scan->problem_data);
198 /* Free basic block info. */
200 static void
201 df_scan_free_bb_info (basic_block bb, void *vbb_info)
203 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
204 unsigned int bb_index = bb->index;
205 rtx_insn *insn;
207 FOR_BB_INSNS (bb, insn)
208 if (INSN_P (insn))
209 df_insn_info_delete (INSN_UID (insn));
211 if (bb_index < df_scan->block_info_size)
212 bb_info = df_scan_get_bb_info (bb_index);
214 /* Get rid of any artificial uses or defs. */
215 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
216 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
217 df_ref_chain_delete (bb_info->artificial_defs);
218 df_ref_chain_delete (bb_info->artificial_uses);
219 bb_info->artificial_defs = NULL;
220 bb_info->artificial_uses = NULL;
224 /* Allocate the problem data for the scanning problem. This should be
225 called when the problem is created or when the entire function is to
226 be rescanned. */
227 void
228 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
230 struct df_scan_problem_data *problem_data;
231 unsigned int insn_num = get_max_uid () + 1;
232 basic_block bb;
234 /* Given the number of pools, this is really faster than tearing
235 everything apart. */
236 if (df_scan->problem_data)
237 df_scan_free_internal ();
239 problem_data = XNEW (struct df_scan_problem_data);
240 df_scan->problem_data = problem_data;
241 df_scan->computed = true;
243 problem_data->ref_base_pool = new object_allocator<df_base_ref>
244 ("df_scan ref base");
245 problem_data->ref_artificial_pool = new object_allocator<df_artificial_ref>
246 ("df_scan ref artificial");
247 problem_data->ref_regular_pool = new object_allocator<df_regular_ref>
248 ("df_scan ref regular");
249 problem_data->insn_pool = new object_allocator<df_insn_info>
250 ("df_scan insn");
251 problem_data->reg_pool = new object_allocator<df_reg_info>
252 ("df_scan reg");
253 problem_data->mw_reg_pool = new object_allocator<df_mw_hardreg>
254 ("df_scan mw_reg");
256 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
257 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
259 insn_num += insn_num / 4;
260 df_grow_reg_info ();
262 df_grow_insn_info ();
263 df_grow_bb_info (df_scan);
265 FOR_ALL_BB_FN (bb, cfun)
267 unsigned int bb_index = bb->index;
268 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
269 bb_info->artificial_defs = NULL;
270 bb_info->artificial_uses = NULL;
273 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
274 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
275 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
276 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
277 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
278 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
279 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
280 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
281 df_scan->optional_p = false;
285 /* Free all of the data associated with the scan problem. */
287 static void
288 df_scan_free (void)
290 if (df_scan->problem_data)
291 df_scan_free_internal ();
293 if (df->blocks_to_analyze)
295 BITMAP_FREE (df->blocks_to_analyze);
296 df->blocks_to_analyze = NULL;
299 free (df_scan);
302 /* Dump the preamble for DF_SCAN dump. */
303 static void
304 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
306 int i;
307 int dcount = 0;
308 int ucount = 0;
309 int ecount = 0;
310 int icount = 0;
311 int ccount = 0;
312 basic_block bb;
313 rtx_insn *insn;
315 fprintf (file, ";; invalidated by call \t");
316 df_print_regset (file, regs_invalidated_by_call_regset);
317 fprintf (file, ";; hardware regs used \t");
318 df_print_regset (file, &df->hardware_regs_used);
319 fprintf (file, ";; regular block artificial uses \t");
320 df_print_regset (file, &df->regular_block_artificial_uses);
321 fprintf (file, ";; eh block artificial uses \t");
322 df_print_regset (file, &df->eh_block_artificial_uses);
323 fprintf (file, ";; entry block defs \t");
324 df_print_regset (file, df->entry_block_defs);
325 fprintf (file, ";; exit block uses \t");
326 df_print_regset (file, df->exit_block_uses);
327 fprintf (file, ";; regs ever live \t");
328 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
329 if (df_regs_ever_live_p (i))
330 fprintf (file, " %d [%s]", i, reg_names[i]);
331 fprintf (file, "\n;; ref usage \t");
333 for (i = 0; i < (int)df->regs_inited; i++)
334 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
336 const char * sep = "";
338 fprintf (file, "r%d={", i);
339 if (DF_REG_DEF_COUNT (i))
341 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
342 sep = ",";
343 dcount += DF_REG_DEF_COUNT (i);
345 if (DF_REG_USE_COUNT (i))
347 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
348 sep = ",";
349 ucount += DF_REG_USE_COUNT (i);
351 if (DF_REG_EQ_USE_COUNT (i))
353 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
354 ecount += DF_REG_EQ_USE_COUNT (i);
356 fprintf (file, "} ");
359 FOR_EACH_BB_FN (bb, cfun)
360 FOR_BB_INSNS (bb, insn)
361 if (INSN_P (insn))
363 if (CALL_P (insn))
364 ccount++;
365 else
366 icount++;
369 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
370 " in %d{%d regular + %d call} insns.\n",
371 dcount + ucount + ecount, dcount, ucount, ecount,
372 icount + ccount, icount, ccount);
375 /* Dump the bb_info for a given basic block. */
376 static void
377 df_scan_start_block (basic_block bb, FILE *file)
379 struct df_scan_bb_info *bb_info
380 = df_scan_get_bb_info (bb->index);
382 if (bb_info)
384 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
385 df_refs_chain_dump (bb_info->artificial_defs, true, file);
386 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
387 df_refs_chain_dump (bb_info->artificial_uses, true, file);
388 fprintf (file, "\n");
390 #if 0
392 rtx_insn *insn;
393 FOR_BB_INSNS (bb, insn)
394 if (INSN_P (insn))
395 df_insn_debug (insn, false, file);
397 #endif
400 static const struct df_problem problem_SCAN =
402 DF_SCAN, /* Problem id. */
403 DF_NONE, /* Direction. */
404 df_scan_alloc, /* Allocate the problem specific data. */
405 NULL, /* Reset global information. */
406 df_scan_free_bb_info, /* Free basic block info. */
407 NULL, /* Local compute function. */
408 NULL, /* Init the solution specific data. */
409 NULL, /* Iterative solver. */
410 NULL, /* Confluence operator 0. */
411 NULL, /* Confluence operator n. */
412 NULL, /* Transfer function. */
413 NULL, /* Finalize function. */
414 df_scan_free, /* Free all of the problem information. */
415 NULL, /* Remove this problem from the stack of dataflow problems. */
416 df_scan_start_dump, /* Debugging. */
417 df_scan_start_block, /* Debugging start block. */
418 NULL, /* Debugging end block. */
419 NULL, /* Debugging start insn. */
420 NULL, /* Debugging end insn. */
421 NULL, /* Incremental solution verify start. */
422 NULL, /* Incremental solution verify end. */
423 NULL, /* Dependent problem. */
424 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
425 TV_DF_SCAN, /* Timing variable. */
426 false /* Reset blocks on dropping out of blocks_to_analyze. */
430 /* Create a new DATAFLOW instance and add it to an existing instance
431 of DF. The returned structure is what is used to get at the
432 solution. */
434 void
435 df_scan_add_problem (void)
437 df_add_problem (&problem_SCAN);
441 /*----------------------------------------------------------------------------
442 Storage Allocation Utilities
443 ----------------------------------------------------------------------------*/
446 /* First, grow the reg_info information. If the current size is less than
447 the number of pseudos, grow to 25% more than the number of
448 pseudos.
450 Second, assure that all of the slots up to max_reg_num have been
451 filled with reg_info structures. */
453 void
454 df_grow_reg_info (void)
456 unsigned int max_reg = max_reg_num ();
457 unsigned int new_size = max_reg;
458 struct df_scan_problem_data *problem_data
459 = (struct df_scan_problem_data *) df_scan->problem_data;
460 unsigned int i;
462 if (df->regs_size < new_size)
464 new_size += new_size / 4;
465 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
466 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
467 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
468 new_size);
469 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
470 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
471 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
472 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
473 df->regs_size = new_size;
476 for (i = df->regs_inited; i < max_reg; i++)
478 struct df_reg_info *reg_info;
480 // TODO
481 reg_info = problem_data->reg_pool->allocate ();
482 memset (reg_info, 0, sizeof (struct df_reg_info));
483 df->def_regs[i] = reg_info;
484 reg_info = problem_data->reg_pool->allocate ();
485 memset (reg_info, 0, sizeof (struct df_reg_info));
486 df->use_regs[i] = reg_info;
487 reg_info = problem_data->reg_pool->allocate ();
488 memset (reg_info, 0, sizeof (struct df_reg_info));
489 df->eq_use_regs[i] = reg_info;
490 df->def_info.begin[i] = 0;
491 df->def_info.count[i] = 0;
492 df->use_info.begin[i] = 0;
493 df->use_info.count[i] = 0;
496 df->regs_inited = max_reg;
500 /* Grow the ref information. */
502 static void
503 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
505 if (ref_info->refs_size < new_size)
507 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
508 memset (ref_info->refs + ref_info->refs_size, 0,
509 (new_size - ref_info->refs_size) *sizeof (df_ref));
510 ref_info->refs_size = new_size;
515 /* Check and grow the ref information if necessary. This routine
516 guarantees total_size + BITMAP_ADDEND amount of entries in refs
517 array. It updates ref_info->refs_size only and does not change
518 ref_info->total_size. */
520 static void
521 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
522 unsigned bitmap_addend)
524 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
526 int new_size = ref_info->total_size + bitmap_addend;
527 new_size += ref_info->total_size / 4;
528 df_grow_ref_info (ref_info, new_size);
533 /* Grow the ref information. If the current size is less than the
534 number of instructions, grow to 25% more than the number of
535 instructions. */
537 void
538 df_grow_insn_info (void)
540 unsigned int new_size = get_max_uid () + 1;
541 if (DF_INSN_SIZE () < new_size)
543 new_size += new_size / 4;
544 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
545 memset (df->insns + df->insns_size, 0,
546 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
547 DF_INSN_SIZE () = new_size;
554 /*----------------------------------------------------------------------------
555 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
556 ----------------------------------------------------------------------------*/
558 /* Rescan all of the block_to_analyze or all of the blocks in the
559 function if df_set_blocks if blocks_to_analyze is NULL; */
561 void
562 df_scan_blocks (void)
564 basic_block bb;
566 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
567 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
569 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
570 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
572 bitmap_ior_into (&df->eh_block_artificial_uses,
573 &df->regular_block_artificial_uses);
575 /* ENTRY and EXIT blocks have special defs/uses. */
576 df_get_entry_block_def_set (df->entry_block_defs);
577 df_record_entry_block_defs (df->entry_block_defs);
578 df_get_exit_block_use_set (df->exit_block_uses);
579 df_record_exit_block_uses (df->exit_block_uses);
580 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
581 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
583 /* Regular blocks */
584 FOR_EACH_BB_FN (bb, cfun)
586 unsigned int bb_index = bb->index;
587 df_bb_refs_record (bb_index, true);
591 /* Create new refs under address LOC within INSN. This function is
592 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
593 depending on whether LOC is inside PATTERN (INSN) or a note. */
595 void
596 df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
598 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
599 df_uses_record (NULL, loc, DF_REF_REG_USE,
600 BLOCK_FOR_INSN (insn),
601 DF_INSN_INFO_GET (insn),
602 ref_flags);
605 static void
606 df_install_ref_incremental (df_ref ref)
608 struct df_reg_info **reg_info;
609 struct df_ref_info *ref_info;
610 df_ref *ref_ptr;
611 bool add_to_table;
613 rtx_insn *insn = DF_REF_INSN (ref);
614 basic_block bb = BLOCK_FOR_INSN (insn);
616 if (DF_REF_REG_DEF_P (ref))
618 reg_info = df->def_regs;
619 ref_info = &df->def_info;
620 ref_ptr = &DF_INSN_DEFS (insn);
621 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
623 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
625 reg_info = df->eq_use_regs;
626 ref_info = &df->use_info;
627 ref_ptr = &DF_INSN_EQ_USES (insn);
628 switch (ref_info->ref_order)
630 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
631 case DF_REF_ORDER_BY_REG_WITH_NOTES:
632 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
633 add_to_table = true;
634 break;
635 default:
636 add_to_table = false;
637 break;
640 else
642 reg_info = df->use_regs;
643 ref_info = &df->use_info;
644 ref_ptr = &DF_INSN_USES (insn);
645 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
648 /* Do not add if ref is not in the right blocks. */
649 if (add_to_table && df->analyze_subset)
650 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
652 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
654 if (add_to_table)
655 switch (ref_info->ref_order)
657 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
658 case DF_REF_ORDER_BY_REG_WITH_NOTES:
659 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
660 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
661 break;
662 default:
663 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
664 break;
667 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
668 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
670 DF_REF_NEXT_LOC (ref) = *ref_ptr;
671 *ref_ptr = ref;
673 #if 0
674 if (dump_file)
676 fprintf (dump_file, "adding ref ");
677 df_ref_debug (ref, dump_file);
679 #endif
680 /* By adding the ref directly, df_insn_rescan my not find any
681 differences even though the block will have changed. So we need
682 to mark the block dirty ourselves. */
683 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
684 df_set_bb_dirty (bb);
689 /*----------------------------------------------------------------------------
690 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
691 ----------------------------------------------------------------------------*/
693 static void
694 df_free_ref (df_ref ref)
696 struct df_scan_problem_data *problem_data
697 = (struct df_scan_problem_data *) df_scan->problem_data;
699 switch (DF_REF_CLASS (ref))
701 case DF_REF_BASE:
702 problem_data->ref_base_pool->remove ((df_base_ref *) (ref));
703 break;
705 case DF_REF_ARTIFICIAL:
706 problem_data->ref_artificial_pool->remove
707 ((df_artificial_ref *) (ref));
708 break;
710 case DF_REF_REGULAR:
711 problem_data->ref_regular_pool->remove
712 ((df_regular_ref *) (ref));
713 break;
718 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
719 Also delete the def-use or use-def chain if it exists. */
721 static void
722 df_reg_chain_unlink (df_ref ref)
724 df_ref next = DF_REF_NEXT_REG (ref);
725 df_ref prev = DF_REF_PREV_REG (ref);
726 int id = DF_REF_ID (ref);
727 struct df_reg_info *reg_info;
728 df_ref *refs = NULL;
730 if (DF_REF_REG_DEF_P (ref))
732 int regno = DF_REF_REGNO (ref);
733 reg_info = DF_REG_DEF_GET (regno);
734 refs = df->def_info.refs;
736 else
738 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
740 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
741 switch (df->use_info.ref_order)
743 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
744 case DF_REF_ORDER_BY_REG_WITH_NOTES:
745 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
746 refs = df->use_info.refs;
747 break;
748 default:
749 break;
752 else
754 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
755 refs = df->use_info.refs;
759 if (refs)
761 if (df->analyze_subset)
763 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
764 refs[id] = NULL;
766 else
767 refs[id] = NULL;
770 /* Delete any def-use or use-def chains that start here. It is
771 possible that there is trash in this field. This happens for
772 insns that have been deleted when rescanning has been deferred
773 and the chain problem has also been deleted. The chain tear down
774 code skips deleted insns. */
775 if (df_chain && DF_REF_CHAIN (ref))
776 df_chain_unlink (ref);
778 reg_info->n_refs--;
779 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
781 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
782 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
785 /* Unlink from the reg chain. If there is no prev, this is the
786 first of the list. If not, just join the next and prev. */
787 if (prev)
788 DF_REF_NEXT_REG (prev) = next;
789 else
791 gcc_assert (reg_info->reg_chain == ref);
792 reg_info->reg_chain = next;
794 if (next)
795 DF_REF_PREV_REG (next) = prev;
797 df_free_ref (ref);
800 /* Initialize INSN_INFO to describe INSN. */
802 static void
803 df_insn_info_init_fields (df_insn_info *insn_info, rtx_insn *insn)
805 memset (insn_info, 0, sizeof (struct df_insn_info));
806 insn_info->insn = insn;
809 /* Create the insn record for INSN. If there was one there, zero it
810 out. */
812 struct df_insn_info *
813 df_insn_create_insn_record (rtx_insn *insn)
815 struct df_scan_problem_data *problem_data
816 = (struct df_scan_problem_data *) df_scan->problem_data;
817 struct df_insn_info *insn_rec;
819 df_grow_insn_info ();
820 insn_rec = DF_INSN_INFO_GET (insn);
821 if (!insn_rec)
823 insn_rec = problem_data->insn_pool->allocate ();
824 DF_INSN_INFO_SET (insn, insn_rec);
826 df_insn_info_init_fields (insn_rec, insn);
827 return insn_rec;
831 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
833 static void
834 df_ref_chain_delete_du_chain (df_ref ref)
836 for (; ref; ref = DF_REF_NEXT_LOC (ref))
837 /* CHAIN is allocated by DF_CHAIN. So make sure to
838 pass df_scan instance for the problem. */
839 if (DF_REF_CHAIN (ref))
840 df_chain_unlink (ref);
844 /* Delete all refs in the ref chain. */
846 static void
847 df_ref_chain_delete (df_ref ref)
849 df_ref next;
850 for (; ref; ref = next)
852 next = DF_REF_NEXT_LOC (ref);
853 df_reg_chain_unlink (ref);
858 /* Delete the hardreg chain. */
860 static void
861 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
863 struct df_scan_problem_data *problem_data
864 = (struct df_scan_problem_data *) df_scan->problem_data;
865 df_mw_hardreg *next;
867 for (; hardregs; hardregs = next)
869 next = DF_MWS_NEXT (hardregs);
870 problem_data->mw_reg_pool->remove (hardregs);
874 /* Remove the contents of INSN_INFO (but don't free INSN_INFO itself). */
876 static void
877 df_insn_info_free_fields (df_insn_info *insn_info)
879 /* In general, notes do not have the insn_info fields
880 initialized. However, combine deletes insns by changing them
881 to notes. How clever. So we cannot just check if it is a
882 valid insn before short circuiting this code, we need to see
883 if we actually initialized it. */
884 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
886 if (df_chain)
888 df_ref_chain_delete_du_chain (insn_info->defs);
889 df_ref_chain_delete_du_chain (insn_info->uses);
890 df_ref_chain_delete_du_chain (insn_info->eq_uses);
893 df_ref_chain_delete (insn_info->defs);
894 df_ref_chain_delete (insn_info->uses);
895 df_ref_chain_delete (insn_info->eq_uses);
898 /* Delete all of the refs information from the insn with UID.
899 Internal helper for df_insn_delete, df_insn_rescan, and other
900 df-scan routines that don't have to work in deferred mode
901 and do not have to mark basic blocks for re-processing. */
903 static void
904 df_insn_info_delete (unsigned int uid)
906 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
908 bitmap_clear_bit (&df->insns_to_delete, uid);
909 bitmap_clear_bit (&df->insns_to_rescan, uid);
910 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
911 if (insn_info)
913 struct df_scan_problem_data *problem_data
914 = (struct df_scan_problem_data *) df_scan->problem_data;
916 df_insn_info_free_fields (insn_info);
917 problem_data->insn_pool->remove (insn_info);
918 DF_INSN_UID_SET (uid, NULL);
922 /* Delete all of the refs information from INSN, either right now
923 or marked for later in deferred mode. */
925 void
926 df_insn_delete (rtx_insn *insn)
928 unsigned int uid;
929 basic_block bb;
931 gcc_checking_assert (INSN_P (insn));
933 if (!df)
934 return;
936 uid = INSN_UID (insn);
937 bb = BLOCK_FOR_INSN (insn);
939 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
940 not exist anymore (as mentioned in df-core.c: "The only requirement
941 [for DF] is that there be a correct control flow graph." Clearly
942 that isn't the case after pass_free_cfg. But DF is freed much later
943 because some back-ends want to use DF info even though the CFG is
944 already gone. It's not clear to me whether that is safe, actually.
945 In any case, we expect BB to be non-NULL at least up to register
946 allocation, so disallow a non-NULL BB up to there. Not perfect
947 but better than nothing... */
948 gcc_checking_assert (bb != NULL || reload_completed);
950 df_grow_bb_info (df_scan);
951 df_grow_reg_info ();
953 /* The block must be marked as dirty now, rather than later as in
954 df_insn_rescan and df_notes_rescan because it may not be there at
955 rescanning time and the mark would blow up.
956 DEBUG_INSNs do not make a block's data flow solution dirty (at
957 worst the LUIDs are no longer contiguous). */
958 if (bb != NULL && NONDEBUG_INSN_P (insn))
959 df_set_bb_dirty (bb);
961 /* The client has deferred rescanning. */
962 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
964 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
965 if (insn_info)
967 bitmap_clear_bit (&df->insns_to_rescan, uid);
968 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
969 bitmap_set_bit (&df->insns_to_delete, uid);
971 if (dump_file)
972 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
973 return;
976 if (dump_file)
977 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
979 df_insn_info_delete (uid);
983 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
985 static void
986 df_free_collection_rec (struct df_collection_rec *collection_rec)
988 unsigned int ix;
989 struct df_scan_problem_data *problem_data
990 = (struct df_scan_problem_data *) df_scan->problem_data;
991 df_ref ref;
992 struct df_mw_hardreg *mw;
994 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
995 df_free_ref (ref);
996 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
997 df_free_ref (ref);
998 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
999 df_free_ref (ref);
1000 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1001 problem_data->mw_reg_pool->remove (mw);
1003 collection_rec->def_vec.release ();
1004 collection_rec->use_vec.release ();
1005 collection_rec->eq_use_vec.release ();
1006 collection_rec->mw_vec.release ();
1009 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1011 bool
1012 df_insn_rescan (rtx_insn *insn)
1014 unsigned int uid = INSN_UID (insn);
1015 struct df_insn_info *insn_info = NULL;
1016 basic_block bb = BLOCK_FOR_INSN (insn);
1017 struct df_collection_rec collection_rec;
1019 if ((!df) || (!INSN_P (insn)))
1020 return false;
1022 if (!bb)
1024 if (dump_file)
1025 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1026 return false;
1029 /* The client has disabled rescanning and plans to do it itself. */
1030 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1031 return false;
1033 df_grow_bb_info (df_scan);
1034 df_grow_reg_info ();
1036 insn_info = DF_INSN_UID_SAFE_GET (uid);
1038 /* The client has deferred rescanning. */
1039 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1041 if (!insn_info)
1043 insn_info = df_insn_create_insn_record (insn);
1044 insn_info->defs = 0;
1045 insn_info->uses = 0;
1046 insn_info->eq_uses = 0;
1047 insn_info->mw_hardregs = 0;
1049 if (dump_file)
1050 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1052 bitmap_clear_bit (&df->insns_to_delete, uid);
1053 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1054 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1055 return false;
1058 bitmap_clear_bit (&df->insns_to_delete, uid);
1059 bitmap_clear_bit (&df->insns_to_rescan, uid);
1060 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1061 if (insn_info)
1063 int luid;
1064 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1065 /* If there's no change, return false. */
1066 if (the_same)
1068 df_free_collection_rec (&collection_rec);
1069 if (dump_file)
1070 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1071 return false;
1073 if (dump_file)
1074 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1076 /* There's change - we need to delete the existing info.
1077 Since the insn isn't moved, we can salvage its LUID. */
1078 luid = DF_INSN_LUID (insn);
1079 df_insn_info_free_fields (insn_info);
1080 df_insn_info_init_fields (insn_info, insn);
1081 DF_INSN_LUID (insn) = luid;
1083 else
1085 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1086 df_insn_refs_collect (&collection_rec, bb, insn_info);
1087 if (dump_file)
1088 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1091 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1092 if (!DEBUG_INSN_P (insn))
1093 df_set_bb_dirty (bb);
1095 return true;
1098 /* Same as df_insn_rescan, but don't mark the basic block as
1099 dirty. */
1101 bool
1102 df_insn_rescan_debug_internal (rtx_insn *insn)
1104 unsigned int uid = INSN_UID (insn);
1105 struct df_insn_info *insn_info;
1107 gcc_assert (DEBUG_INSN_P (insn)
1108 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1110 if (!df)
1111 return false;
1113 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1114 if (!insn_info)
1115 return false;
1117 if (dump_file)
1118 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1120 bitmap_clear_bit (&df->insns_to_delete, uid);
1121 bitmap_clear_bit (&df->insns_to_rescan, uid);
1122 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1124 if (insn_info->defs == 0
1125 && insn_info->uses == 0
1126 && insn_info->eq_uses == 0
1127 && insn_info->mw_hardregs == 0)
1128 return false;
1130 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1132 if (df_chain)
1134 df_ref_chain_delete_du_chain (insn_info->defs);
1135 df_ref_chain_delete_du_chain (insn_info->uses);
1136 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1139 df_ref_chain_delete (insn_info->defs);
1140 df_ref_chain_delete (insn_info->uses);
1141 df_ref_chain_delete (insn_info->eq_uses);
1143 insn_info->defs = 0;
1144 insn_info->uses = 0;
1145 insn_info->eq_uses = 0;
1146 insn_info->mw_hardregs = 0;
1148 return true;
1152 /* Rescan all of the insns in the function. Note that the artificial
1153 uses and defs are not touched. This function will destroy def-use
1154 or use-def chains. */
1156 void
1157 df_insn_rescan_all (void)
1159 bool no_insn_rescan = false;
1160 bool defer_insn_rescan = false;
1161 basic_block bb;
1162 bitmap_iterator bi;
1163 unsigned int uid;
1165 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1167 df_clear_flags (DF_NO_INSN_RESCAN);
1168 no_insn_rescan = true;
1171 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1173 df_clear_flags (DF_DEFER_INSN_RESCAN);
1174 defer_insn_rescan = true;
1177 auto_bitmap tmp (&df_bitmap_obstack);
1178 bitmap_copy (tmp, &df->insns_to_delete);
1179 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1181 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1182 if (insn_info)
1183 df_insn_info_delete (uid);
1186 bitmap_clear (&df->insns_to_delete);
1187 bitmap_clear (&df->insns_to_rescan);
1188 bitmap_clear (&df->insns_to_notes_rescan);
1190 FOR_EACH_BB_FN (bb, cfun)
1192 rtx_insn *insn;
1193 FOR_BB_INSNS (bb, insn)
1195 df_insn_rescan (insn);
1199 if (no_insn_rescan)
1200 df_set_flags (DF_NO_INSN_RESCAN);
1201 if (defer_insn_rescan)
1202 df_set_flags (DF_DEFER_INSN_RESCAN);
1206 /* Process all of the deferred rescans or deletions. */
1208 void
1209 df_process_deferred_rescans (void)
1211 bool no_insn_rescan = false;
1212 bool defer_insn_rescan = false;
1213 bitmap_iterator bi;
1214 unsigned int uid;
1216 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1218 df_clear_flags (DF_NO_INSN_RESCAN);
1219 no_insn_rescan = true;
1222 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1224 df_clear_flags (DF_DEFER_INSN_RESCAN);
1225 defer_insn_rescan = true;
1228 if (dump_file)
1229 fprintf (dump_file, "starting the processing of deferred insns\n");
1231 auto_bitmap tmp (&df_bitmap_obstack);
1232 bitmap_copy (tmp, &df->insns_to_delete);
1233 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1235 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1236 if (insn_info)
1237 df_insn_info_delete (uid);
1240 bitmap_copy (tmp, &df->insns_to_rescan);
1241 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1243 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1244 if (insn_info)
1245 df_insn_rescan (insn_info->insn);
1248 bitmap_copy (tmp, &df->insns_to_notes_rescan);
1249 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1251 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1252 if (insn_info)
1253 df_notes_rescan (insn_info->insn);
1256 if (dump_file)
1257 fprintf (dump_file, "ending the processing of deferred insns\n");
1259 bitmap_clear (&df->insns_to_delete);
1260 bitmap_clear (&df->insns_to_rescan);
1261 bitmap_clear (&df->insns_to_notes_rescan);
1263 if (no_insn_rescan)
1264 df_set_flags (DF_NO_INSN_RESCAN);
1265 if (defer_insn_rescan)
1266 df_set_flags (DF_DEFER_INSN_RESCAN);
1268 /* If someone changed regs_ever_live during this pass, fix up the
1269 entry and exit blocks. */
1270 if (df->redo_entry_and_exit)
1272 df_update_entry_exit_and_calls ();
1273 df->redo_entry_and_exit = false;
1278 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1279 the uses if INCLUDE_USES. Include the eq_uses if
1280 INCLUDE_EQ_USES. */
1282 static unsigned int
1283 df_count_refs (bool include_defs, bool include_uses,
1284 bool include_eq_uses)
1286 unsigned int regno;
1287 int size = 0;
1288 unsigned int m = df->regs_inited;
1290 for (regno = 0; regno < m; regno++)
1292 if (include_defs)
1293 size += DF_REG_DEF_COUNT (regno);
1294 if (include_uses)
1295 size += DF_REG_USE_COUNT (regno);
1296 if (include_eq_uses)
1297 size += DF_REG_EQ_USE_COUNT (regno);
1299 return size;
1303 /* Take build ref table for either the uses or defs from the reg-use
1304 or reg-def chains. This version processes the refs in reg order
1305 which is likely to be best if processing the whole function. */
1307 static void
1308 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1309 bool include_defs,
1310 bool include_uses,
1311 bool include_eq_uses)
1313 unsigned int m = df->regs_inited;
1314 unsigned int regno;
1315 unsigned int offset = 0;
1316 unsigned int start;
1318 if (df->changeable_flags & DF_NO_HARD_REGS)
1320 start = FIRST_PSEUDO_REGISTER;
1321 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1322 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1324 else
1325 start = 0;
1327 ref_info->total_size
1328 = df_count_refs (include_defs, include_uses, include_eq_uses);
1330 df_check_and_grow_ref_info (ref_info, 1);
1332 for (regno = start; regno < m; regno++)
1334 int count = 0;
1335 ref_info->begin[regno] = offset;
1336 if (include_defs)
1338 df_ref ref = DF_REG_DEF_CHAIN (regno);
1339 while (ref)
1341 ref_info->refs[offset] = ref;
1342 DF_REF_ID (ref) = offset++;
1343 count++;
1344 ref = DF_REF_NEXT_REG (ref);
1345 gcc_checking_assert (offset < ref_info->refs_size);
1348 if (include_uses)
1350 df_ref ref = DF_REG_USE_CHAIN (regno);
1351 while (ref)
1353 ref_info->refs[offset] = ref;
1354 DF_REF_ID (ref) = offset++;
1355 count++;
1356 ref = DF_REF_NEXT_REG (ref);
1357 gcc_checking_assert (offset < ref_info->refs_size);
1360 if (include_eq_uses)
1362 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1363 while (ref)
1365 ref_info->refs[offset] = ref;
1366 DF_REF_ID (ref) = offset++;
1367 count++;
1368 ref = DF_REF_NEXT_REG (ref);
1369 gcc_checking_assert (offset < ref_info->refs_size);
1372 ref_info->count[regno] = count;
1375 /* The bitmap size is not decremented when refs are deleted. So
1376 reset it now that we have squished out all of the empty
1377 slots. */
1378 ref_info->table_size = offset;
1382 /* Take build ref table for either the uses or defs from the reg-use
1383 or reg-def chains. This version processes the refs in insn order
1384 which is likely to be best if processing some segment of the
1385 function. */
1387 static void
1388 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1389 bool include_defs,
1390 bool include_uses,
1391 bool include_eq_uses)
1393 bitmap_iterator bi;
1394 unsigned int bb_index;
1395 unsigned int m = df->regs_inited;
1396 unsigned int offset = 0;
1397 unsigned int r;
1398 unsigned int start
1399 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1401 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1402 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1404 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1405 df_check_and_grow_ref_info (ref_info, 1);
1407 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1409 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1410 rtx_insn *insn;
1411 df_ref def, use;
1413 if (include_defs)
1414 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1416 unsigned int regno = DF_REF_REGNO (def);
1417 ref_info->count[regno]++;
1419 if (include_uses)
1420 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1422 unsigned int regno = DF_REF_REGNO (use);
1423 ref_info->count[regno]++;
1426 FOR_BB_INSNS (bb, insn)
1428 if (INSN_P (insn))
1430 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1432 if (include_defs)
1433 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1435 unsigned int regno = DF_REF_REGNO (def);
1436 ref_info->count[regno]++;
1438 if (include_uses)
1439 FOR_EACH_INSN_INFO_USE (use, insn_info)
1441 unsigned int regno = DF_REF_REGNO (use);
1442 ref_info->count[regno]++;
1444 if (include_eq_uses)
1445 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1447 unsigned int regno = DF_REF_REGNO (use);
1448 ref_info->count[regno]++;
1454 for (r = start; r < m; r++)
1456 ref_info->begin[r] = offset;
1457 offset += ref_info->count[r];
1458 ref_info->count[r] = 0;
1461 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1463 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1464 rtx_insn *insn;
1465 df_ref def, use;
1467 if (include_defs)
1468 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1470 unsigned int regno = DF_REF_REGNO (def);
1471 if (regno >= start)
1473 unsigned int id
1474 = ref_info->begin[regno] + ref_info->count[regno]++;
1475 DF_REF_ID (def) = id;
1476 ref_info->refs[id] = def;
1479 if (include_uses)
1480 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1482 unsigned int regno = DF_REF_REGNO (def);
1483 if (regno >= start)
1485 unsigned int id
1486 = ref_info->begin[regno] + ref_info->count[regno]++;
1487 DF_REF_ID (use) = id;
1488 ref_info->refs[id] = use;
1492 FOR_BB_INSNS (bb, insn)
1494 if (INSN_P (insn))
1496 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1498 if (include_defs)
1499 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1501 unsigned int regno = DF_REF_REGNO (def);
1502 if (regno >= start)
1504 unsigned int id
1505 = ref_info->begin[regno] + ref_info->count[regno]++;
1506 DF_REF_ID (def) = id;
1507 ref_info->refs[id] = def;
1510 if (include_uses)
1511 FOR_EACH_INSN_INFO_USE (use, insn_info)
1513 unsigned int regno = DF_REF_REGNO (use);
1514 if (regno >= start)
1516 unsigned int id
1517 = ref_info->begin[regno] + ref_info->count[regno]++;
1518 DF_REF_ID (use) = id;
1519 ref_info->refs[id] = use;
1522 if (include_eq_uses)
1523 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1525 unsigned int regno = DF_REF_REGNO (use);
1526 if (regno >= start)
1528 unsigned int id
1529 = ref_info->begin[regno] + ref_info->count[regno]++;
1530 DF_REF_ID (use) = id;
1531 ref_info->refs[id] = use;
1538 /* The bitmap size is not decremented when refs are deleted. So
1539 reset it now that we have squished out all of the empty
1540 slots. */
1542 ref_info->table_size = offset;
1545 /* Take build ref table for either the uses or defs from the reg-use
1546 or reg-def chains. */
1548 static void
1549 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1550 bool include_defs,
1551 bool include_uses,
1552 bool include_eq_uses)
1554 if (df->analyze_subset)
1555 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1556 include_uses, include_eq_uses);
1557 else
1558 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1559 include_uses, include_eq_uses);
1563 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1564 static unsigned int
1565 df_add_refs_to_table (unsigned int offset,
1566 struct df_ref_info *ref_info,
1567 df_ref ref)
1569 for (; ref; ref = DF_REF_NEXT_LOC (ref))
1570 if (!(df->changeable_flags & DF_NO_HARD_REGS)
1571 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1573 ref_info->refs[offset] = ref;
1574 DF_REF_ID (ref) = offset++;
1576 return offset;
1580 /* Count the number of refs in all of the insns of BB. Include the
1581 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1582 eq_uses if INCLUDE_EQ_USES. */
1584 static unsigned int
1585 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1586 struct df_ref_info *ref_info,
1587 bool include_defs, bool include_uses,
1588 bool include_eq_uses)
1590 rtx_insn *insn;
1592 if (include_defs)
1593 offset = df_add_refs_to_table (offset, ref_info,
1594 df_get_artificial_defs (bb->index));
1595 if (include_uses)
1596 offset = df_add_refs_to_table (offset, ref_info,
1597 df_get_artificial_uses (bb->index));
1599 FOR_BB_INSNS (bb, insn)
1600 if (INSN_P (insn))
1602 unsigned int uid = INSN_UID (insn);
1603 if (include_defs)
1604 offset = df_add_refs_to_table (offset, ref_info,
1605 DF_INSN_UID_DEFS (uid));
1606 if (include_uses)
1607 offset = df_add_refs_to_table (offset, ref_info,
1608 DF_INSN_UID_USES (uid));
1609 if (include_eq_uses)
1610 offset = df_add_refs_to_table (offset, ref_info,
1611 DF_INSN_UID_EQ_USES (uid));
1613 return offset;
1617 /* Organize the refs by insn into the table in REF_INFO. If
1618 blocks_to_analyze is defined, use that set, otherwise the entire
1619 program. Include the defs if INCLUDE_DEFS. Include the uses if
1620 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1622 static void
1623 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1624 bool include_defs, bool include_uses,
1625 bool include_eq_uses)
1627 basic_block bb;
1628 unsigned int offset = 0;
1630 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1631 df_check_and_grow_ref_info (ref_info, 1);
1632 if (df->blocks_to_analyze)
1634 bitmap_iterator bi;
1635 unsigned int index;
1637 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1639 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1640 index),
1641 offset, ref_info,
1642 include_defs, include_uses,
1643 include_eq_uses);
1646 ref_info->table_size = offset;
1648 else
1650 FOR_ALL_BB_FN (bb, cfun)
1651 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1652 include_defs, include_uses,
1653 include_eq_uses);
1654 ref_info->table_size = offset;
1659 /* If the use refs in DF are not organized, reorganize them. */
1661 void
1662 df_maybe_reorganize_use_refs (enum df_ref_order order)
1664 if (order == df->use_info.ref_order)
1665 return;
1667 switch (order)
1669 case DF_REF_ORDER_BY_REG:
1670 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1671 break;
1673 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1674 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1675 break;
1677 case DF_REF_ORDER_BY_INSN:
1678 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1679 break;
1681 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1682 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1683 break;
1685 case DF_REF_ORDER_NO_TABLE:
1686 free (df->use_info.refs);
1687 df->use_info.refs = NULL;
1688 df->use_info.refs_size = 0;
1689 break;
1691 case DF_REF_ORDER_UNORDERED:
1692 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1693 gcc_unreachable ();
1694 break;
1697 df->use_info.ref_order = order;
1701 /* If the def refs in DF are not organized, reorganize them. */
1703 void
1704 df_maybe_reorganize_def_refs (enum df_ref_order order)
1706 if (order == df->def_info.ref_order)
1707 return;
1709 switch (order)
1711 case DF_REF_ORDER_BY_REG:
1712 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1713 break;
1715 case DF_REF_ORDER_BY_INSN:
1716 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1717 break;
1719 case DF_REF_ORDER_NO_TABLE:
1720 free (df->def_info.refs);
1721 df->def_info.refs = NULL;
1722 df->def_info.refs_size = 0;
1723 break;
1725 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1726 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1727 case DF_REF_ORDER_UNORDERED:
1728 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1729 gcc_unreachable ();
1730 break;
1733 df->def_info.ref_order = order;
1737 /* Change all of the basic block references in INSN to use the insn's
1738 current basic block. This function is called from routines that move
1739 instructions from one block to another. */
1741 void
1742 df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1744 basic_block old_bb = BLOCK_FOR_INSN (insn);
1745 struct df_insn_info *insn_info;
1746 unsigned int uid = INSN_UID (insn);
1748 if (old_bb == new_bb)
1749 return;
1751 set_block_for_insn (insn, new_bb);
1753 if (!df)
1754 return;
1756 if (dump_file)
1757 fprintf (dump_file, "changing bb of uid %d\n", uid);
1759 insn_info = DF_INSN_UID_SAFE_GET (uid);
1760 if (insn_info == NULL)
1762 if (dump_file)
1763 fprintf (dump_file, " unscanned insn\n");
1764 df_insn_rescan (insn);
1765 return;
1768 if (!INSN_P (insn))
1769 return;
1771 df_set_bb_dirty (new_bb);
1772 if (old_bb)
1774 if (dump_file)
1775 fprintf (dump_file, " from %d to %d\n",
1776 old_bb->index, new_bb->index);
1777 df_set_bb_dirty (old_bb);
1779 else
1780 if (dump_file)
1781 fprintf (dump_file, " to %d\n", new_bb->index);
1785 /* Helper function for df_ref_change_reg_with_loc. */
1787 static void
1788 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1789 struct df_reg_info *new_df,
1790 unsigned int new_regno, rtx loc)
1792 df_ref the_ref = old_df->reg_chain;
1794 while (the_ref)
1796 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1797 && DF_REF_LOC (the_ref)
1798 && (*DF_REF_LOC (the_ref) == loc))
1800 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1801 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1802 df_ref *ref_ptr;
1803 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1805 DF_REF_REGNO (the_ref) = new_regno;
1806 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1808 /* Pull the_ref out of the old regno chain. */
1809 if (prev_ref)
1810 DF_REF_NEXT_REG (prev_ref) = next_ref;
1811 else
1812 old_df->reg_chain = next_ref;
1813 if (next_ref)
1814 DF_REF_PREV_REG (next_ref) = prev_ref;
1815 old_df->n_refs--;
1817 /* Put the ref into the new regno chain. */
1818 DF_REF_PREV_REG (the_ref) = NULL;
1819 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1820 if (new_df->reg_chain)
1821 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1822 new_df->reg_chain = the_ref;
1823 new_df->n_refs++;
1824 if (DF_REF_BB (the_ref))
1825 df_set_bb_dirty (DF_REF_BB (the_ref));
1827 /* Need to sort the record again that the ref was in because
1828 the regno is a sorting key. First, find the right
1829 record. */
1830 if (DF_REF_REG_DEF_P (the_ref))
1831 ref_ptr = &insn_info->defs;
1832 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1833 ref_ptr = &insn_info->eq_uses;
1834 else
1835 ref_ptr = &insn_info->uses;
1836 if (dump_file)
1837 fprintf (dump_file, "changing reg in insn %d\n",
1838 DF_REF_INSN_UID (the_ref));
1840 /* Stop if we find the current reference or where the reference
1841 needs to be. */
1842 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1843 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1844 if (*ref_ptr != the_ref)
1846 /* The reference needs to be promoted up the list. */
1847 df_ref next = DF_REF_NEXT_LOC (the_ref);
1848 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1849 *ref_ptr = the_ref;
1851 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1852 while (*ref_ptr != the_ref);
1853 *ref_ptr = next;
1855 else if (DF_REF_NEXT_LOC (the_ref)
1856 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1858 /* The reference needs to be demoted down the list. */
1859 *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1861 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1862 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1863 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1864 *ref_ptr = the_ref;
1867 the_ref = next_ref;
1869 else
1870 the_ref = DF_REF_NEXT_REG (the_ref);
1875 /* Change the regno of register LOC to NEW_REGNO and update the df
1876 information accordingly. Refs that do not match LOC are not changed
1877 which means that artificial refs are not changed since they have no loc.
1878 This call is to support the SET_REGNO macro. */
1880 void
1881 df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1883 unsigned int old_regno = REGNO (loc);
1884 if (old_regno == new_regno)
1885 return;
1887 if (df)
1889 df_grow_reg_info ();
1891 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1892 DF_REG_DEF_GET (new_regno),
1893 new_regno, loc);
1894 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1895 DF_REG_USE_GET (new_regno),
1896 new_regno, loc);
1897 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1898 DF_REG_EQ_USE_GET (new_regno),
1899 new_regno, loc);
1901 set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1905 /* Delete the mw_hardregs that point into the eq_notes. */
1907 static void
1908 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1910 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1911 struct df_scan_problem_data *problem_data
1912 = (struct df_scan_problem_data *) df_scan->problem_data;
1914 while (*mw_ptr)
1916 df_mw_hardreg *mw = *mw_ptr;
1917 if (mw->flags & DF_REF_IN_NOTE)
1919 *mw_ptr = DF_MWS_NEXT (mw);
1920 problem_data->mw_reg_pool->remove (mw);
1922 else
1923 mw_ptr = &DF_MWS_NEXT (mw);
1928 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1930 void
1931 df_notes_rescan (rtx_insn *insn)
1933 struct df_insn_info *insn_info;
1934 unsigned int uid = INSN_UID (insn);
1936 if (!df)
1937 return;
1939 /* The client has disabled rescanning and plans to do it itself. */
1940 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1941 return;
1943 /* Do nothing if the insn hasn't been emitted yet. */
1944 if (!BLOCK_FOR_INSN (insn))
1945 return;
1947 df_grow_bb_info (df_scan);
1948 df_grow_reg_info ();
1950 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1952 /* The client has deferred rescanning. */
1953 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1955 if (!insn_info)
1957 insn_info = df_insn_create_insn_record (insn);
1958 insn_info->defs = 0;
1959 insn_info->uses = 0;
1960 insn_info->eq_uses = 0;
1961 insn_info->mw_hardregs = 0;
1964 bitmap_clear_bit (&df->insns_to_delete, uid);
1965 /* If the insn is set to be rescanned, it does not need to also
1966 be notes rescanned. */
1967 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1968 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1969 return;
1972 bitmap_clear_bit (&df->insns_to_delete, uid);
1973 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1975 if (insn_info)
1977 basic_block bb = BLOCK_FOR_INSN (insn);
1978 rtx note;
1979 struct df_collection_rec collection_rec;
1980 unsigned int i;
1982 df_mw_hardreg_chain_delete_eq_uses (insn_info);
1983 df_ref_chain_delete (insn_info->eq_uses);
1984 insn_info->eq_uses = NULL;
1986 /* Process REG_EQUIV/REG_EQUAL notes */
1987 for (note = REG_NOTES (insn); note;
1988 note = XEXP (note, 1))
1990 switch (REG_NOTE_KIND (note))
1992 case REG_EQUIV:
1993 case REG_EQUAL:
1994 df_uses_record (&collection_rec,
1995 &XEXP (note, 0), DF_REF_REG_USE,
1996 bb, insn_info, DF_REF_IN_NOTE);
1997 default:
1998 break;
2002 /* Find some place to put any new mw_hardregs. */
2003 df_canonize_collection_rec (&collection_rec);
2004 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2005 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2007 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2008 mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2009 DF_MWS_NEXT (mw) = *mw_ptr;
2010 *mw_ptr = mw;
2011 mw_ptr = &DF_MWS_NEXT (mw);
2013 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2015 else
2016 df_insn_rescan (insn);
2021 /*----------------------------------------------------------------------------
2022 Hard core instruction scanning code. No external interfaces here,
2023 just a lot of routines that look inside insns.
2024 ----------------------------------------------------------------------------*/
2027 /* Return true if the contents of two df_ref's are identical.
2028 It ignores DF_REF_MARKER. */
2030 static bool
2031 df_ref_equal_p (df_ref ref1, df_ref ref2)
2033 if (!ref2)
2034 return false;
2036 if (ref1 == ref2)
2037 return true;
2039 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2040 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2041 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2042 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2043 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2044 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2045 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2046 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2047 return false;
2049 switch (DF_REF_CLASS (ref1))
2051 case DF_REF_ARTIFICIAL:
2052 case DF_REF_BASE:
2053 return true;
2055 case DF_REF_REGULAR:
2056 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2058 default:
2059 gcc_unreachable ();
2061 return false;
2065 /* Compare REF1 and REF2 for sorting. This is only called from places
2066 where all of the refs are of the same type, in the same insn, and
2067 have the same bb. So these fields are not checked. */
2069 static int
2070 df_ref_compare (df_ref ref1, df_ref ref2)
2072 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2073 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2075 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2076 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2078 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2079 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2081 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2082 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2084 /* Cannot look at the LOC field on artificial refs. */
2085 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2086 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2087 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2089 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2091 /* If two refs are identical except that one of them has is from
2092 a mw and one is not, we need to have the one with the mw
2093 first. */
2094 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2095 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2096 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2097 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2098 return -1;
2099 else
2100 return 1;
2103 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2106 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2108 static int
2109 df_ref_ptr_compare (const void *r1, const void *r2)
2111 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2114 /* Sort and compress a set of refs. */
2116 static void
2117 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2119 unsigned int count;
2120 unsigned int i;
2121 unsigned int dist = 0;
2123 count = ref_vec->length ();
2125 /* If there are 1 or 0 elements, there is nothing to do. */
2126 if (count < 2)
2127 return;
2128 else if (count == 2)
2130 df_ref r0 = (*ref_vec)[0];
2131 df_ref r1 = (*ref_vec)[1];
2132 if (df_ref_compare (r0, r1) > 0)
2133 std::swap ((*ref_vec)[0], (*ref_vec)[1]);
2135 else
2137 for (i = 0; i < count - 1; i++)
2139 df_ref r0 = (*ref_vec)[i];
2140 df_ref r1 = (*ref_vec)[i + 1];
2141 if (df_ref_compare (r0, r1) >= 0)
2142 break;
2144 /* If the array is already strictly ordered,
2145 which is the most common case for large COUNT case
2146 (which happens for CALL INSNs),
2147 no need to sort and filter out duplicate.
2148 Simply return the count.
2149 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2150 of DF_REF_COMPARE. */
2151 if (i == count - 1)
2152 return;
2153 ref_vec->qsort (df_ref_ptr_compare);
2156 for (i=0; i<count-dist; i++)
2158 /* Find the next ref that is not equal to the current ref. */
2159 while (i + dist + 1 < count
2160 && df_ref_equal_p ((*ref_vec)[i],
2161 (*ref_vec)[i + dist + 1]))
2163 df_free_ref ((*ref_vec)[i + dist + 1]);
2164 dist++;
2166 /* Copy it down to the next position. */
2167 if (dist && i + dist + 1 < count)
2168 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2171 count -= dist;
2172 ref_vec->truncate (count);
2176 /* Return true if the contents of two df_ref's are identical.
2177 It ignores DF_REF_MARKER. */
2179 static bool
2180 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2182 if (!mw2)
2183 return false;
2184 return (mw1 == mw2) ||
2185 (mw1->mw_reg == mw2->mw_reg
2186 && mw1->type == mw2->type
2187 && mw1->flags == mw2->flags
2188 && mw1->start_regno == mw2->start_regno
2189 && mw1->end_regno == mw2->end_regno);
2193 /* Compare MW1 and MW2 for sorting. */
2195 static int
2196 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2198 if (mw1->type != mw2->type)
2199 return mw1->type - mw2->type;
2201 if (mw1->flags != mw2->flags)
2202 return mw1->flags - mw2->flags;
2204 if (mw1->start_regno != mw2->start_regno)
2205 return mw1->start_regno - mw2->start_regno;
2207 if (mw1->end_regno != mw2->end_regno)
2208 return mw1->end_regno - mw2->end_regno;
2210 if (mw1->mw_reg != mw2->mw_reg)
2211 return mw1->mw_order - mw2->mw_order;
2213 return 0;
2216 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2218 static int
2219 df_mw_ptr_compare (const void *m1, const void *m2)
2221 return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2222 *(const df_mw_hardreg *const *) m2);
2225 /* Sort and compress a set of refs. */
2227 static void
2228 df_sort_and_compress_mws (vec<df_mw_hardreg *, va_heap> *mw_vec)
2230 unsigned int count;
2231 struct df_scan_problem_data *problem_data
2232 = (struct df_scan_problem_data *) df_scan->problem_data;
2233 unsigned int i;
2234 unsigned int dist = 0;
2236 count = mw_vec->length ();
2237 if (count < 2)
2238 return;
2239 else if (count == 2)
2241 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2242 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2243 if (df_mw_compare (m0, m1) > 0)
2245 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2246 (*mw_vec)[0] = (*mw_vec)[1];
2247 (*mw_vec)[1] = tmp;
2250 else
2251 mw_vec->qsort (df_mw_ptr_compare);
2253 for (i=0; i<count-dist; i++)
2255 /* Find the next ref that is not equal to the current ref. */
2256 while (i + dist + 1 < count
2257 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2259 problem_data->mw_reg_pool->remove ((*mw_vec)[i + dist + 1]);
2260 dist++;
2262 /* Copy it down to the next position. */
2263 if (dist && i + dist + 1 < count)
2264 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2267 count -= dist;
2268 mw_vec->truncate (count);
2272 /* Sort and remove duplicates from the COLLECTION_REC. */
2274 static void
2275 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2277 df_sort_and_compress_refs (&collection_rec->def_vec);
2278 df_sort_and_compress_refs (&collection_rec->use_vec);
2279 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2280 df_sort_and_compress_mws (&collection_rec->mw_vec);
2284 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2286 static void
2287 df_install_ref (df_ref this_ref,
2288 struct df_reg_info *reg_info,
2289 struct df_ref_info *ref_info,
2290 bool add_to_table)
2292 unsigned int regno = DF_REF_REGNO (this_ref);
2293 /* Add the ref to the reg_{def,use,eq_use} chain. */
2294 df_ref head = reg_info->reg_chain;
2296 reg_info->reg_chain = this_ref;
2297 reg_info->n_refs++;
2299 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2301 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2302 df->hard_regs_live_count[regno]++;
2305 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2306 && DF_REF_PREV_REG (this_ref) == NULL);
2308 DF_REF_NEXT_REG (this_ref) = head;
2310 /* We cannot actually link to the head of the chain. */
2311 DF_REF_PREV_REG (this_ref) = NULL;
2313 if (head)
2314 DF_REF_PREV_REG (head) = this_ref;
2316 if (add_to_table)
2318 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2319 df_check_and_grow_ref_info (ref_info, 1);
2320 DF_REF_ID (this_ref) = ref_info->table_size;
2321 /* Add the ref to the big array of defs. */
2322 ref_info->refs[ref_info->table_size] = this_ref;
2323 ref_info->table_size++;
2325 else
2326 DF_REF_ID (this_ref) = -1;
2328 ref_info->total_size++;
2332 /* This function takes one of the groups of refs (defs, uses or
2333 eq_uses) and installs the entire group into the insn. It also adds
2334 each of these refs into the appropriate chains. */
2336 static df_ref
2337 df_install_refs (basic_block bb,
2338 const vec<df_ref, va_heap> *old_vec,
2339 struct df_reg_info **reg_info,
2340 struct df_ref_info *ref_info,
2341 bool is_notes)
2343 unsigned int count = old_vec->length ();
2344 if (count)
2346 bool add_to_table;
2347 df_ref this_ref;
2348 unsigned int ix;
2350 switch (ref_info->ref_order)
2352 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2353 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2354 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2355 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2356 add_to_table = true;
2357 break;
2358 case DF_REF_ORDER_UNORDERED:
2359 case DF_REF_ORDER_BY_REG:
2360 case DF_REF_ORDER_BY_INSN:
2361 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2362 add_to_table = !is_notes;
2363 break;
2364 default:
2365 add_to_table = false;
2366 break;
2369 /* Do not add if ref is not in the right blocks. */
2370 if (add_to_table && df->analyze_subset)
2371 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2373 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2375 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2376 ? (*old_vec)[ix + 1]
2377 : NULL);
2378 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2379 ref_info, add_to_table);
2381 return (*old_vec)[0];
2383 else
2384 return 0;
2388 /* This function takes the mws installs the entire group into the
2389 insn. */
2391 static struct df_mw_hardreg *
2392 df_install_mws (const vec<df_mw_hardreg *, va_heap> *old_vec)
2394 unsigned int count = old_vec->length ();
2395 if (count)
2397 for (unsigned int i = 0; i < count - 1; i++)
2398 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2399 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2400 return (*old_vec)[0];
2402 else
2403 return 0;
2407 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2408 chains and update other necessary information. */
2410 static void
2411 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2412 basic_block bb, rtx_insn *insn, unsigned int flags)
2414 if (insn)
2416 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2417 /* If there is a vector in the collection rec, add it to the
2418 insn. A null rec is a signal that the caller will handle the
2419 chain specially. */
2420 if (flags & copy_defs)
2422 gcc_checking_assert (!insn_rec->defs);
2423 insn_rec->defs
2424 = df_install_refs (bb, &collection_rec->def_vec,
2425 df->def_regs,
2426 &df->def_info, false);
2428 if (flags & copy_uses)
2430 gcc_checking_assert (!insn_rec->uses);
2431 insn_rec->uses
2432 = df_install_refs (bb, &collection_rec->use_vec,
2433 df->use_regs,
2434 &df->use_info, false);
2436 if (flags & copy_eq_uses)
2438 gcc_checking_assert (!insn_rec->eq_uses);
2439 insn_rec->eq_uses
2440 = df_install_refs (bb, &collection_rec->eq_use_vec,
2441 df->eq_use_regs,
2442 &df->use_info, true);
2444 if (flags & copy_mw)
2446 gcc_checking_assert (!insn_rec->mw_hardregs);
2447 insn_rec->mw_hardregs
2448 = df_install_mws (&collection_rec->mw_vec);
2451 else
2453 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2455 gcc_checking_assert (!bb_info->artificial_defs);
2456 bb_info->artificial_defs
2457 = df_install_refs (bb, &collection_rec->def_vec,
2458 df->def_regs,
2459 &df->def_info, false);
2460 gcc_checking_assert (!bb_info->artificial_uses);
2461 bb_info->artificial_uses
2462 = df_install_refs (bb, &collection_rec->use_vec,
2463 df->use_regs,
2464 &df->use_info, false);
2469 /* Allocate a ref and initialize its fields. */
2471 static df_ref
2472 df_ref_create_structure (enum df_ref_class cl,
2473 struct df_collection_rec *collection_rec,
2474 rtx reg, rtx *loc,
2475 basic_block bb, struct df_insn_info *info,
2476 enum df_ref_type ref_type,
2477 int ref_flags)
2479 df_ref this_ref = NULL;
2480 unsigned int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2481 struct df_scan_problem_data *problem_data
2482 = (struct df_scan_problem_data *) df_scan->problem_data;
2484 switch (cl)
2486 case DF_REF_BASE:
2487 this_ref = (df_ref) (problem_data->ref_base_pool->allocate ());
2488 gcc_checking_assert (loc == NULL);
2489 break;
2491 case DF_REF_ARTIFICIAL:
2492 this_ref = (df_ref) (problem_data->ref_artificial_pool->allocate ());
2493 this_ref->artificial_ref.bb = bb;
2494 gcc_checking_assert (loc == NULL);
2495 break;
2497 case DF_REF_REGULAR:
2498 this_ref = (df_ref) (problem_data->ref_regular_pool->allocate ());
2499 this_ref->regular_ref.loc = loc;
2500 gcc_checking_assert (loc);
2501 break;
2504 DF_REF_CLASS (this_ref) = cl;
2505 DF_REF_ID (this_ref) = -1;
2506 DF_REF_REG (this_ref) = reg;
2507 DF_REF_REGNO (this_ref) = regno;
2508 DF_REF_TYPE (this_ref) = ref_type;
2509 DF_REF_INSN_INFO (this_ref) = info;
2510 DF_REF_CHAIN (this_ref) = NULL;
2511 DF_REF_FLAGS (this_ref) = ref_flags;
2512 DF_REF_NEXT_REG (this_ref) = NULL;
2513 DF_REF_PREV_REG (this_ref) = NULL;
2514 DF_REF_ORDER (this_ref) = df->ref_order++;
2516 /* We need to clear this bit because fwprop, and in the future
2517 possibly other optimizations sometimes create new refs using ond
2518 refs as the model. */
2519 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2521 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2522 if (regno < FIRST_PSEUDO_REGISTER
2523 && !DF_REF_IS_ARTIFICIAL (this_ref)
2524 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2526 if (DF_REF_REG_DEF_P (this_ref))
2528 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2529 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2531 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2532 && (regno == FRAME_POINTER_REGNUM
2533 || regno == ARG_POINTER_REGNUM)))
2534 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2537 if (collection_rec)
2539 if (DF_REF_REG_DEF_P (this_ref))
2540 collection_rec->def_vec.safe_push (this_ref);
2541 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2542 collection_rec->eq_use_vec.safe_push (this_ref);
2543 else
2544 collection_rec->use_vec.safe_push (this_ref);
2546 else
2547 df_install_ref_incremental (this_ref);
2549 return this_ref;
2553 /* Create new references of type DF_REF_TYPE for each part of register REG
2554 at address LOC within INSN of BB. */
2557 static void
2558 df_ref_record (enum df_ref_class cl,
2559 struct df_collection_rec *collection_rec,
2560 rtx reg, rtx *loc,
2561 basic_block bb, struct df_insn_info *insn_info,
2562 enum df_ref_type ref_type,
2563 int ref_flags)
2565 unsigned int regno;
2567 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2569 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2570 if (regno < FIRST_PSEUDO_REGISTER)
2572 struct df_mw_hardreg *hardreg = NULL;
2573 struct df_scan_problem_data *problem_data
2574 = (struct df_scan_problem_data *) df_scan->problem_data;
2575 unsigned int i;
2576 unsigned int endregno;
2577 df_ref ref;
2579 if (GET_CODE (reg) == SUBREG)
2581 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2582 SUBREG_BYTE (reg), GET_MODE (reg));
2583 endregno = regno + subreg_nregs (reg);
2585 else
2586 endregno = END_REGNO (reg);
2588 /* If this is a multiword hardreg, we create some extra
2589 datastructures that will enable us to easily build REG_DEAD
2590 and REG_UNUSED notes. */
2591 if (collection_rec
2592 && (endregno != regno + 1) && insn_info)
2594 /* Sets to a subreg of a multiword register are partial.
2595 Sets to a non-subreg of a multiword register are not. */
2596 if (GET_CODE (reg) == SUBREG)
2597 ref_flags |= DF_REF_PARTIAL;
2598 ref_flags |= DF_REF_MW_HARDREG;
2600 hardreg = problem_data->mw_reg_pool->allocate ();
2601 hardreg->type = ref_type;
2602 hardreg->flags = ref_flags;
2603 hardreg->mw_reg = reg;
2604 hardreg->start_regno = regno;
2605 hardreg->end_regno = endregno - 1;
2606 hardreg->mw_order = df->ref_order++;
2607 collection_rec->mw_vec.safe_push (hardreg);
2610 for (i = regno; i < endregno; i++)
2612 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2613 bb, insn_info, ref_type, ref_flags);
2615 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2618 else
2620 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2621 ref_type, ref_flags);
2626 /* Process all the registers defined in the rtx pointed by LOC.
2627 Autoincrement/decrement definitions will be picked up by df_uses_record.
2628 Any change here has to be matched in df_find_hard_reg_defs_1. */
2630 static void
2631 df_def_record_1 (struct df_collection_rec *collection_rec,
2632 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2633 int flags)
2635 rtx dst = *loc;
2637 /* It is legal to have a set destination be a parallel. */
2638 if (GET_CODE (dst) == PARALLEL)
2640 int i;
2641 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2643 rtx temp = XVECEXP (dst, 0, i);
2644 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2645 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2646 bb, insn_info, flags);
2648 return;
2651 if (GET_CODE (dst) == STRICT_LOW_PART)
2653 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2655 loc = &XEXP (dst, 0);
2656 dst = *loc;
2659 if (GET_CODE (dst) == ZERO_EXTRACT)
2661 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2663 loc = &XEXP (dst, 0);
2664 dst = *loc;
2667 /* At this point if we do not have a reg or a subreg, just return. */
2668 if (REG_P (dst))
2670 df_ref_record (DF_REF_REGULAR, collection_rec,
2671 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2673 /* We want to keep sp alive everywhere - by making all
2674 writes to sp also use of sp. */
2675 if (REGNO (dst) == STACK_POINTER_REGNUM)
2676 df_ref_record (DF_REF_BASE, collection_rec,
2677 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2679 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2681 if (read_modify_subreg_p (dst))
2682 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2684 flags |= DF_REF_SUBREG;
2686 df_ref_record (DF_REF_REGULAR, collection_rec,
2687 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2692 /* Process all the registers defined in the pattern rtx, X. Any change
2693 here has to be matched in df_find_hard_reg_defs. */
2695 static void
2696 df_defs_record (struct df_collection_rec *collection_rec,
2697 rtx x, basic_block bb, struct df_insn_info *insn_info,
2698 int flags)
2700 RTX_CODE code = GET_CODE (x);
2701 int i;
2703 switch (code)
2705 case SET:
2706 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2707 break;
2709 case CLOBBER:
2710 flags |= DF_REF_MUST_CLOBBER;
2711 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2712 break;
2714 case COND_EXEC:
2715 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2716 bb, insn_info, DF_REF_CONDITIONAL);
2717 break;
2719 case PARALLEL:
2720 for (i = 0; i < XVECLEN (x, 0); i++)
2721 df_defs_record (collection_rec, XVECEXP (x, 0, i),
2722 bb, insn_info, flags);
2723 break;
2724 default:
2725 /* No DEFs to record in other cases */
2726 break;
2730 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2731 destination of a set or clobber. This has to match the logic in
2732 df_defs_record_1. */
2734 static void
2735 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2737 /* It is legal to have a set destination be a parallel. */
2738 if (GET_CODE (dst) == PARALLEL)
2740 int i;
2741 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2743 rtx temp = XVECEXP (dst, 0, i);
2744 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2745 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2747 return;
2750 if (GET_CODE (dst) == STRICT_LOW_PART)
2751 dst = XEXP (dst, 0);
2753 if (GET_CODE (dst) == ZERO_EXTRACT)
2754 dst = XEXP (dst, 0);
2756 /* At this point if we do not have a reg or a subreg, just return. */
2757 if (REG_P (dst) && HARD_REGISTER_P (dst))
2758 SET_HARD_REG_BIT (*defs, REGNO (dst));
2759 else if (GET_CODE (dst) == SUBREG
2760 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2761 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2764 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2765 has to match the logic in df_defs_record. */
2767 static void
2768 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2770 RTX_CODE code = GET_CODE (x);
2771 int i;
2773 switch (code)
2775 case SET:
2776 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2777 break;
2779 case CLOBBER:
2780 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2781 break;
2783 case COND_EXEC:
2784 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2785 break;
2787 case PARALLEL:
2788 for (i = 0; i < XVECLEN (x, 0); i++)
2789 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2790 break;
2791 default:
2792 /* No DEFs to record in other cases */
2793 break;
2798 /* Process all the registers used in the rtx at address LOC. */
2800 static void
2801 df_uses_record (struct df_collection_rec *collection_rec,
2802 rtx *loc, enum df_ref_type ref_type,
2803 basic_block bb, struct df_insn_info *insn_info,
2804 int flags)
2806 RTX_CODE code;
2807 rtx x;
2809 retry:
2810 x = *loc;
2811 if (!x)
2812 return;
2813 code = GET_CODE (x);
2814 switch (code)
2816 case LABEL_REF:
2817 case SYMBOL_REF:
2818 case CONST:
2819 CASE_CONST_ANY:
2820 case PC:
2821 case CC0:
2822 case ADDR_VEC:
2823 case ADDR_DIFF_VEC:
2824 return;
2826 case CLOBBER:
2827 /* If we are clobbering a MEM, mark any registers inside the address
2828 as being used. */
2829 if (MEM_P (XEXP (x, 0)))
2830 df_uses_record (collection_rec,
2831 &XEXP (XEXP (x, 0), 0),
2832 DF_REF_REG_MEM_STORE,
2833 bb, insn_info,
2834 flags);
2836 /* If we're clobbering a REG then we have a def so ignore. */
2837 return;
2839 case MEM:
2840 df_uses_record (collection_rec,
2841 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2842 bb, insn_info, flags & DF_REF_IN_NOTE);
2843 return;
2845 case SUBREG:
2846 /* While we're here, optimize this case. */
2847 flags |= DF_REF_PARTIAL;
2848 /* In case the SUBREG is not of a REG, do not optimize. */
2849 if (!REG_P (SUBREG_REG (x)))
2851 loc = &SUBREG_REG (x);
2852 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2853 return;
2855 /* Fall through */
2857 case REG:
2858 df_ref_record (DF_REF_REGULAR, collection_rec,
2859 x, loc, bb, insn_info,
2860 ref_type, flags);
2861 return;
2863 case SIGN_EXTRACT:
2864 case ZERO_EXTRACT:
2866 df_uses_record (collection_rec,
2867 &XEXP (x, 1), ref_type, bb, insn_info, flags);
2868 df_uses_record (collection_rec,
2869 &XEXP (x, 2), ref_type, bb, insn_info, flags);
2871 /* If the parameters to the zero or sign extract are
2872 constants, strip them off and recurse, otherwise there is
2873 no information that we can gain from this operation. */
2874 if (code == ZERO_EXTRACT)
2875 flags |= DF_REF_ZERO_EXTRACT;
2876 else
2877 flags |= DF_REF_SIGN_EXTRACT;
2879 df_uses_record (collection_rec,
2880 &XEXP (x, 0), ref_type, bb, insn_info, flags);
2881 return;
2883 break;
2885 case SET:
2887 rtx dst = SET_DEST (x);
2888 gcc_assert (!(flags & DF_REF_IN_NOTE));
2889 df_uses_record (collection_rec,
2890 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2892 switch (GET_CODE (dst))
2894 case SUBREG:
2895 if (read_modify_subreg_p (dst))
2897 df_uses_record (collection_rec, &SUBREG_REG (dst),
2898 DF_REF_REG_USE, bb, insn_info,
2899 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2900 break;
2902 /* Fall through. */
2903 case REG:
2904 case PARALLEL:
2905 case SCRATCH:
2906 case PC:
2907 case CC0:
2908 break;
2909 case MEM:
2910 df_uses_record (collection_rec, &XEXP (dst, 0),
2911 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2912 break;
2913 case STRICT_LOW_PART:
2915 rtx *temp = &XEXP (dst, 0);
2916 /* A strict_low_part uses the whole REG and not just the
2917 SUBREG. */
2918 dst = XEXP (dst, 0);
2919 df_uses_record (collection_rec,
2920 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2921 DF_REF_REG_USE, bb, insn_info,
2922 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2924 break;
2925 case ZERO_EXTRACT:
2927 df_uses_record (collection_rec, &XEXP (dst, 1),
2928 DF_REF_REG_USE, bb, insn_info, flags);
2929 df_uses_record (collection_rec, &XEXP (dst, 2),
2930 DF_REF_REG_USE, bb, insn_info, flags);
2931 if (GET_CODE (XEXP (dst,0)) == MEM)
2932 df_uses_record (collection_rec, &XEXP (dst, 0),
2933 DF_REF_REG_USE, bb, insn_info,
2934 flags);
2935 else
2936 df_uses_record (collection_rec, &XEXP (dst, 0),
2937 DF_REF_REG_USE, bb, insn_info,
2938 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2940 break;
2942 default:
2943 gcc_unreachable ();
2945 return;
2948 case RETURN:
2949 case SIMPLE_RETURN:
2950 break;
2952 case ASM_OPERANDS:
2953 case UNSPEC_VOLATILE:
2954 case TRAP_IF:
2955 case ASM_INPUT:
2957 /* Traditional and volatile asm instructions must be
2958 considered to use and clobber all hard registers, all
2959 pseudo-registers and all of memory. So must TRAP_IF and
2960 UNSPEC_VOLATILE operations.
2962 Consider for instance a volatile asm that changes the fpu
2963 rounding mode. An insn should not be moved across this
2964 even if it only uses pseudo-regs because it might give an
2965 incorrectly rounded result.
2967 However, flow.c's liveness computation did *not* do this,
2968 giving the reasoning as " ?!? Unfortunately, marking all
2969 hard registers as live causes massive problems for the
2970 register allocator and marking all pseudos as live creates
2971 mountains of uninitialized variable warnings."
2973 In order to maintain the status quo with regard to liveness
2974 and uses, we do what flow.c did and just mark any regs we
2975 can find in ASM_OPERANDS as used. In global asm insns are
2976 scanned and regs_asm_clobbered is filled out.
2978 For all ASM_OPERANDS, we must traverse the vector of input
2979 operands. We can not just fall through here since then we
2980 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2981 which do not indicate traditional asms unlike their normal
2982 usage. */
2983 if (code == ASM_OPERANDS)
2985 int j;
2987 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2988 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
2989 DF_REF_REG_USE, bb, insn_info, flags);
2990 return;
2992 break;
2995 case VAR_LOCATION:
2996 df_uses_record (collection_rec,
2997 &PAT_VAR_LOCATION_LOC (x),
2998 DF_REF_REG_USE, bb, insn_info, flags);
2999 return;
3001 case PRE_DEC:
3002 case POST_DEC:
3003 case PRE_INC:
3004 case POST_INC:
3005 case PRE_MODIFY:
3006 case POST_MODIFY:
3007 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3008 /* Catch the def of the register being modified. */
3009 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3010 bb, insn_info,
3011 DF_REF_REG_DEF,
3012 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3014 /* ... Fall through to handle uses ... */
3016 default:
3017 break;
3020 /* Recursively scan the operands of this expression. */
3022 const char *fmt = GET_RTX_FORMAT (code);
3023 int i;
3025 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3027 if (fmt[i] == 'e')
3029 /* Tail recursive case: save a function call level. */
3030 if (i == 0)
3032 loc = &XEXP (x, 0);
3033 goto retry;
3035 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3036 bb, insn_info, flags);
3038 else if (fmt[i] == 'E')
3040 int j;
3041 for (j = 0; j < XVECLEN (x, i); j++)
3042 df_uses_record (collection_rec,
3043 &XVECEXP (x, i, j), ref_type,
3044 bb, insn_info, flags);
3049 return;
3053 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3055 static void
3056 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3058 unsigned int ix;
3059 df_ref ref;
3061 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3063 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3065 df_ref use;
3067 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3068 DF_REF_LOC (ref), DF_REF_BB (ref),
3069 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3070 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3071 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3077 /* Get call's extra defs and uses (track caller-saved registers). */
3079 static void
3080 df_get_call_refs (struct df_collection_rec *collection_rec,
3081 basic_block bb,
3082 struct df_insn_info *insn_info,
3083 int flags)
3085 rtx note;
3086 bool is_sibling_call;
3087 unsigned int i;
3088 HARD_REG_SET defs_generated;
3089 HARD_REG_SET fn_reg_set_usage;
3091 CLEAR_HARD_REG_SET (defs_generated);
3092 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3093 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3094 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3095 regs_invalidated_by_call);
3097 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3099 if (i == STACK_POINTER_REGNUM)
3100 /* The stack ptr is used (honorarily) by a CALL insn. */
3101 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3102 NULL, bb, insn_info, DF_REF_REG_USE,
3103 DF_REF_CALL_STACK_USAGE | flags);
3104 else if (global_regs[i])
3106 /* Calls to const functions cannot access any global registers and
3107 calls to pure functions cannot set them. All other calls may
3108 reference any of the global registers, so they are recorded as
3109 used. */
3110 if (!RTL_CONST_CALL_P (insn_info->insn))
3112 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3113 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3114 if (!RTL_PURE_CALL_P (insn_info->insn))
3115 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3116 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3119 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3120 /* no clobbers for regs that are the result of the call */
3121 && !TEST_HARD_REG_BIT (defs_generated, i)
3122 && (!is_sibling_call
3123 || !bitmap_bit_p (df->exit_block_uses, i)
3124 || refers_to_regno_p (i, crtl->return_rtx)))
3125 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3126 NULL, bb, insn_info, DF_REF_REG_DEF,
3127 DF_REF_MAY_CLOBBER | flags);
3130 /* Record the registers used to pass arguments, and explicitly
3131 noted as clobbered. */
3132 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3133 note = XEXP (note, 1))
3135 if (GET_CODE (XEXP (note, 0)) == USE)
3136 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3137 DF_REF_REG_USE, bb, insn_info, flags);
3138 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3140 if (REG_P (XEXP (XEXP (note, 0), 0)))
3142 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3143 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3144 df_defs_record (collection_rec, XEXP (note, 0), bb,
3145 insn_info, flags);
3147 else
3148 df_uses_record (collection_rec, &XEXP (note, 0),
3149 DF_REF_REG_USE, bb, insn_info, flags);
3153 return;
3156 /* Collect all refs in the INSN. This function is free of any
3157 side-effect - it will create and return a lists of df_ref's in the
3158 COLLECTION_REC without putting those refs into existing ref chains
3159 and reg chains. */
3161 static void
3162 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3163 basic_block bb, struct df_insn_info *insn_info)
3165 rtx note;
3166 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3168 /* Clear out the collection record. */
3169 collection_rec->def_vec.truncate (0);
3170 collection_rec->use_vec.truncate (0);
3171 collection_rec->eq_use_vec.truncate (0);
3172 collection_rec->mw_vec.truncate (0);
3174 /* Process REG_EQUIV/REG_EQUAL notes. */
3175 for (note = REG_NOTES (insn_info->insn); note;
3176 note = XEXP (note, 1))
3178 switch (REG_NOTE_KIND (note))
3180 case REG_EQUIV:
3181 case REG_EQUAL:
3182 df_uses_record (collection_rec,
3183 &XEXP (note, 0), DF_REF_REG_USE,
3184 bb, insn_info, DF_REF_IN_NOTE);
3185 break;
3186 case REG_NON_LOCAL_GOTO:
3187 /* The frame ptr is used by a non-local goto. */
3188 df_ref_record (DF_REF_BASE, collection_rec,
3189 regno_reg_rtx[FRAME_POINTER_REGNUM],
3190 NULL, bb, insn_info,
3191 DF_REF_REG_USE, 0);
3192 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3193 df_ref_record (DF_REF_BASE, collection_rec,
3194 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3195 NULL, bb, insn_info,
3196 DF_REF_REG_USE, 0);
3197 break;
3198 default:
3199 break;
3203 int flags = (is_cond_exec) ? DF_REF_CONDITIONAL : 0;
3204 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3205 uses from CALL_INSN_FUNCTION_USAGE. */
3206 if (CALL_P (insn_info->insn))
3207 df_get_call_refs (collection_rec, bb, insn_info, flags);
3209 if (asm_noperands (PATTERN (insn_info->insn)) >= 0)
3210 for (unsigned i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3211 if (global_regs[i])
3213 /* As with calls, asm statements reference all global regs. */
3214 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3215 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3216 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3217 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3220 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3221 that a qsort on the defs is unnecessary in most cases. */
3222 df_defs_record (collection_rec,
3223 PATTERN (insn_info->insn), bb, insn_info, 0);
3225 /* Record the register uses. */
3226 df_uses_record (collection_rec,
3227 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3229 /* DF_REF_CONDITIONAL needs corresponding USES. */
3230 if (is_cond_exec)
3231 df_get_conditional_uses (collection_rec);
3233 df_canonize_collection_rec (collection_rec);
3236 /* Recompute the luids for the insns in BB. */
3238 void
3239 df_recompute_luids (basic_block bb)
3241 rtx_insn *insn;
3242 int luid = 0;
3244 df_grow_insn_info ();
3246 /* Scan the block an insn at a time from beginning to end. */
3247 FOR_BB_INSNS (bb, insn)
3249 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3250 /* Inserting labels does not always trigger the incremental
3251 rescanning. */
3252 if (!insn_info)
3254 gcc_assert (!INSN_P (insn));
3255 insn_info = df_insn_create_insn_record (insn);
3258 DF_INSN_INFO_LUID (insn_info) = luid;
3259 if (INSN_P (insn))
3260 luid++;
3265 /* Collect all artificial refs at the block level for BB and add them
3266 to COLLECTION_REC. */
3268 static void
3269 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3271 collection_rec->def_vec.truncate (0);
3272 collection_rec->use_vec.truncate (0);
3273 collection_rec->eq_use_vec.truncate (0);
3274 collection_rec->mw_vec.truncate (0);
3276 if (bb->index == ENTRY_BLOCK)
3278 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3279 return;
3281 else if (bb->index == EXIT_BLOCK)
3283 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3284 return;
3287 if (bb_has_eh_pred (bb))
3289 unsigned int i;
3290 /* Mark the registers that will contain data for the handler. */
3291 for (i = 0; ; ++i)
3293 unsigned regno = EH_RETURN_DATA_REGNO (i);
3294 if (regno == INVALID_REGNUM)
3295 break;
3296 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3297 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3301 /* Add the hard_frame_pointer if this block is the target of a
3302 non-local goto. */
3303 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3304 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3305 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3307 /* Add the artificial uses. */
3308 if (bb->index >= NUM_FIXED_BLOCKS)
3310 bitmap_iterator bi;
3311 unsigned int regno;
3312 bitmap au = bb_has_eh_pred (bb)
3313 ? &df->eh_block_artificial_uses
3314 : &df->regular_block_artificial_uses;
3316 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3318 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3319 bb, NULL, DF_REF_REG_USE, 0);
3323 df_canonize_collection_rec (collection_rec);
3327 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3329 void
3330 df_bb_refs_record (int bb_index, bool scan_insns)
3332 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3333 rtx_insn *insn;
3334 int luid = 0;
3336 if (!df)
3337 return;
3339 df_collection_rec collection_rec;
3340 df_grow_bb_info (df_scan);
3341 if (scan_insns)
3342 /* Scan the block an insn at a time from beginning to end. */
3343 FOR_BB_INSNS (bb, insn)
3345 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3346 gcc_assert (!insn_info);
3348 insn_info = df_insn_create_insn_record (insn);
3349 if (INSN_P (insn))
3351 /* Record refs within INSN. */
3352 DF_INSN_INFO_LUID (insn_info) = luid++;
3353 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3354 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3356 DF_INSN_INFO_LUID (insn_info) = luid;
3359 /* Other block level artificial refs */
3360 df_bb_refs_collect (&collection_rec, bb);
3361 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3363 /* Now that the block has been processed, set the block as dirty so
3364 LR and LIVE will get it processed. */
3365 df_set_bb_dirty (bb);
3369 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3370 block. */
3372 static void
3373 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3375 #ifdef EH_USES
3376 unsigned int i;
3377 #endif
3379 bitmap_clear (regular_block_artificial_uses);
3381 if (reload_completed)
3383 if (frame_pointer_needed)
3384 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3386 else
3387 /* Before reload, there are a few registers that must be forced
3388 live everywhere -- which might not already be the case for
3389 blocks within infinite loops. */
3391 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3393 /* Any reference to any pseudo before reload is a potential
3394 reference of the frame pointer. */
3395 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3397 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3398 bitmap_set_bit (regular_block_artificial_uses,
3399 HARD_FRAME_POINTER_REGNUM);
3401 /* Pseudos with argument area equivalences may require
3402 reloading via the argument pointer. */
3403 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3404 && fixed_regs[ARG_POINTER_REGNUM])
3405 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3407 /* Any constant, or pseudo with constant equivalences, may
3408 require reloading from memory using the pic register. */
3409 if (picreg != INVALID_REGNUM
3410 && fixed_regs[picreg])
3411 bitmap_set_bit (regular_block_artificial_uses, picreg);
3413 /* The all-important stack pointer must always be live. */
3414 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3416 #ifdef EH_USES
3417 /* EH_USES registers are used:
3418 1) at all insns that might throw (calls or with -fnon-call-exceptions
3419 trapping insns)
3420 2) in all EH edges
3421 3) to support backtraces and/or debugging, anywhere between their
3422 initialization and where they the saved registers are restored
3423 from them, including the cases where we don't reach the epilogue
3424 (noreturn call or infinite loop). */
3425 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3426 if (EH_USES (i))
3427 bitmap_set_bit (regular_block_artificial_uses, i);
3428 #endif
3432 /* Get the artificial use set for an eh block. */
3434 static void
3435 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3437 bitmap_clear (eh_block_artificial_uses);
3439 /* The following code (down through the arg_pointer setting APPEARS
3440 to be necessary because there is nothing that actually
3441 describes what the exception handling code may actually need
3442 to keep alive. */
3443 if (reload_completed)
3445 if (frame_pointer_needed)
3447 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3448 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3449 bitmap_set_bit (eh_block_artificial_uses,
3450 HARD_FRAME_POINTER_REGNUM);
3452 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3453 && fixed_regs[ARG_POINTER_REGNUM])
3454 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3460 /*----------------------------------------------------------------------------
3461 Specialized hard register scanning functions.
3462 ----------------------------------------------------------------------------*/
3465 /* Mark a register in SET. Hard registers in large modes get all
3466 of their component registers set as well. */
3468 static void
3469 df_mark_reg (rtx reg, void *vset)
3471 bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3475 /* Set the bit for regs that are considered being defined at the entry. */
3477 static void
3478 df_get_entry_block_def_set (bitmap entry_block_defs)
3480 rtx r;
3481 int i;
3483 bitmap_clear (entry_block_defs);
3485 /* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3486 need a prologue for some component to be executed before that block,
3487 and we do not care about any other registers. Hence, we do not want
3488 any register for any component defined in the entry block, and we can
3489 just leave all registers undefined. */
3490 if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3491 return;
3493 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3495 if (global_regs[i])
3496 bitmap_set_bit (entry_block_defs, i);
3497 if (FUNCTION_ARG_REGNO_P (i))
3498 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3501 /* The always important stack pointer. */
3502 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3504 /* Once the prologue has been generated, all of these registers
3505 should just show up in the first regular block. */
3506 if (targetm.have_prologue () && epilogue_completed)
3508 /* Defs for the callee saved registers are inserted so that the
3509 pushes have some defining location. */
3510 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3511 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3512 bitmap_set_bit (entry_block_defs, i);
3515 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3516 if (r && REG_P (r))
3517 bitmap_set_bit (entry_block_defs, REGNO (r));
3519 /* If the function has an incoming STATIC_CHAIN, it has to show up
3520 in the entry def set. */
3521 r = targetm.calls.static_chain (current_function_decl, true);
3522 if (r && REG_P (r))
3523 bitmap_set_bit (entry_block_defs, REGNO (r));
3525 if ((!reload_completed) || frame_pointer_needed)
3527 /* Any reference to any pseudo before reload is a potential
3528 reference of the frame pointer. */
3529 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3531 /* If they are different, also mark the hard frame pointer as live. */
3532 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3533 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3534 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3537 /* These registers are live everywhere. */
3538 if (!reload_completed)
3540 /* Pseudos with argument area equivalences may require
3541 reloading via the argument pointer. */
3542 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3543 && fixed_regs[ARG_POINTER_REGNUM])
3544 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3546 /* Any constant, or pseudo with constant equivalences, may
3547 require reloading from memory using the pic register. */
3548 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3549 if (picreg != INVALID_REGNUM
3550 && fixed_regs[picreg])
3551 bitmap_set_bit (entry_block_defs, picreg);
3554 #ifdef INCOMING_RETURN_ADDR_RTX
3555 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3556 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3557 #endif
3559 targetm.extra_live_on_entry (entry_block_defs);
3563 /* Return the (conservative) set of hard registers that are defined on
3564 entry to the function.
3565 It uses df->entry_block_defs to determine which register
3566 reference to include. */
3568 static void
3569 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3570 bitmap entry_block_defs)
3572 unsigned int i;
3573 bitmap_iterator bi;
3575 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3577 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3578 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3581 df_canonize_collection_rec (collection_rec);
3585 /* Record the (conservative) set of hard registers that are defined on
3586 entry to the function. */
3588 static void
3589 df_record_entry_block_defs (bitmap entry_block_defs)
3591 struct df_collection_rec collection_rec;
3592 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3594 /* Process bb_refs chain */
3595 df_refs_add_to_chains (&collection_rec,
3596 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3597 NULL,
3598 copy_defs);
3602 /* Update the defs in the entry block. */
3604 void
3605 df_update_entry_block_defs (void)
3607 bool changed = false;
3609 auto_bitmap refs (&df_bitmap_obstack);
3610 df_get_entry_block_def_set (refs);
3611 if (df->entry_block_defs)
3613 if (!bitmap_equal_p (df->entry_block_defs, refs))
3615 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3616 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3617 df_ref_chain_delete (bb_info->artificial_defs);
3618 bb_info->artificial_defs = NULL;
3619 changed = true;
3622 else
3624 struct df_scan_problem_data *problem_data
3625 = (struct df_scan_problem_data *) df_scan->problem_data;
3626 gcc_unreachable ();
3627 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3628 changed = true;
3631 if (changed)
3633 df_record_entry_block_defs (refs);
3634 bitmap_copy (df->entry_block_defs, refs);
3635 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3640 /* Set the bit for regs that are considered being used at the exit. */
3642 static void
3643 df_get_exit_block_use_set (bitmap exit_block_uses)
3645 unsigned int i;
3646 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3648 bitmap_clear (exit_block_uses);
3650 /* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3651 need an epilogue for some component to be executed after that block,
3652 and we do not care about any other registers. Hence, we do not want
3653 any register for any component seen as used in the exit block, and we
3654 can just say no registers at all are used. */
3655 if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3656 return;
3658 /* Stack pointer is always live at the exit. */
3659 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3661 /* Mark the frame pointer if needed at the end of the function.
3662 If we end up eliminating it, it will be removed from the live
3663 list of each basic block by reload. */
3665 if ((!reload_completed) || frame_pointer_needed)
3667 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3669 /* If they are different, also mark the hard frame pointer as live. */
3670 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3671 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3672 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3675 /* Many architectures have a GP register even without flag_pic.
3676 Assume the pic register is not in use, or will be handled by
3677 other means, if it is not fixed. */
3678 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3679 && picreg != INVALID_REGNUM
3680 && fixed_regs[picreg])
3681 bitmap_set_bit (exit_block_uses, picreg);
3683 /* Mark all global registers, and all registers used by the
3684 epilogue as being live at the end of the function since they
3685 may be referenced by our caller. */
3686 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3687 if (global_regs[i] || EPILOGUE_USES (i))
3688 bitmap_set_bit (exit_block_uses, i);
3690 if (targetm.have_epilogue () && epilogue_completed)
3692 /* Mark all call-saved registers that we actually used. */
3693 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3694 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3695 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3696 bitmap_set_bit (exit_block_uses, i);
3699 /* Mark the registers that will contain data for the handler. */
3700 if (reload_completed && crtl->calls_eh_return)
3701 for (i = 0; ; ++i)
3703 unsigned regno = EH_RETURN_DATA_REGNO (i);
3704 if (regno == INVALID_REGNUM)
3705 break;
3706 bitmap_set_bit (exit_block_uses, regno);
3709 #ifdef EH_RETURN_STACKADJ_RTX
3710 if ((!targetm.have_epilogue () || ! epilogue_completed)
3711 && crtl->calls_eh_return)
3713 rtx tmp = EH_RETURN_STACKADJ_RTX;
3714 if (tmp && REG_P (tmp))
3715 df_mark_reg (tmp, exit_block_uses);
3717 #endif
3719 if ((!targetm.have_epilogue () || ! epilogue_completed)
3720 && crtl->calls_eh_return)
3722 rtx tmp = EH_RETURN_HANDLER_RTX;
3723 if (tmp && REG_P (tmp))
3724 df_mark_reg (tmp, exit_block_uses);
3727 /* Mark function return value. */
3728 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3732 /* Return the refs of hard registers that are used in the exit block.
3733 It uses df->exit_block_uses to determine register to include. */
3735 static void
3736 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3738 unsigned int i;
3739 bitmap_iterator bi;
3741 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3742 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3743 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3745 /* It is deliberate that this is not put in the exit block uses but
3746 I do not know why. */
3747 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3748 && reload_completed
3749 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3750 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3751 && fixed_regs[ARG_POINTER_REGNUM])
3752 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3753 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3755 df_canonize_collection_rec (collection_rec);
3759 /* Record the set of hard registers that are used in the exit block.
3760 It uses df->exit_block_uses to determine which bit to include. */
3762 static void
3763 df_record_exit_block_uses (bitmap exit_block_uses)
3765 struct df_collection_rec collection_rec;
3766 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3768 /* Process bb_refs chain */
3769 df_refs_add_to_chains (&collection_rec,
3770 BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3771 NULL,
3772 copy_uses);
3776 /* Update the uses in the exit block. */
3778 void
3779 df_update_exit_block_uses (void)
3781 bool changed = false;
3783 auto_bitmap refs (&df_bitmap_obstack);
3784 df_get_exit_block_use_set (refs);
3785 if (df->exit_block_uses)
3787 if (!bitmap_equal_p (df->exit_block_uses, refs))
3789 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3790 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3791 df_ref_chain_delete (bb_info->artificial_uses);
3792 bb_info->artificial_uses = NULL;
3793 changed = true;
3796 else
3798 struct df_scan_problem_data *problem_data
3799 = (struct df_scan_problem_data *) df_scan->problem_data;
3800 gcc_unreachable ();
3801 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3802 changed = true;
3805 if (changed)
3807 df_record_exit_block_uses (refs);
3808 bitmap_copy (df->exit_block_uses, refs);
3809 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3813 static bool initialized = false;
3816 /* Initialize some platform specific structures. */
3818 void
3819 df_hard_reg_init (void)
3821 int i;
3822 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3824 if (initialized)
3825 return;
3827 /* Record which registers will be eliminated. We use this in
3828 mark_used_regs. */
3829 CLEAR_HARD_REG_SET (elim_reg_set);
3831 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3832 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3834 initialized = true;
3838 /* Recompute the parts of scanning that are based on regs_ever_live
3839 because something changed in that array. */
3841 void
3842 df_update_entry_exit_and_calls (void)
3844 basic_block bb;
3846 df_update_entry_block_defs ();
3847 df_update_exit_block_uses ();
3849 /* The call insns need to be rescanned because there may be changes
3850 in the set of registers clobbered across the call. */
3851 FOR_EACH_BB_FN (bb, cfun)
3853 rtx_insn *insn;
3854 FOR_BB_INSNS (bb, insn)
3856 if (INSN_P (insn) && CALL_P (insn))
3857 df_insn_rescan (insn);
3863 /* Return true if hard REG is actually used in the some instruction.
3864 There are a fair number of conditions that affect the setting of
3865 this array. See the comment in df.h for df->hard_regs_live_count
3866 for the conditions that this array is set. */
3868 bool
3869 df_hard_reg_used_p (unsigned int reg)
3871 return df->hard_regs_live_count[reg] != 0;
3875 /* A count of the number of times REG is actually used in the some
3876 instruction. There are a fair number of conditions that affect the
3877 setting of this array. See the comment in df.h for
3878 df->hard_regs_live_count for the conditions that this array is
3879 set. */
3882 unsigned int
3883 df_hard_reg_used_count (unsigned int reg)
3885 return df->hard_regs_live_count[reg];
3889 /* Get the value of regs_ever_live[REGNO]. */
3891 bool
3892 df_regs_ever_live_p (unsigned int regno)
3894 return regs_ever_live[regno];
3898 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3899 to change, schedule that change for the next update. */
3901 void
3902 df_set_regs_ever_live (unsigned int regno, bool value)
3904 if (regs_ever_live[regno] == value)
3905 return;
3907 regs_ever_live[regno] = value;
3908 if (df)
3909 df->redo_entry_and_exit = true;
3913 /* Compute "regs_ever_live" information from the underlying df
3914 information. Set the vector to all false if RESET. */
3916 void
3917 df_compute_regs_ever_live (bool reset)
3919 unsigned int i;
3920 bool changed = df->redo_entry_and_exit;
3922 if (reset)
3923 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3925 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3926 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3928 regs_ever_live[i] = true;
3929 changed = true;
3931 if (changed)
3932 df_update_entry_exit_and_calls ();
3933 df->redo_entry_and_exit = false;
3937 /*----------------------------------------------------------------------------
3938 Dataflow ref information verification functions.
3940 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3941 df_reg_chain_verify_unmarked (refs)
3942 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3943 df_mws_verify (mw*, mw*, bool)
3944 df_insn_refs_verify (collection_rec, bb, insn, bool)
3945 df_bb_refs_verify (bb, refs, bool)
3946 df_bb_verify (bb)
3947 df_exit_block_bitmap_verify (bool)
3948 df_entry_block_bitmap_verify (bool)
3949 df_scan_verify ()
3950 ----------------------------------------------------------------------------*/
3953 /* Mark all refs in the reg chain. Verify that all of the registers
3954 are in the correct chain. */
3956 static unsigned int
3957 df_reg_chain_mark (df_ref refs, unsigned int regno,
3958 bool is_def, bool is_eq_use)
3960 unsigned int count = 0;
3961 df_ref ref;
3962 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3964 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3966 /* If there are no def-use or use-def chains, make sure that all
3967 of the chains are clear. */
3968 if (!df_chain)
3969 gcc_assert (!DF_REF_CHAIN (ref));
3971 /* Check to make sure the ref is in the correct chain. */
3972 gcc_assert (DF_REF_REGNO (ref) == regno);
3973 if (is_def)
3974 gcc_assert (DF_REF_REG_DEF_P (ref));
3975 else
3976 gcc_assert (!DF_REF_REG_DEF_P (ref));
3978 if (is_eq_use)
3979 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
3980 else
3981 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
3983 if (DF_REF_NEXT_REG (ref))
3984 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
3985 count++;
3986 DF_REF_REG_MARK (ref);
3988 return count;
3992 /* Verify that all of the registers in the chain are unmarked. */
3994 static void
3995 df_reg_chain_verify_unmarked (df_ref refs)
3997 df_ref ref;
3998 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3999 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4003 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4005 static bool
4006 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4007 bool abort_if_fail)
4009 unsigned int ix;
4010 df_ref new_ref;
4012 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4014 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4016 if (abort_if_fail)
4017 gcc_assert (0);
4018 else
4019 return false;
4022 /* Abort if fail is called from the function level verifier. If
4023 that is the context, mark this reg as being seem. */
4024 if (abort_if_fail)
4026 gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4027 DF_REF_REG_UNMARK (old_rec);
4030 old_rec = DF_REF_NEXT_LOC (old_rec);
4033 if (abort_if_fail)
4034 gcc_assert (old_rec == NULL);
4035 else
4036 return old_rec == NULL;
4037 return false;
4041 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4043 static bool
4044 df_mws_verify (const vec<df_mw_hardreg *, va_heap> *new_rec,
4045 struct df_mw_hardreg *old_rec,
4046 bool abort_if_fail)
4048 unsigned int ix;
4049 struct df_mw_hardreg *new_reg;
4051 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4053 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4055 if (abort_if_fail)
4056 gcc_assert (0);
4057 else
4058 return false;
4060 old_rec = DF_MWS_NEXT (old_rec);
4063 if (abort_if_fail)
4064 gcc_assert (old_rec == NULL);
4065 else
4066 return old_rec == NULL;
4067 return false;
4071 /* Return true if the existing insn refs information is complete and
4072 correct. Otherwise (i.e. if there's any missing or extra refs),
4073 return the correct df_ref chain in REFS_RETURN.
4075 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4076 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4077 verification mode instead of the whole function, so unmark
4078 everything.
4080 If ABORT_IF_FAIL is set, this function never returns false. */
4082 static bool
4083 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4084 basic_block bb,
4085 rtx_insn *insn,
4086 bool abort_if_fail)
4088 bool ret1, ret2, ret3;
4089 unsigned int uid = INSN_UID (insn);
4090 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4092 df_insn_refs_collect (collection_rec, bb, insn_info);
4094 /* Unfortunately we cannot opt out early if one of these is not
4095 right and abort_if_fail is set because the marks will not get cleared. */
4096 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4097 abort_if_fail);
4098 if (!ret1 && !abort_if_fail)
4099 return false;
4100 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4101 abort_if_fail);
4102 if (!ret2 && !abort_if_fail)
4103 return false;
4104 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4105 abort_if_fail);
4106 if (!ret3 && !abort_if_fail)
4107 return false;
4108 if (! df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4109 abort_if_fail))
4110 return false;
4111 return (ret1 && ret2 && ret3);
4115 /* Return true if all refs in the basic block are correct and complete.
4116 Due to df_ref_chain_verify, it will cause all refs
4117 that are verified to have DF_REF_MARK bit set. */
4119 static bool
4120 df_bb_verify (basic_block bb)
4122 rtx_insn *insn;
4123 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4124 struct df_collection_rec collection_rec;
4126 gcc_assert (bb_info);
4128 /* Scan the block, one insn at a time, from beginning to end. */
4129 FOR_BB_INSNS_REVERSE (bb, insn)
4131 if (!INSN_P (insn))
4132 continue;
4133 df_insn_refs_verify (&collection_rec, bb, insn, true);
4134 df_free_collection_rec (&collection_rec);
4137 /* Do the artificial defs and uses. */
4138 df_bb_refs_collect (&collection_rec, bb);
4139 df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4140 df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4141 df_free_collection_rec (&collection_rec);
4143 return true;
4147 /* Returns true if the entry block has correct and complete df_ref set.
4148 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4150 static bool
4151 df_entry_block_bitmap_verify (bool abort_if_fail)
4153 bool is_eq;
4155 auto_bitmap entry_block_defs (&df_bitmap_obstack);
4156 df_get_entry_block_def_set (entry_block_defs);
4158 is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4160 if (!is_eq && abort_if_fail)
4162 fprintf (stderr, "entry_block_defs = ");
4163 df_print_regset (stderr, entry_block_defs);
4164 fprintf (stderr, "df->entry_block_defs = ");
4165 df_print_regset (stderr, df->entry_block_defs);
4166 gcc_assert (0);
4169 return is_eq;
4173 /* Returns true if the exit block has correct and complete df_ref set.
4174 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4176 static bool
4177 df_exit_block_bitmap_verify (bool abort_if_fail)
4179 bool is_eq;
4181 auto_bitmap exit_block_uses (&df_bitmap_obstack);
4182 df_get_exit_block_use_set (exit_block_uses);
4184 is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4186 if (!is_eq && abort_if_fail)
4188 fprintf (stderr, "exit_block_uses = ");
4189 df_print_regset (stderr, exit_block_uses);
4190 fprintf (stderr, "df->exit_block_uses = ");
4191 df_print_regset (stderr, df->exit_block_uses);
4192 gcc_assert (0);
4195 return is_eq;
4199 /* Return true if df_ref information for all insns in all blocks are
4200 correct and complete. */
4202 void
4203 df_scan_verify (void)
4205 unsigned int i;
4206 basic_block bb;
4208 if (!df)
4209 return;
4211 /* Verification is a 4 step process. */
4213 /* (1) All of the refs are marked by going through the reg chains. */
4214 for (i = 0; i < DF_REG_SIZE (df); i++)
4216 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4217 == DF_REG_DEF_COUNT (i));
4218 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4219 == DF_REG_USE_COUNT (i));
4220 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4221 == DF_REG_EQ_USE_COUNT (i));
4224 /* (2) There are various bitmaps whose value may change over the
4225 course of the compilation. This step recomputes them to make
4226 sure that they have not slipped out of date. */
4227 auto_bitmap regular_block_artificial_uses (&df_bitmap_obstack);
4228 auto_bitmap eh_block_artificial_uses (&df_bitmap_obstack);
4230 df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4231 df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4233 bitmap_ior_into (eh_block_artificial_uses,
4234 regular_block_artificial_uses);
4236 /* Check artificial_uses bitmaps didn't change. */
4237 gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4238 &df->regular_block_artificial_uses));
4239 gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4240 &df->eh_block_artificial_uses));
4242 /* Verify entry block and exit block. These only verify the bitmaps,
4243 the refs are verified in df_bb_verify. */
4244 df_entry_block_bitmap_verify (true);
4245 df_exit_block_bitmap_verify (true);
4247 /* (3) All of the insns in all of the blocks are traversed and the
4248 marks are cleared both in the artificial refs attached to the
4249 blocks and the real refs inside the insns. It is a failure to
4250 clear a mark that has not been set as this means that the ref in
4251 the block or insn was not in the reg chain. */
4253 FOR_ALL_BB_FN (bb, cfun)
4254 df_bb_verify (bb);
4256 /* (4) See if all reg chains are traversed a second time. This time
4257 a check is made that the marks are clear. A set mark would be a
4258 from a reg that is not in any insn or basic block. */
4260 for (i = 0; i < DF_REG_SIZE (df); i++)
4262 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4263 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4264 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));