[AArch64][14/14] Reuse target_option_current_node when passing pragma string to targe...
[official-gcc.git] / gcc / df-scan.c
blob93c2eae3e0228518003f924d76cbd08aba86fae8
1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999-2015 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 "tree.h"
29 #include "rtl.h"
30 #include "df.h"
31 #include "tm_p.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "alias.h"
35 #include "regs.h"
36 #include "alloc-pool.h"
37 #include "flags.h"
38 #include "dumpfile.h"
39 #include "target.h"
40 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
43 typedef struct df_mw_hardreg *df_mw_hardreg_ptr;
46 /* The set of hard registers in eliminables[i].from. */
48 static HARD_REG_SET elim_reg_set;
50 /* Initialize ur_in and ur_out as if all hard registers were partially
51 available. */
53 struct df_collection_rec
55 auto_vec<df_ref, 128> def_vec;
56 auto_vec<df_ref, 32> use_vec;
57 auto_vec<df_ref, 32> eq_use_vec;
58 auto_vec<df_mw_hardreg_ptr, 32> mw_vec;
61 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
62 rtx, rtx *,
63 basic_block, struct df_insn_info *,
64 enum df_ref_type, int ref_flags);
65 static void df_def_record_1 (struct df_collection_rec *, rtx *,
66 basic_block, struct df_insn_info *,
67 int ref_flags);
68 static void df_defs_record (struct df_collection_rec *, rtx,
69 basic_block, struct df_insn_info *,
70 int ref_flags);
71 static void df_uses_record (struct df_collection_rec *,
72 rtx *, enum df_ref_type,
73 basic_block, struct df_insn_info *,
74 int ref_flags);
76 static void df_install_ref_incremental (df_ref);
77 static void df_insn_refs_collect (struct df_collection_rec*,
78 basic_block, struct df_insn_info *);
79 static void df_canonize_collection_rec (struct df_collection_rec *);
81 static void df_get_regular_block_artificial_uses (bitmap);
82 static void df_get_eh_block_artificial_uses (bitmap);
84 static void df_record_entry_block_defs (bitmap);
85 static void df_record_exit_block_uses (bitmap);
86 static void df_get_exit_block_use_set (bitmap);
87 static void df_get_entry_block_def_set (bitmap);
88 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
89 static void df_ref_chain_delete_du_chain (df_ref);
90 static void df_ref_chain_delete (df_ref);
92 static void df_refs_add_to_chains (struct df_collection_rec *,
93 basic_block, rtx_insn *, unsigned int);
95 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block,
96 rtx_insn *, bool);
97 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
98 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
99 static void df_install_ref (df_ref, struct df_reg_info *,
100 struct df_ref_info *, bool);
102 static int df_ref_compare (df_ref, df_ref);
103 static int df_ref_ptr_compare (const void *, const void *);
104 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
105 static int df_mw_ptr_compare (const void *, const void *);
107 static void df_insn_info_delete (unsigned int);
109 /* Indexed by hardware reg number, is true if that register is ever
110 used in the current function.
112 In df-scan.c, this is set up to record the hard regs used
113 explicitly. Reload adds in the hard regs used for holding pseudo
114 regs. Final uses it to generate the code in the function prologue
115 and epilogue to save and restore registers as needed. */
117 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
119 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
120 static const unsigned int copy_defs = 0x1;
121 static const unsigned int copy_uses = 0x2;
122 static const unsigned int copy_eq_uses = 0x4;
123 static const unsigned int copy_mw = 0x8;
124 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
125 | copy_mw;
127 /*----------------------------------------------------------------------------
128 SCANNING DATAFLOW PROBLEM
130 There are several ways in which scanning looks just like the other
131 dataflow problems. It shares the all the mechanisms for local info
132 as well as basic block info. Where it differs is when and how often
133 it gets run. It also has no need for the iterative solver.
134 ----------------------------------------------------------------------------*/
136 #define SCAN_PROBLEM_DATA_BLOCK_SIZE 512
138 /* Problem data for the scanning dataflow function. */
139 struct df_scan_problem_data
141 object_allocator<df_base_ref> *ref_base_pool;
142 object_allocator<df_artificial_ref> *ref_artificial_pool;
143 object_allocator<df_regular_ref> *ref_regular_pool;
144 object_allocator<df_insn_info> *insn_pool;
145 object_allocator<df_reg_info> *reg_pool;
146 object_allocator<df_mw_hardreg> *mw_reg_pool;
148 bitmap_obstack reg_bitmaps;
149 bitmap_obstack insn_bitmaps;
152 typedef struct df_scan_bb_info *df_scan_bb_info_t;
155 /* Internal function to shut down the scanning problem. */
156 static void
157 df_scan_free_internal (void)
159 struct df_scan_problem_data *problem_data
160 = (struct df_scan_problem_data *) df_scan->problem_data;
162 free (df->def_info.refs);
163 free (df->def_info.begin);
164 free (df->def_info.count);
165 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
167 free (df->use_info.refs);
168 free (df->use_info.begin);
169 free (df->use_info.count);
170 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
172 free (df->def_regs);
173 df->def_regs = NULL;
174 free (df->use_regs);
175 df->use_regs = NULL;
176 free (df->eq_use_regs);
177 df->eq_use_regs = NULL;
178 df->regs_size = 0;
179 DF_REG_SIZE (df) = 0;
181 free (df->insns);
182 df->insns = NULL;
183 DF_INSN_SIZE () = 0;
185 free (df_scan->block_info);
186 df_scan->block_info = NULL;
187 df_scan->block_info_size = 0;
189 bitmap_clear (&df->hardware_regs_used);
190 bitmap_clear (&df->regular_block_artificial_uses);
191 bitmap_clear (&df->eh_block_artificial_uses);
192 BITMAP_FREE (df->entry_block_defs);
193 BITMAP_FREE (df->exit_block_uses);
194 bitmap_clear (&df->insns_to_delete);
195 bitmap_clear (&df->insns_to_rescan);
196 bitmap_clear (&df->insns_to_notes_rescan);
198 delete problem_data->ref_base_pool;
199 delete problem_data->ref_artificial_pool;
200 delete problem_data->ref_regular_pool;
201 delete problem_data->insn_pool;
202 delete problem_data->reg_pool;
203 delete problem_data->mw_reg_pool;
204 bitmap_obstack_release (&problem_data->reg_bitmaps);
205 bitmap_obstack_release (&problem_data->insn_bitmaps);
206 free (df_scan->problem_data);
210 /* Free basic block info. */
212 static void
213 df_scan_free_bb_info (basic_block bb, void *vbb_info)
215 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
216 unsigned int bb_index = bb->index;
217 rtx_insn *insn;
219 FOR_BB_INSNS (bb, insn)
220 if (INSN_P (insn))
221 df_insn_info_delete (INSN_UID (insn));
223 if (bb_index < df_scan->block_info_size)
224 bb_info = df_scan_get_bb_info (bb_index);
226 /* Get rid of any artificial uses or defs. */
227 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
228 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
229 df_ref_chain_delete (bb_info->artificial_defs);
230 df_ref_chain_delete (bb_info->artificial_uses);
231 bb_info->artificial_defs = NULL;
232 bb_info->artificial_uses = NULL;
236 /* Allocate the problem data for the scanning problem. This should be
237 called when the problem is created or when the entire function is to
238 be rescanned. */
239 void
240 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
242 struct df_scan_problem_data *problem_data;
243 unsigned int insn_num = get_max_uid () + 1;
244 basic_block bb;
246 /* Given the number of pools, this is really faster than tearing
247 everything apart. */
248 if (df_scan->problem_data)
249 df_scan_free_internal ();
251 problem_data = XNEW (struct df_scan_problem_data);
252 df_scan->problem_data = problem_data;
253 df_scan->computed = true;
255 problem_data->ref_base_pool = new object_allocator<df_base_ref>
256 ("df_scan ref base", SCAN_PROBLEM_DATA_BLOCK_SIZE);
257 problem_data->ref_artificial_pool = new object_allocator<df_artificial_ref>
258 ("df_scan ref artificial", SCAN_PROBLEM_DATA_BLOCK_SIZE);
259 problem_data->ref_regular_pool = new object_allocator<df_regular_ref>
260 ("df_scan ref regular", SCAN_PROBLEM_DATA_BLOCK_SIZE);
261 problem_data->insn_pool = new object_allocator<df_insn_info>
262 ("df_scan insn", SCAN_PROBLEM_DATA_BLOCK_SIZE);
263 problem_data->reg_pool = new object_allocator<df_reg_info>
264 ("df_scan reg", SCAN_PROBLEM_DATA_BLOCK_SIZE);
265 problem_data->mw_reg_pool = new object_allocator<df_mw_hardreg>
266 ("df_scan mw_reg", SCAN_PROBLEM_DATA_BLOCK_SIZE / 16);
268 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
269 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
271 insn_num += insn_num / 4;
272 df_grow_reg_info ();
274 df_grow_insn_info ();
275 df_grow_bb_info (df_scan);
277 FOR_ALL_BB_FN (bb, cfun)
279 unsigned int bb_index = bb->index;
280 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
281 bb_info->artificial_defs = NULL;
282 bb_info->artificial_uses = NULL;
285 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
286 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
287 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
288 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
289 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
290 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
291 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
292 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
293 df_scan->optional_p = false;
297 /* Free all of the data associated with the scan problem. */
299 static void
300 df_scan_free (void)
302 if (df_scan->problem_data)
303 df_scan_free_internal ();
305 if (df->blocks_to_analyze)
307 BITMAP_FREE (df->blocks_to_analyze);
308 df->blocks_to_analyze = NULL;
311 free (df_scan);
314 /* Dump the preamble for DF_SCAN dump. */
315 static void
316 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
318 int i;
319 int dcount = 0;
320 int ucount = 0;
321 int ecount = 0;
322 int icount = 0;
323 int ccount = 0;
324 basic_block bb;
325 rtx_insn *insn;
327 fprintf (file, ";; invalidated by call \t");
328 df_print_regset (file, regs_invalidated_by_call_regset);
329 fprintf (file, ";; hardware regs used \t");
330 df_print_regset (file, &df->hardware_regs_used);
331 fprintf (file, ";; regular block artificial uses \t");
332 df_print_regset (file, &df->regular_block_artificial_uses);
333 fprintf (file, ";; eh block artificial uses \t");
334 df_print_regset (file, &df->eh_block_artificial_uses);
335 fprintf (file, ";; entry block defs \t");
336 df_print_regset (file, df->entry_block_defs);
337 fprintf (file, ";; exit block uses \t");
338 df_print_regset (file, df->exit_block_uses);
339 fprintf (file, ";; regs ever live \t");
340 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
341 if (df_regs_ever_live_p (i))
342 fprintf (file, " %d [%s]", i, reg_names[i]);
343 fprintf (file, "\n;; ref usage \t");
345 for (i = 0; i < (int)df->regs_inited; i++)
346 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
348 const char * sep = "";
350 fprintf (file, "r%d={", i);
351 if (DF_REG_DEF_COUNT (i))
353 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
354 sep = ",";
355 dcount += DF_REG_DEF_COUNT (i);
357 if (DF_REG_USE_COUNT (i))
359 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
360 sep = ",";
361 ucount += DF_REG_USE_COUNT (i);
363 if (DF_REG_EQ_USE_COUNT (i))
365 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
366 ecount += DF_REG_EQ_USE_COUNT (i);
368 fprintf (file, "} ");
371 FOR_EACH_BB_FN (bb, cfun)
372 FOR_BB_INSNS (bb, insn)
373 if (INSN_P (insn))
375 if (CALL_P (insn))
376 ccount++;
377 else
378 icount++;
381 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
382 " in %d{%d regular + %d call} insns.\n",
383 dcount + ucount + ecount, dcount, ucount, ecount,
384 icount + ccount, icount, ccount);
387 /* Dump the bb_info for a given basic block. */
388 static void
389 df_scan_start_block (basic_block bb, FILE *file)
391 struct df_scan_bb_info *bb_info
392 = df_scan_get_bb_info (bb->index);
394 if (bb_info)
396 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
397 df_refs_chain_dump (bb_info->artificial_defs, true, file);
398 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
399 df_refs_chain_dump (bb_info->artificial_uses, true, file);
400 fprintf (file, "\n");
402 #if 0
404 rtx_insn *insn;
405 FOR_BB_INSNS (bb, insn)
406 if (INSN_P (insn))
407 df_insn_debug (insn, false, file);
409 #endif
412 static struct df_problem problem_SCAN =
414 DF_SCAN, /* Problem id. */
415 DF_NONE, /* Direction. */
416 df_scan_alloc, /* Allocate the problem specific data. */
417 NULL, /* Reset global information. */
418 df_scan_free_bb_info, /* Free basic block info. */
419 NULL, /* Local compute function. */
420 NULL, /* Init the solution specific data. */
421 NULL, /* Iterative solver. */
422 NULL, /* Confluence operator 0. */
423 NULL, /* Confluence operator n. */
424 NULL, /* Transfer function. */
425 NULL, /* Finalize function. */
426 df_scan_free, /* Free all of the problem information. */
427 NULL, /* Remove this problem from the stack of dataflow problems. */
428 df_scan_start_dump, /* Debugging. */
429 df_scan_start_block, /* Debugging start block. */
430 NULL, /* Debugging end block. */
431 NULL, /* Debugging start insn. */
432 NULL, /* Debugging end insn. */
433 NULL, /* Incremental solution verify start. */
434 NULL, /* Incremental solution verify end. */
435 NULL, /* Dependent problem. */
436 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
437 TV_DF_SCAN, /* Timing variable. */
438 false /* Reset blocks on dropping out of blocks_to_analyze. */
442 /* Create a new DATAFLOW instance and add it to an existing instance
443 of DF. The returned structure is what is used to get at the
444 solution. */
446 void
447 df_scan_add_problem (void)
449 df_add_problem (&problem_SCAN);
453 /*----------------------------------------------------------------------------
454 Storage Allocation Utilities
455 ----------------------------------------------------------------------------*/
458 /* First, grow the reg_info information. If the current size is less than
459 the number of pseudos, grow to 25% more than the number of
460 pseudos.
462 Second, assure that all of the slots up to max_reg_num have been
463 filled with reg_info structures. */
465 void
466 df_grow_reg_info (void)
468 unsigned int max_reg = max_reg_num ();
469 unsigned int new_size = max_reg;
470 struct df_scan_problem_data *problem_data
471 = (struct df_scan_problem_data *) df_scan->problem_data;
472 unsigned int i;
474 if (df->regs_size < new_size)
476 new_size += new_size / 4;
477 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
478 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
479 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
480 new_size);
481 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
482 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
483 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
484 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
485 df->regs_size = new_size;
488 for (i = df->regs_inited; i < max_reg; i++)
490 struct df_reg_info *reg_info;
492 // TODO
493 reg_info = problem_data->reg_pool->allocate ();
494 memset (reg_info, 0, sizeof (struct df_reg_info));
495 df->def_regs[i] = reg_info;
496 reg_info = problem_data->reg_pool->allocate ();
497 memset (reg_info, 0, sizeof (struct df_reg_info));
498 df->use_regs[i] = reg_info;
499 reg_info = problem_data->reg_pool->allocate ();
500 memset (reg_info, 0, sizeof (struct df_reg_info));
501 df->eq_use_regs[i] = reg_info;
502 df->def_info.begin[i] = 0;
503 df->def_info.count[i] = 0;
504 df->use_info.begin[i] = 0;
505 df->use_info.count[i] = 0;
508 df->regs_inited = max_reg;
512 /* Grow the ref information. */
514 static void
515 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
517 if (ref_info->refs_size < new_size)
519 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
520 memset (ref_info->refs + ref_info->refs_size, 0,
521 (new_size - ref_info->refs_size) *sizeof (df_ref));
522 ref_info->refs_size = new_size;
527 /* Check and grow the ref information if necessary. This routine
528 guarantees total_size + BITMAP_ADDEND amount of entries in refs
529 array. It updates ref_info->refs_size only and does not change
530 ref_info->total_size. */
532 static void
533 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
534 unsigned bitmap_addend)
536 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
538 int new_size = ref_info->total_size + bitmap_addend;
539 new_size += ref_info->total_size / 4;
540 df_grow_ref_info (ref_info, new_size);
545 /* Grow the ref information. If the current size is less than the
546 number of instructions, grow to 25% more than the number of
547 instructions. */
549 void
550 df_grow_insn_info (void)
552 unsigned int new_size = get_max_uid () + 1;
553 if (DF_INSN_SIZE () < new_size)
555 new_size += new_size / 4;
556 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
557 memset (df->insns + df->insns_size, 0,
558 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
559 DF_INSN_SIZE () = new_size;
566 /*----------------------------------------------------------------------------
567 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
568 ----------------------------------------------------------------------------*/
570 /* Rescan all of the block_to_analyze or all of the blocks in the
571 function if df_set_blocks if blocks_to_analyze is NULL; */
573 void
574 df_scan_blocks (void)
576 basic_block bb;
578 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
579 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
581 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
582 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
584 bitmap_ior_into (&df->eh_block_artificial_uses,
585 &df->regular_block_artificial_uses);
587 /* ENTRY and EXIT blocks have special defs/uses. */
588 df_get_entry_block_def_set (df->entry_block_defs);
589 df_record_entry_block_defs (df->entry_block_defs);
590 df_get_exit_block_use_set (df->exit_block_uses);
591 df_record_exit_block_uses (df->exit_block_uses);
592 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
593 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
595 /* Regular blocks */
596 FOR_EACH_BB_FN (bb, cfun)
598 unsigned int bb_index = bb->index;
599 df_bb_refs_record (bb_index, true);
603 /* Create new refs under address LOC within INSN. This function is
604 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
605 depending on whether LOC is inside PATTERN (INSN) or a note. */
607 void
608 df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
610 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
611 df_uses_record (NULL, loc, DF_REF_REG_USE,
612 BLOCK_FOR_INSN (insn),
613 DF_INSN_INFO_GET (insn),
614 ref_flags);
617 static void
618 df_install_ref_incremental (df_ref ref)
620 struct df_reg_info **reg_info;
621 struct df_ref_info *ref_info;
622 df_ref *ref_ptr;
623 bool add_to_table;
625 rtx_insn *insn = DF_REF_INSN (ref);
626 basic_block bb = BLOCK_FOR_INSN (insn);
628 if (DF_REF_REG_DEF_P (ref))
630 reg_info = df->def_regs;
631 ref_info = &df->def_info;
632 ref_ptr = &DF_INSN_DEFS (insn);
633 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
635 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
637 reg_info = df->eq_use_regs;
638 ref_info = &df->use_info;
639 ref_ptr = &DF_INSN_EQ_USES (insn);
640 switch (ref_info->ref_order)
642 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
643 case DF_REF_ORDER_BY_REG_WITH_NOTES:
644 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
645 add_to_table = true;
646 break;
647 default:
648 add_to_table = false;
649 break;
652 else
654 reg_info = df->use_regs;
655 ref_info = &df->use_info;
656 ref_ptr = &DF_INSN_USES (insn);
657 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
660 /* Do not add if ref is not in the right blocks. */
661 if (add_to_table && df->analyze_subset)
662 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
664 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
666 if (add_to_table)
667 switch (ref_info->ref_order)
669 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
670 case DF_REF_ORDER_BY_REG_WITH_NOTES:
671 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
672 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
673 break;
674 default:
675 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
676 break;
679 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
680 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
682 DF_REF_NEXT_LOC (ref) = *ref_ptr;
683 *ref_ptr = ref;
685 #if 0
686 if (dump_file)
688 fprintf (dump_file, "adding ref ");
689 df_ref_debug (ref, dump_file);
691 #endif
692 /* By adding the ref directly, df_insn_rescan my not find any
693 differences even though the block will have changed. So we need
694 to mark the block dirty ourselves. */
695 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
696 df_set_bb_dirty (bb);
701 /*----------------------------------------------------------------------------
702 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
703 ----------------------------------------------------------------------------*/
705 static void
706 df_free_ref (df_ref ref)
708 struct df_scan_problem_data *problem_data
709 = (struct df_scan_problem_data *) df_scan->problem_data;
711 switch (DF_REF_CLASS (ref))
713 case DF_REF_BASE:
714 problem_data->ref_base_pool->remove ((df_base_ref *) (ref));
715 break;
717 case DF_REF_ARTIFICIAL:
718 problem_data->ref_artificial_pool->remove
719 ((df_artificial_ref *) (ref));
720 break;
722 case DF_REF_REGULAR:
723 problem_data->ref_regular_pool->remove
724 ((df_regular_ref *) (ref));
725 break;
730 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
731 Also delete the def-use or use-def chain if it exists. */
733 static void
734 df_reg_chain_unlink (df_ref ref)
736 df_ref next = DF_REF_NEXT_REG (ref);
737 df_ref prev = DF_REF_PREV_REG (ref);
738 int id = DF_REF_ID (ref);
739 struct df_reg_info *reg_info;
740 df_ref *refs = NULL;
742 if (DF_REF_REG_DEF_P (ref))
744 int regno = DF_REF_REGNO (ref);
745 reg_info = DF_REG_DEF_GET (regno);
746 refs = df->def_info.refs;
748 else
750 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
752 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
753 switch (df->use_info.ref_order)
755 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
756 case DF_REF_ORDER_BY_REG_WITH_NOTES:
757 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
758 refs = df->use_info.refs;
759 break;
760 default:
761 break;
764 else
766 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
767 refs = df->use_info.refs;
771 if (refs)
773 if (df->analyze_subset)
775 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
776 refs[id] = NULL;
778 else
779 refs[id] = NULL;
782 /* Delete any def-use or use-def chains that start here. It is
783 possible that there is trash in this field. This happens for
784 insns that have been deleted when rescanning has been deferred
785 and the chain problem has also been deleted. The chain tear down
786 code skips deleted insns. */
787 if (df_chain && DF_REF_CHAIN (ref))
788 df_chain_unlink (ref);
790 reg_info->n_refs--;
791 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
793 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
794 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
797 /* Unlink from the reg chain. If there is no prev, this is the
798 first of the list. If not, just join the next and prev. */
799 if (prev)
800 DF_REF_NEXT_REG (prev) = next;
801 else
803 gcc_assert (reg_info->reg_chain == ref);
804 reg_info->reg_chain = next;
806 if (next)
807 DF_REF_PREV_REG (next) = prev;
809 df_free_ref (ref);
813 /* Create the insn record for INSN. If there was one there, zero it
814 out. */
816 struct df_insn_info *
817 df_insn_create_insn_record (rtx_insn *insn)
819 struct df_scan_problem_data *problem_data
820 = (struct df_scan_problem_data *) df_scan->problem_data;
821 struct df_insn_info *insn_rec;
823 df_grow_insn_info ();
824 insn_rec = DF_INSN_INFO_GET (insn);
825 if (!insn_rec)
827 insn_rec = problem_data->insn_pool->allocate ();
828 DF_INSN_INFO_SET (insn, insn_rec);
830 memset (insn_rec, 0, sizeof (struct df_insn_info));
831 insn_rec->insn = insn;
832 return insn_rec;
836 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
838 static void
839 df_ref_chain_delete_du_chain (df_ref ref)
841 for (; ref; ref = DF_REF_NEXT_LOC (ref))
842 /* CHAIN is allocated by DF_CHAIN. So make sure to
843 pass df_scan instance for the problem. */
844 if (DF_REF_CHAIN (ref))
845 df_chain_unlink (ref);
849 /* Delete all refs in the ref chain. */
851 static void
852 df_ref_chain_delete (df_ref ref)
854 df_ref next;
855 for (; ref; ref = next)
857 next = DF_REF_NEXT_LOC (ref);
858 df_reg_chain_unlink (ref);
863 /* Delete the hardreg chain. */
865 static void
866 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
868 struct df_scan_problem_data *problem_data
869 = (struct df_scan_problem_data *) df_scan->problem_data;
870 df_mw_hardreg *next;
872 for (; hardregs; hardregs = next)
874 next = DF_MWS_NEXT (hardregs);
875 problem_data->mw_reg_pool->remove (hardregs);
880 /* Delete all of the refs information from the insn with UID.
881 Internal helper for df_insn_delete, df_insn_rescan, and other
882 df-scan routines that don't have to work in deferred mode
883 and do not have to mark basic blocks for re-processing. */
885 static void
886 df_insn_info_delete (unsigned int uid)
888 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
890 bitmap_clear_bit (&df->insns_to_delete, uid);
891 bitmap_clear_bit (&df->insns_to_rescan, uid);
892 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
893 if (insn_info)
895 struct df_scan_problem_data *problem_data
896 = (struct df_scan_problem_data *) df_scan->problem_data;
898 /* In general, notes do not have the insn_info fields
899 initialized. However, combine deletes insns by changing them
900 to notes. How clever. So we cannot just check if it is a
901 valid insn before short circuiting this code, we need to see
902 if we actually initialized it. */
903 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
905 if (df_chain)
907 df_ref_chain_delete_du_chain (insn_info->defs);
908 df_ref_chain_delete_du_chain (insn_info->uses);
909 df_ref_chain_delete_du_chain (insn_info->eq_uses);
912 df_ref_chain_delete (insn_info->defs);
913 df_ref_chain_delete (insn_info->uses);
914 df_ref_chain_delete (insn_info->eq_uses);
916 problem_data->insn_pool->remove (insn_info);
917 DF_INSN_UID_SET (uid, NULL);
921 /* Delete all of the refs information from INSN, either right now
922 or marked for later in deferred mode. */
924 void
925 df_insn_delete (rtx_insn *insn)
927 unsigned int uid;
928 basic_block bb;
930 gcc_checking_assert (INSN_P (insn));
932 if (!df)
933 return;
935 uid = INSN_UID (insn);
936 bb = BLOCK_FOR_INSN (insn);
938 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
939 not exist anymore (as mentioned in df-core.c: "The only requirement
940 [for DF] is that there be a correct control flow graph." Clearly
941 that isn't the case after pass_free_cfg. But DF is freed much later
942 because some back-ends want to use DF info even though the CFG is
943 already gone. It's not clear to me whether that is safe, actually.
944 In any case, we expect BB to be non-NULL at least up to register
945 allocation, so disallow a non-NULL BB up to there. Not perfect
946 but better than nothing... */
947 gcc_checking_assert (bb != NULL || reload_completed);
949 df_grow_bb_info (df_scan);
950 df_grow_reg_info ();
952 /* The block must be marked as dirty now, rather than later as in
953 df_insn_rescan and df_notes_rescan because it may not be there at
954 rescanning time and the mark would blow up.
955 DEBUG_INSNs do not make a block's data flow solution dirty (at
956 worst the LUIDs are no longer contiguous). */
957 if (bb != NULL && NONDEBUG_INSN_P (insn))
958 df_set_bb_dirty (bb);
960 /* The client has deferred rescanning. */
961 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
963 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
964 if (insn_info)
966 bitmap_clear_bit (&df->insns_to_rescan, uid);
967 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
968 bitmap_set_bit (&df->insns_to_delete, uid);
970 if (dump_file)
971 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
972 return;
975 if (dump_file)
976 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
978 df_insn_info_delete (uid);
982 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
984 static void
985 df_free_collection_rec (struct df_collection_rec *collection_rec)
987 unsigned int ix;
988 struct df_scan_problem_data *problem_data
989 = (struct df_scan_problem_data *) df_scan->problem_data;
990 df_ref ref;
991 struct df_mw_hardreg *mw;
993 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
994 df_free_ref (ref);
995 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
996 df_free_ref (ref);
997 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
998 df_free_ref (ref);
999 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1000 problem_data->mw_reg_pool->remove (mw);
1002 collection_rec->def_vec.release ();
1003 collection_rec->use_vec.release ();
1004 collection_rec->eq_use_vec.release ();
1005 collection_rec->mw_vec.release ();
1008 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1010 bool
1011 df_insn_rescan (rtx_insn *insn)
1013 unsigned int uid = INSN_UID (insn);
1014 struct df_insn_info *insn_info = NULL;
1015 basic_block bb = BLOCK_FOR_INSN (insn);
1016 struct df_collection_rec collection_rec;
1018 if ((!df) || (!INSN_P (insn)))
1019 return false;
1021 if (!bb)
1023 if (dump_file)
1024 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1025 return false;
1028 /* The client has disabled rescanning and plans to do it itself. */
1029 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1030 return false;
1032 df_grow_bb_info (df_scan);
1033 df_grow_reg_info ();
1035 insn_info = DF_INSN_UID_SAFE_GET (uid);
1037 /* The client has deferred rescanning. */
1038 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1040 if (!insn_info)
1042 insn_info = df_insn_create_insn_record (insn);
1043 insn_info->defs = 0;
1044 insn_info->uses = 0;
1045 insn_info->eq_uses = 0;
1046 insn_info->mw_hardregs = 0;
1048 if (dump_file)
1049 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1051 bitmap_clear_bit (&df->insns_to_delete, uid);
1052 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1053 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1054 return false;
1057 bitmap_clear_bit (&df->insns_to_delete, uid);
1058 bitmap_clear_bit (&df->insns_to_rescan, uid);
1059 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1060 if (insn_info)
1062 int luid;
1063 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1064 /* If there's no change, return false. */
1065 if (the_same)
1067 df_free_collection_rec (&collection_rec);
1068 if (dump_file)
1069 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1070 return false;
1072 if (dump_file)
1073 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1075 /* There's change - we need to delete the existing info.
1076 Since the insn isn't moved, we can salvage its LUID. */
1077 luid = DF_INSN_LUID (insn);
1078 df_insn_info_delete (uid);
1079 df_insn_create_insn_record (insn);
1080 DF_INSN_LUID (insn) = luid;
1082 else
1084 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1085 df_insn_refs_collect (&collection_rec, bb, insn_info);
1086 if (dump_file)
1087 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1090 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1091 if (!DEBUG_INSN_P (insn))
1092 df_set_bb_dirty (bb);
1094 return true;
1097 /* Same as df_insn_rescan, but don't mark the basic block as
1098 dirty. */
1100 bool
1101 df_insn_rescan_debug_internal (rtx_insn *insn)
1103 unsigned int uid = INSN_UID (insn);
1104 struct df_insn_info *insn_info;
1106 gcc_assert (DEBUG_INSN_P (insn)
1107 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1109 if (!df)
1110 return false;
1112 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1113 if (!insn_info)
1114 return false;
1116 if (dump_file)
1117 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1119 bitmap_clear_bit (&df->insns_to_delete, uid);
1120 bitmap_clear_bit (&df->insns_to_rescan, uid);
1121 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1123 if (insn_info->defs == 0
1124 && insn_info->uses == 0
1125 && insn_info->eq_uses == 0
1126 && insn_info->mw_hardregs == 0)
1127 return false;
1129 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1131 if (df_chain)
1133 df_ref_chain_delete_du_chain (insn_info->defs);
1134 df_ref_chain_delete_du_chain (insn_info->uses);
1135 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1138 df_ref_chain_delete (insn_info->defs);
1139 df_ref_chain_delete (insn_info->uses);
1140 df_ref_chain_delete (insn_info->eq_uses);
1142 insn_info->defs = 0;
1143 insn_info->uses = 0;
1144 insn_info->eq_uses = 0;
1145 insn_info->mw_hardregs = 0;
1147 return true;
1151 /* Rescan all of the insns in the function. Note that the artificial
1152 uses and defs are not touched. This function will destroy def-use
1153 or use-def chains. */
1155 void
1156 df_insn_rescan_all (void)
1158 bool no_insn_rescan = false;
1159 bool defer_insn_rescan = false;
1160 basic_block bb;
1161 bitmap_iterator bi;
1162 unsigned int uid;
1163 bitmap_head tmp;
1165 bitmap_initialize (&tmp, &df_bitmap_obstack);
1167 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1169 df_clear_flags (DF_NO_INSN_RESCAN);
1170 no_insn_rescan = true;
1173 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1175 df_clear_flags (DF_DEFER_INSN_RESCAN);
1176 defer_insn_rescan = true;
1179 bitmap_copy (&tmp, &df->insns_to_delete);
1180 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1182 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1183 if (insn_info)
1184 df_insn_info_delete (uid);
1187 bitmap_clear (&tmp);
1188 bitmap_clear (&df->insns_to_delete);
1189 bitmap_clear (&df->insns_to_rescan);
1190 bitmap_clear (&df->insns_to_notes_rescan);
1192 FOR_EACH_BB_FN (bb, cfun)
1194 rtx_insn *insn;
1195 FOR_BB_INSNS (bb, insn)
1197 df_insn_rescan (insn);
1201 if (no_insn_rescan)
1202 df_set_flags (DF_NO_INSN_RESCAN);
1203 if (defer_insn_rescan)
1204 df_set_flags (DF_DEFER_INSN_RESCAN);
1208 /* Process all of the deferred rescans or deletions. */
1210 void
1211 df_process_deferred_rescans (void)
1213 bool no_insn_rescan = false;
1214 bool defer_insn_rescan = false;
1215 bitmap_iterator bi;
1216 unsigned int uid;
1217 bitmap_head tmp;
1219 bitmap_initialize (&tmp, &df_bitmap_obstack);
1221 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1223 df_clear_flags (DF_NO_INSN_RESCAN);
1224 no_insn_rescan = true;
1227 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1229 df_clear_flags (DF_DEFER_INSN_RESCAN);
1230 defer_insn_rescan = true;
1233 if (dump_file)
1234 fprintf (dump_file, "starting the processing of deferred insns\n");
1236 bitmap_copy (&tmp, &df->insns_to_delete);
1237 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1239 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1240 if (insn_info)
1241 df_insn_info_delete (uid);
1244 bitmap_copy (&tmp, &df->insns_to_rescan);
1245 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1247 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1248 if (insn_info)
1249 df_insn_rescan (insn_info->insn);
1252 bitmap_copy (&tmp, &df->insns_to_notes_rescan);
1253 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1255 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1256 if (insn_info)
1257 df_notes_rescan (insn_info->insn);
1260 if (dump_file)
1261 fprintf (dump_file, "ending the processing of deferred insns\n");
1263 bitmap_clear (&tmp);
1264 bitmap_clear (&df->insns_to_delete);
1265 bitmap_clear (&df->insns_to_rescan);
1266 bitmap_clear (&df->insns_to_notes_rescan);
1268 if (no_insn_rescan)
1269 df_set_flags (DF_NO_INSN_RESCAN);
1270 if (defer_insn_rescan)
1271 df_set_flags (DF_DEFER_INSN_RESCAN);
1273 /* If someone changed regs_ever_live during this pass, fix up the
1274 entry and exit blocks. */
1275 if (df->redo_entry_and_exit)
1277 df_update_entry_exit_and_calls ();
1278 df->redo_entry_and_exit = false;
1283 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1284 the uses if INCLUDE_USES. Include the eq_uses if
1285 INCLUDE_EQ_USES. */
1287 static unsigned int
1288 df_count_refs (bool include_defs, bool include_uses,
1289 bool include_eq_uses)
1291 unsigned int regno;
1292 int size = 0;
1293 unsigned int m = df->regs_inited;
1295 for (regno = 0; regno < m; regno++)
1297 if (include_defs)
1298 size += DF_REG_DEF_COUNT (regno);
1299 if (include_uses)
1300 size += DF_REG_USE_COUNT (regno);
1301 if (include_eq_uses)
1302 size += DF_REG_EQ_USE_COUNT (regno);
1304 return size;
1308 /* Take build ref table for either the uses or defs from the reg-use
1309 or reg-def chains. This version processes the refs in reg order
1310 which is likely to be best if processing the whole function. */
1312 static void
1313 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1314 bool include_defs,
1315 bool include_uses,
1316 bool include_eq_uses)
1318 unsigned int m = df->regs_inited;
1319 unsigned int regno;
1320 unsigned int offset = 0;
1321 unsigned int start;
1323 if (df->changeable_flags & DF_NO_HARD_REGS)
1325 start = FIRST_PSEUDO_REGISTER;
1326 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1327 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1329 else
1330 start = 0;
1332 ref_info->total_size
1333 = df_count_refs (include_defs, include_uses, include_eq_uses);
1335 df_check_and_grow_ref_info (ref_info, 1);
1337 for (regno = start; regno < m; regno++)
1339 int count = 0;
1340 ref_info->begin[regno] = offset;
1341 if (include_defs)
1343 df_ref ref = DF_REG_DEF_CHAIN (regno);
1344 while (ref)
1346 ref_info->refs[offset] = ref;
1347 DF_REF_ID (ref) = offset++;
1348 count++;
1349 ref = DF_REF_NEXT_REG (ref);
1350 gcc_checking_assert (offset < ref_info->refs_size);
1353 if (include_uses)
1355 df_ref ref = DF_REG_USE_CHAIN (regno);
1356 while (ref)
1358 ref_info->refs[offset] = ref;
1359 DF_REF_ID (ref) = offset++;
1360 count++;
1361 ref = DF_REF_NEXT_REG (ref);
1362 gcc_checking_assert (offset < ref_info->refs_size);
1365 if (include_eq_uses)
1367 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1368 while (ref)
1370 ref_info->refs[offset] = ref;
1371 DF_REF_ID (ref) = offset++;
1372 count++;
1373 ref = DF_REF_NEXT_REG (ref);
1374 gcc_checking_assert (offset < ref_info->refs_size);
1377 ref_info->count[regno] = count;
1380 /* The bitmap size is not decremented when refs are deleted. So
1381 reset it now that we have squished out all of the empty
1382 slots. */
1383 ref_info->table_size = offset;
1387 /* Take build ref table for either the uses or defs from the reg-use
1388 or reg-def chains. This version processes the refs in insn order
1389 which is likely to be best if processing some segment of the
1390 function. */
1392 static void
1393 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1394 bool include_defs,
1395 bool include_uses,
1396 bool include_eq_uses)
1398 bitmap_iterator bi;
1399 unsigned int bb_index;
1400 unsigned int m = df->regs_inited;
1401 unsigned int offset = 0;
1402 unsigned int r;
1403 unsigned int start
1404 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1406 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1407 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1409 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1410 df_check_and_grow_ref_info (ref_info, 1);
1412 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1414 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1415 rtx_insn *insn;
1416 df_ref def, use;
1418 if (include_defs)
1419 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1421 unsigned int regno = DF_REF_REGNO (def);
1422 ref_info->count[regno]++;
1424 if (include_uses)
1425 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1427 unsigned int regno = DF_REF_REGNO (use);
1428 ref_info->count[regno]++;
1431 FOR_BB_INSNS (bb, insn)
1433 if (INSN_P (insn))
1435 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1437 if (include_defs)
1438 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1440 unsigned int regno = DF_REF_REGNO (def);
1441 ref_info->count[regno]++;
1443 if (include_uses)
1444 FOR_EACH_INSN_INFO_USE (use, insn_info)
1446 unsigned int regno = DF_REF_REGNO (use);
1447 ref_info->count[regno]++;
1449 if (include_eq_uses)
1450 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1452 unsigned int regno = DF_REF_REGNO (use);
1453 ref_info->count[regno]++;
1459 for (r = start; r < m; r++)
1461 ref_info->begin[r] = offset;
1462 offset += ref_info->count[r];
1463 ref_info->count[r] = 0;
1466 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1468 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1469 rtx_insn *insn;
1470 df_ref def, use;
1472 if (include_defs)
1473 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1475 unsigned int regno = DF_REF_REGNO (def);
1476 if (regno >= start)
1478 unsigned int id
1479 = ref_info->begin[regno] + ref_info->count[regno]++;
1480 DF_REF_ID (def) = id;
1481 ref_info->refs[id] = def;
1484 if (include_uses)
1485 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1487 unsigned int regno = DF_REF_REGNO (def);
1488 if (regno >= start)
1490 unsigned int id
1491 = ref_info->begin[regno] + ref_info->count[regno]++;
1492 DF_REF_ID (use) = id;
1493 ref_info->refs[id] = use;
1497 FOR_BB_INSNS (bb, insn)
1499 if (INSN_P (insn))
1501 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1503 if (include_defs)
1504 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1506 unsigned int regno = DF_REF_REGNO (def);
1507 if (regno >= start)
1509 unsigned int id
1510 = ref_info->begin[regno] + ref_info->count[regno]++;
1511 DF_REF_ID (def) = id;
1512 ref_info->refs[id] = def;
1515 if (include_uses)
1516 FOR_EACH_INSN_INFO_USE (use, insn_info)
1518 unsigned int regno = DF_REF_REGNO (use);
1519 if (regno >= start)
1521 unsigned int id
1522 = ref_info->begin[regno] + ref_info->count[regno]++;
1523 DF_REF_ID (use) = id;
1524 ref_info->refs[id] = use;
1527 if (include_eq_uses)
1528 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1530 unsigned int regno = DF_REF_REGNO (use);
1531 if (regno >= start)
1533 unsigned int id
1534 = ref_info->begin[regno] + ref_info->count[regno]++;
1535 DF_REF_ID (use) = id;
1536 ref_info->refs[id] = use;
1543 /* The bitmap size is not decremented when refs are deleted. So
1544 reset it now that we have squished out all of the empty
1545 slots. */
1547 ref_info->table_size = offset;
1550 /* Take build ref table for either the uses or defs from the reg-use
1551 or reg-def chains. */
1553 static void
1554 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1555 bool include_defs,
1556 bool include_uses,
1557 bool include_eq_uses)
1559 if (df->analyze_subset)
1560 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1561 include_uses, include_eq_uses);
1562 else
1563 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1564 include_uses, include_eq_uses);
1568 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1569 static unsigned int
1570 df_add_refs_to_table (unsigned int offset,
1571 struct df_ref_info *ref_info,
1572 df_ref ref)
1574 for (; ref; ref = DF_REF_NEXT_LOC (ref))
1575 if (!(df->changeable_flags & DF_NO_HARD_REGS)
1576 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1578 ref_info->refs[offset] = ref;
1579 DF_REF_ID (ref) = offset++;
1581 return offset;
1585 /* Count the number of refs in all of the insns of BB. Include the
1586 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1587 eq_uses if INCLUDE_EQ_USES. */
1589 static unsigned int
1590 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1591 struct df_ref_info *ref_info,
1592 bool include_defs, bool include_uses,
1593 bool include_eq_uses)
1595 rtx_insn *insn;
1597 if (include_defs)
1598 offset = df_add_refs_to_table (offset, ref_info,
1599 df_get_artificial_defs (bb->index));
1600 if (include_uses)
1601 offset = df_add_refs_to_table (offset, ref_info,
1602 df_get_artificial_uses (bb->index));
1604 FOR_BB_INSNS (bb, insn)
1605 if (INSN_P (insn))
1607 unsigned int uid = INSN_UID (insn);
1608 if (include_defs)
1609 offset = df_add_refs_to_table (offset, ref_info,
1610 DF_INSN_UID_DEFS (uid));
1611 if (include_uses)
1612 offset = df_add_refs_to_table (offset, ref_info,
1613 DF_INSN_UID_USES (uid));
1614 if (include_eq_uses)
1615 offset = df_add_refs_to_table (offset, ref_info,
1616 DF_INSN_UID_EQ_USES (uid));
1618 return offset;
1622 /* Organize the refs by insn into the table in REF_INFO. If
1623 blocks_to_analyze is defined, use that set, otherwise the entire
1624 program. Include the defs if INCLUDE_DEFS. Include the uses if
1625 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1627 static void
1628 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1629 bool include_defs, bool include_uses,
1630 bool include_eq_uses)
1632 basic_block bb;
1633 unsigned int offset = 0;
1635 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1636 df_check_and_grow_ref_info (ref_info, 1);
1637 if (df->blocks_to_analyze)
1639 bitmap_iterator bi;
1640 unsigned int index;
1642 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1644 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1645 index),
1646 offset, ref_info,
1647 include_defs, include_uses,
1648 include_eq_uses);
1651 ref_info->table_size = offset;
1653 else
1655 FOR_ALL_BB_FN (bb, cfun)
1656 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1657 include_defs, include_uses,
1658 include_eq_uses);
1659 ref_info->table_size = offset;
1664 /* If the use refs in DF are not organized, reorganize them. */
1666 void
1667 df_maybe_reorganize_use_refs (enum df_ref_order order)
1669 if (order == df->use_info.ref_order)
1670 return;
1672 switch (order)
1674 case DF_REF_ORDER_BY_REG:
1675 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1676 break;
1678 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1679 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1680 break;
1682 case DF_REF_ORDER_BY_INSN:
1683 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1684 break;
1686 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1687 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1688 break;
1690 case DF_REF_ORDER_NO_TABLE:
1691 free (df->use_info.refs);
1692 df->use_info.refs = NULL;
1693 df->use_info.refs_size = 0;
1694 break;
1696 case DF_REF_ORDER_UNORDERED:
1697 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1698 gcc_unreachable ();
1699 break;
1702 df->use_info.ref_order = order;
1706 /* If the def refs in DF are not organized, reorganize them. */
1708 void
1709 df_maybe_reorganize_def_refs (enum df_ref_order order)
1711 if (order == df->def_info.ref_order)
1712 return;
1714 switch (order)
1716 case DF_REF_ORDER_BY_REG:
1717 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1718 break;
1720 case DF_REF_ORDER_BY_INSN:
1721 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1722 break;
1724 case DF_REF_ORDER_NO_TABLE:
1725 free (df->def_info.refs);
1726 df->def_info.refs = NULL;
1727 df->def_info.refs_size = 0;
1728 break;
1730 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1731 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1732 case DF_REF_ORDER_UNORDERED:
1733 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1734 gcc_unreachable ();
1735 break;
1738 df->def_info.ref_order = order;
1742 /* Change all of the basic block references in INSN to use the insn's
1743 current basic block. This function is called from routines that move
1744 instructions from one block to another. */
1746 void
1747 df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1749 basic_block old_bb = BLOCK_FOR_INSN (insn);
1750 struct df_insn_info *insn_info;
1751 unsigned int uid = INSN_UID (insn);
1753 if (old_bb == new_bb)
1754 return;
1756 set_block_for_insn (insn, new_bb);
1758 if (!df)
1759 return;
1761 if (dump_file)
1762 fprintf (dump_file, "changing bb of uid %d\n", uid);
1764 insn_info = DF_INSN_UID_SAFE_GET (uid);
1765 if (insn_info == NULL)
1767 if (dump_file)
1768 fprintf (dump_file, " unscanned insn\n");
1769 df_insn_rescan (insn);
1770 return;
1773 if (!INSN_P (insn))
1774 return;
1776 df_set_bb_dirty (new_bb);
1777 if (old_bb)
1779 if (dump_file)
1780 fprintf (dump_file, " from %d to %d\n",
1781 old_bb->index, new_bb->index);
1782 df_set_bb_dirty (old_bb);
1784 else
1785 if (dump_file)
1786 fprintf (dump_file, " to %d\n", new_bb->index);
1790 /* Helper function for df_ref_change_reg_with_loc. */
1792 static void
1793 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1794 struct df_reg_info *new_df,
1795 unsigned int new_regno, rtx loc)
1797 df_ref the_ref = old_df->reg_chain;
1799 while (the_ref)
1801 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1802 && DF_REF_LOC (the_ref)
1803 && (*DF_REF_LOC (the_ref) == loc))
1805 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1806 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1807 df_ref *ref_ptr;
1808 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1810 DF_REF_REGNO (the_ref) = new_regno;
1811 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1813 /* Pull the_ref out of the old regno chain. */
1814 if (prev_ref)
1815 DF_REF_NEXT_REG (prev_ref) = next_ref;
1816 else
1817 old_df->reg_chain = next_ref;
1818 if (next_ref)
1819 DF_REF_PREV_REG (next_ref) = prev_ref;
1820 old_df->n_refs--;
1822 /* Put the ref into the new regno chain. */
1823 DF_REF_PREV_REG (the_ref) = NULL;
1824 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1825 if (new_df->reg_chain)
1826 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1827 new_df->reg_chain = the_ref;
1828 new_df->n_refs++;
1829 if (DF_REF_BB (the_ref))
1830 df_set_bb_dirty (DF_REF_BB (the_ref));
1832 /* Need to sort the record again that the ref was in because
1833 the regno is a sorting key. First, find the right
1834 record. */
1835 if (DF_REF_REG_DEF_P (the_ref))
1836 ref_ptr = &insn_info->defs;
1837 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1838 ref_ptr = &insn_info->eq_uses;
1839 else
1840 ref_ptr = &insn_info->uses;
1841 if (dump_file)
1842 fprintf (dump_file, "changing reg in insn %d\n",
1843 DF_REF_INSN_UID (the_ref));
1845 /* Stop if we find the current reference or where the reference
1846 needs to be. */
1847 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1848 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1849 if (*ref_ptr != the_ref)
1851 /* The reference needs to be promoted up the list. */
1852 df_ref next = DF_REF_NEXT_LOC (the_ref);
1853 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1854 *ref_ptr = the_ref;
1856 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1857 while (*ref_ptr != the_ref);
1858 *ref_ptr = next;
1860 else if (DF_REF_NEXT_LOC (the_ref)
1861 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1863 /* The reference needs to be demoted down the list. */
1864 *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1866 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1867 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1868 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1869 *ref_ptr = the_ref;
1872 the_ref = next_ref;
1874 else
1875 the_ref = DF_REF_NEXT_REG (the_ref);
1880 /* Change the regno of register LOC to NEW_REGNO and update the df
1881 information accordingly. Refs that do not match LOC are not changed
1882 which means that artificial refs are not changed since they have no loc.
1883 This call is to support the SET_REGNO macro. */
1885 void
1886 df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1888 unsigned int old_regno = REGNO (loc);
1889 if (old_regno == new_regno)
1890 return;
1892 if (df)
1894 df_grow_reg_info ();
1896 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1897 DF_REG_DEF_GET (new_regno),
1898 new_regno, loc);
1899 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1900 DF_REG_USE_GET (new_regno),
1901 new_regno, loc);
1902 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1903 DF_REG_EQ_USE_GET (new_regno),
1904 new_regno, loc);
1906 set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1910 /* Delete the mw_hardregs that point into the eq_notes. */
1912 static void
1913 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1915 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1916 struct df_scan_problem_data *problem_data
1917 = (struct df_scan_problem_data *) df_scan->problem_data;
1919 while (*mw_ptr)
1921 df_mw_hardreg *mw = *mw_ptr;
1922 if (mw->flags & DF_REF_IN_NOTE)
1924 *mw_ptr = DF_MWS_NEXT (mw);
1925 problem_data->mw_reg_pool->remove (mw);
1927 else
1928 mw_ptr = &DF_MWS_NEXT (mw);
1933 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1935 void
1936 df_notes_rescan (rtx_insn *insn)
1938 struct df_insn_info *insn_info;
1939 unsigned int uid = INSN_UID (insn);
1941 if (!df)
1942 return;
1944 /* The client has disabled rescanning and plans to do it itself. */
1945 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1946 return;
1948 /* Do nothing if the insn hasn't been emitted yet. */
1949 if (!BLOCK_FOR_INSN (insn))
1950 return;
1952 df_grow_bb_info (df_scan);
1953 df_grow_reg_info ();
1955 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1957 /* The client has deferred rescanning. */
1958 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1960 if (!insn_info)
1962 insn_info = df_insn_create_insn_record (insn);
1963 insn_info->defs = 0;
1964 insn_info->uses = 0;
1965 insn_info->eq_uses = 0;
1966 insn_info->mw_hardregs = 0;
1969 bitmap_clear_bit (&df->insns_to_delete, uid);
1970 /* If the insn is set to be rescanned, it does not need to also
1971 be notes rescanned. */
1972 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1973 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1974 return;
1977 bitmap_clear_bit (&df->insns_to_delete, uid);
1978 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1980 if (insn_info)
1982 basic_block bb = BLOCK_FOR_INSN (insn);
1983 rtx note;
1984 struct df_collection_rec collection_rec;
1985 unsigned int i;
1987 df_mw_hardreg_chain_delete_eq_uses (insn_info);
1988 df_ref_chain_delete (insn_info->eq_uses);
1989 insn_info->eq_uses = NULL;
1991 /* Process REG_EQUIV/REG_EQUAL notes */
1992 for (note = REG_NOTES (insn); note;
1993 note = XEXP (note, 1))
1995 switch (REG_NOTE_KIND (note))
1997 case REG_EQUIV:
1998 case REG_EQUAL:
1999 df_uses_record (&collection_rec,
2000 &XEXP (note, 0), DF_REF_REG_USE,
2001 bb, insn_info, DF_REF_IN_NOTE);
2002 default:
2003 break;
2007 /* Find some place to put any new mw_hardregs. */
2008 df_canonize_collection_rec (&collection_rec);
2009 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2010 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2012 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2013 mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2014 DF_MWS_NEXT (mw) = *mw_ptr;
2015 *mw_ptr = mw;
2016 mw_ptr = &DF_MWS_NEXT (mw);
2018 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2020 else
2021 df_insn_rescan (insn);
2026 /*----------------------------------------------------------------------------
2027 Hard core instruction scanning code. No external interfaces here,
2028 just a lot of routines that look inside insns.
2029 ----------------------------------------------------------------------------*/
2032 /* Return true if the contents of two df_ref's are identical.
2033 It ignores DF_REF_MARKER. */
2035 static bool
2036 df_ref_equal_p (df_ref ref1, df_ref ref2)
2038 if (!ref2)
2039 return false;
2041 if (ref1 == ref2)
2042 return true;
2044 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2045 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2046 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2047 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2048 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2049 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2050 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2051 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2052 return false;
2054 switch (DF_REF_CLASS (ref1))
2056 case DF_REF_ARTIFICIAL:
2057 case DF_REF_BASE:
2058 return true;
2060 case DF_REF_REGULAR:
2061 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2063 default:
2064 gcc_unreachable ();
2066 return false;
2070 /* Compare REF1 and REF2 for sorting. This is only called from places
2071 where all of the refs are of the same type, in the same insn, and
2072 have the same bb. So these fields are not checked. */
2074 static int
2075 df_ref_compare (df_ref ref1, df_ref ref2)
2077 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2078 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2080 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2081 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2083 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2084 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2086 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2087 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2089 /* Cannot look at the LOC field on artificial refs. */
2090 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2091 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2092 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2094 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2096 /* If two refs are identical except that one of them has is from
2097 a mw and one is not, we need to have the one with the mw
2098 first. */
2099 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2100 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2101 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2102 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2103 return -1;
2104 else
2105 return 1;
2108 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2111 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2113 static int
2114 df_ref_ptr_compare (const void *r1, const void *r2)
2116 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2119 /* Sort and compress a set of refs. */
2121 static void
2122 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2124 unsigned int count;
2125 unsigned int i;
2126 unsigned int dist = 0;
2128 count = ref_vec->length ();
2130 /* If there are 1 or 0 elements, there is nothing to do. */
2131 if (count < 2)
2132 return;
2133 else if (count == 2)
2135 df_ref r0 = (*ref_vec)[0];
2136 df_ref r1 = (*ref_vec)[1];
2137 if (df_ref_compare (r0, r1) > 0)
2138 std::swap ((*ref_vec)[0], (*ref_vec)[1]);
2140 else
2142 for (i = 0; i < count - 1; i++)
2144 df_ref r0 = (*ref_vec)[i];
2145 df_ref r1 = (*ref_vec)[i + 1];
2146 if (df_ref_compare (r0, r1) >= 0)
2147 break;
2149 /* If the array is already strictly ordered,
2150 which is the most common case for large COUNT case
2151 (which happens for CALL INSNs),
2152 no need to sort and filter out duplicate.
2153 Simply return the count.
2154 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2155 of DF_REF_COMPARE. */
2156 if (i == count - 1)
2157 return;
2158 ref_vec->qsort (df_ref_ptr_compare);
2161 for (i=0; i<count-dist; i++)
2163 /* Find the next ref that is not equal to the current ref. */
2164 while (i + dist + 1 < count
2165 && df_ref_equal_p ((*ref_vec)[i],
2166 (*ref_vec)[i + dist + 1]))
2168 df_free_ref ((*ref_vec)[i + dist + 1]);
2169 dist++;
2171 /* Copy it down to the next position. */
2172 if (dist && i + dist + 1 < count)
2173 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2176 count -= dist;
2177 ref_vec->truncate (count);
2181 /* Return true if the contents of two df_ref's are identical.
2182 It ignores DF_REF_MARKER. */
2184 static bool
2185 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2187 if (!mw2)
2188 return false;
2189 return (mw1 == mw2) ||
2190 (mw1->mw_reg == mw2->mw_reg
2191 && mw1->type == mw2->type
2192 && mw1->flags == mw2->flags
2193 && mw1->start_regno == mw2->start_regno
2194 && mw1->end_regno == mw2->end_regno);
2198 /* Compare MW1 and MW2 for sorting. */
2200 static int
2201 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2203 if (mw1->type != mw2->type)
2204 return mw1->type - mw2->type;
2206 if (mw1->flags != mw2->flags)
2207 return mw1->flags - mw2->flags;
2209 if (mw1->start_regno != mw2->start_regno)
2210 return mw1->start_regno - mw2->start_regno;
2212 if (mw1->end_regno != mw2->end_regno)
2213 return mw1->end_regno - mw2->end_regno;
2215 if (mw1->mw_reg != mw2->mw_reg)
2216 return mw1->mw_order - mw2->mw_order;
2218 return 0;
2221 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2223 static int
2224 df_mw_ptr_compare (const void *m1, const void *m2)
2226 return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2227 *(const df_mw_hardreg *const *) m2);
2230 /* Sort and compress a set of refs. */
2232 static void
2233 df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec)
2235 unsigned int count;
2236 struct df_scan_problem_data *problem_data
2237 = (struct df_scan_problem_data *) df_scan->problem_data;
2238 unsigned int i;
2239 unsigned int dist = 0;
2241 count = mw_vec->length ();
2242 if (count < 2)
2243 return;
2244 else if (count == 2)
2246 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2247 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2248 if (df_mw_compare (m0, m1) > 0)
2250 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2251 (*mw_vec)[0] = (*mw_vec)[1];
2252 (*mw_vec)[1] = tmp;
2255 else
2256 mw_vec->qsort (df_mw_ptr_compare);
2258 for (i=0; i<count-dist; i++)
2260 /* Find the next ref that is not equal to the current ref. */
2261 while (i + dist + 1 < count
2262 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2264 problem_data->mw_reg_pool->remove ((*mw_vec)[i + dist + 1]);
2265 dist++;
2267 /* Copy it down to the next position. */
2268 if (dist && i + dist + 1 < count)
2269 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2272 count -= dist;
2273 mw_vec->truncate (count);
2277 /* Sort and remove duplicates from the COLLECTION_REC. */
2279 static void
2280 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2282 df_sort_and_compress_refs (&collection_rec->def_vec);
2283 df_sort_and_compress_refs (&collection_rec->use_vec);
2284 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2285 df_sort_and_compress_mws (&collection_rec->mw_vec);
2289 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2291 static void
2292 df_install_ref (df_ref this_ref,
2293 struct df_reg_info *reg_info,
2294 struct df_ref_info *ref_info,
2295 bool add_to_table)
2297 unsigned int regno = DF_REF_REGNO (this_ref);
2298 /* Add the ref to the reg_{def,use,eq_use} chain. */
2299 df_ref head = reg_info->reg_chain;
2301 reg_info->reg_chain = this_ref;
2302 reg_info->n_refs++;
2304 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2306 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2307 df->hard_regs_live_count[regno]++;
2310 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2311 && DF_REF_PREV_REG (this_ref) == NULL);
2313 DF_REF_NEXT_REG (this_ref) = head;
2315 /* We cannot actually link to the head of the chain. */
2316 DF_REF_PREV_REG (this_ref) = NULL;
2318 if (head)
2319 DF_REF_PREV_REG (head) = this_ref;
2321 if (add_to_table)
2323 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2324 df_check_and_grow_ref_info (ref_info, 1);
2325 DF_REF_ID (this_ref) = ref_info->table_size;
2326 /* Add the ref to the big array of defs. */
2327 ref_info->refs[ref_info->table_size] = this_ref;
2328 ref_info->table_size++;
2330 else
2331 DF_REF_ID (this_ref) = -1;
2333 ref_info->total_size++;
2337 /* This function takes one of the groups of refs (defs, uses or
2338 eq_uses) and installs the entire group into the insn. It also adds
2339 each of these refs into the appropriate chains. */
2341 static df_ref
2342 df_install_refs (basic_block bb,
2343 const vec<df_ref, va_heap> *old_vec,
2344 struct df_reg_info **reg_info,
2345 struct df_ref_info *ref_info,
2346 bool is_notes)
2348 unsigned int count = old_vec->length ();
2349 if (count)
2351 bool add_to_table;
2352 df_ref this_ref;
2353 unsigned int ix;
2355 switch (ref_info->ref_order)
2357 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2358 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2359 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2360 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2361 add_to_table = true;
2362 break;
2363 case DF_REF_ORDER_UNORDERED:
2364 case DF_REF_ORDER_BY_REG:
2365 case DF_REF_ORDER_BY_INSN:
2366 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2367 add_to_table = !is_notes;
2368 break;
2369 default:
2370 add_to_table = false;
2371 break;
2374 /* Do not add if ref is not in the right blocks. */
2375 if (add_to_table && df->analyze_subset)
2376 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2378 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2380 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2381 ? (*old_vec)[ix + 1]
2382 : NULL);
2383 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2384 ref_info, add_to_table);
2386 return (*old_vec)[0];
2388 else
2389 return 0;
2393 /* This function takes the mws installs the entire group into the
2394 insn. */
2396 static struct df_mw_hardreg *
2397 df_install_mws (const vec<df_mw_hardreg_ptr, va_heap> *old_vec)
2399 unsigned int count = old_vec->length ();
2400 if (count)
2402 for (unsigned int i = 0; i < count - 1; i++)
2403 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2404 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2405 return (*old_vec)[0];
2407 else
2408 return 0;
2412 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2413 chains and update other necessary information. */
2415 static void
2416 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2417 basic_block bb, rtx_insn *insn, unsigned int flags)
2419 if (insn)
2421 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2422 /* If there is a vector in the collection rec, add it to the
2423 insn. A null rec is a signal that the caller will handle the
2424 chain specially. */
2425 if (flags & copy_defs)
2427 gcc_checking_assert (!insn_rec->defs);
2428 insn_rec->defs
2429 = df_install_refs (bb, &collection_rec->def_vec,
2430 df->def_regs,
2431 &df->def_info, false);
2433 if (flags & copy_uses)
2435 gcc_checking_assert (!insn_rec->uses);
2436 insn_rec->uses
2437 = df_install_refs (bb, &collection_rec->use_vec,
2438 df->use_regs,
2439 &df->use_info, false);
2441 if (flags & copy_eq_uses)
2443 gcc_checking_assert (!insn_rec->eq_uses);
2444 insn_rec->eq_uses
2445 = df_install_refs (bb, &collection_rec->eq_use_vec,
2446 df->eq_use_regs,
2447 &df->use_info, true);
2449 if (flags & copy_mw)
2451 gcc_checking_assert (!insn_rec->mw_hardregs);
2452 insn_rec->mw_hardregs
2453 = df_install_mws (&collection_rec->mw_vec);
2456 else
2458 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2460 gcc_checking_assert (!bb_info->artificial_defs);
2461 bb_info->artificial_defs
2462 = df_install_refs (bb, &collection_rec->def_vec,
2463 df->def_regs,
2464 &df->def_info, false);
2465 gcc_checking_assert (!bb_info->artificial_uses);
2466 bb_info->artificial_uses
2467 = df_install_refs (bb, &collection_rec->use_vec,
2468 df->use_regs,
2469 &df->use_info, false);
2474 /* Allocate a ref and initialize its fields. */
2476 static df_ref
2477 df_ref_create_structure (enum df_ref_class cl,
2478 struct df_collection_rec *collection_rec,
2479 rtx reg, rtx *loc,
2480 basic_block bb, struct df_insn_info *info,
2481 enum df_ref_type ref_type,
2482 int ref_flags)
2484 df_ref this_ref = NULL;
2485 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2486 struct df_scan_problem_data *problem_data
2487 = (struct df_scan_problem_data *) df_scan->problem_data;
2489 switch (cl)
2491 case DF_REF_BASE:
2492 this_ref = (df_ref) (problem_data->ref_base_pool->allocate ());
2493 gcc_checking_assert (loc == NULL);
2494 break;
2496 case DF_REF_ARTIFICIAL:
2497 this_ref = (df_ref) (problem_data->ref_artificial_pool->allocate ());
2498 this_ref->artificial_ref.bb = bb;
2499 gcc_checking_assert (loc == NULL);
2500 break;
2502 case DF_REF_REGULAR:
2503 this_ref = (df_ref) (problem_data->ref_regular_pool->allocate ());
2504 this_ref->regular_ref.loc = loc;
2505 gcc_checking_assert (loc);
2506 break;
2509 DF_REF_CLASS (this_ref) = cl;
2510 DF_REF_ID (this_ref) = -1;
2511 DF_REF_REG (this_ref) = reg;
2512 DF_REF_REGNO (this_ref) = regno;
2513 DF_REF_TYPE (this_ref) = ref_type;
2514 DF_REF_INSN_INFO (this_ref) = info;
2515 DF_REF_CHAIN (this_ref) = NULL;
2516 DF_REF_FLAGS (this_ref) = ref_flags;
2517 DF_REF_NEXT_REG (this_ref) = NULL;
2518 DF_REF_PREV_REG (this_ref) = NULL;
2519 DF_REF_ORDER (this_ref) = df->ref_order++;
2521 /* We need to clear this bit because fwprop, and in the future
2522 possibly other optimizations sometimes create new refs using ond
2523 refs as the model. */
2524 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2526 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2527 if (regno < FIRST_PSEUDO_REGISTER
2528 && !DF_REF_IS_ARTIFICIAL (this_ref)
2529 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2531 if (DF_REF_REG_DEF_P (this_ref))
2533 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2534 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2536 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2537 && (regno == FRAME_POINTER_REGNUM
2538 || regno == ARG_POINTER_REGNUM)))
2539 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2542 if (collection_rec)
2544 if (DF_REF_REG_DEF_P (this_ref))
2545 collection_rec->def_vec.safe_push (this_ref);
2546 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2547 collection_rec->eq_use_vec.safe_push (this_ref);
2548 else
2549 collection_rec->use_vec.safe_push (this_ref);
2551 else
2552 df_install_ref_incremental (this_ref);
2554 return this_ref;
2558 /* Create new references of type DF_REF_TYPE for each part of register REG
2559 at address LOC within INSN of BB. */
2562 static void
2563 df_ref_record (enum df_ref_class cl,
2564 struct df_collection_rec *collection_rec,
2565 rtx reg, rtx *loc,
2566 basic_block bb, struct df_insn_info *insn_info,
2567 enum df_ref_type ref_type,
2568 int ref_flags)
2570 unsigned int regno;
2572 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2574 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2575 if (regno < FIRST_PSEUDO_REGISTER)
2577 struct df_mw_hardreg *hardreg = NULL;
2578 struct df_scan_problem_data *problem_data
2579 = (struct df_scan_problem_data *) df_scan->problem_data;
2580 unsigned int i;
2581 unsigned int endregno;
2582 df_ref ref;
2584 if (GET_CODE (reg) == SUBREG)
2586 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2587 SUBREG_BYTE (reg), GET_MODE (reg));
2588 endregno = regno + subreg_nregs (reg);
2590 else
2591 endregno = END_REGNO (reg);
2593 /* If this is a multiword hardreg, we create some extra
2594 datastructures that will enable us to easily build REG_DEAD
2595 and REG_UNUSED notes. */
2596 if (collection_rec
2597 && (endregno != regno + 1) && insn_info)
2599 /* Sets to a subreg of a multiword register are partial.
2600 Sets to a non-subreg of a multiword register are not. */
2601 if (GET_CODE (reg) == SUBREG)
2602 ref_flags |= DF_REF_PARTIAL;
2603 ref_flags |= DF_REF_MW_HARDREG;
2605 hardreg = problem_data->mw_reg_pool->allocate ();
2606 hardreg->type = ref_type;
2607 hardreg->flags = ref_flags;
2608 hardreg->mw_reg = reg;
2609 hardreg->start_regno = regno;
2610 hardreg->end_regno = endregno - 1;
2611 hardreg->mw_order = df->ref_order++;
2612 collection_rec->mw_vec.safe_push (hardreg);
2615 for (i = regno; i < endregno; i++)
2617 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2618 bb, insn_info, ref_type, ref_flags);
2620 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2623 else
2625 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2626 ref_type, ref_flags);
2631 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2632 covered by the outer mode is smaller than that covered by the inner mode,
2633 is a read-modify-write operation.
2634 This function returns true iff the SUBREG X is such a SUBREG. */
2636 bool
2637 df_read_modify_subreg_p (rtx x)
2639 unsigned int isize, osize;
2640 if (GET_CODE (x) != SUBREG)
2641 return false;
2642 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2643 osize = GET_MODE_SIZE (GET_MODE (x));
2644 return isize > osize
2645 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2649 /* Process all the registers defined in the rtx pointed by LOC.
2650 Autoincrement/decrement definitions will be picked up by df_uses_record.
2651 Any change here has to be matched in df_find_hard_reg_defs_1. */
2653 static void
2654 df_def_record_1 (struct df_collection_rec *collection_rec,
2655 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2656 int flags)
2658 rtx dst = *loc;
2660 /* It is legal to have a set destination be a parallel. */
2661 if (GET_CODE (dst) == PARALLEL)
2663 int i;
2664 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2666 rtx temp = XVECEXP (dst, 0, i);
2667 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2668 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2669 bb, insn_info, flags);
2671 return;
2674 if (GET_CODE (dst) == STRICT_LOW_PART)
2676 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2678 loc = &XEXP (dst, 0);
2679 dst = *loc;
2682 if (GET_CODE (dst) == ZERO_EXTRACT)
2684 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2686 loc = &XEXP (dst, 0);
2687 dst = *loc;
2690 /* At this point if we do not have a reg or a subreg, just return. */
2691 if (REG_P (dst))
2693 df_ref_record (DF_REF_REGULAR, collection_rec,
2694 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2696 /* We want to keep sp alive everywhere - by making all
2697 writes to sp also use of sp. */
2698 if (REGNO (dst) == STACK_POINTER_REGNUM)
2699 df_ref_record (DF_REF_BASE, collection_rec,
2700 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2702 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2704 if (df_read_modify_subreg_p (dst))
2705 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2707 flags |= DF_REF_SUBREG;
2709 df_ref_record (DF_REF_REGULAR, collection_rec,
2710 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2715 /* Process all the registers defined in the pattern rtx, X. Any change
2716 here has to be matched in df_find_hard_reg_defs. */
2718 static void
2719 df_defs_record (struct df_collection_rec *collection_rec,
2720 rtx x, basic_block bb, struct df_insn_info *insn_info,
2721 int flags)
2723 RTX_CODE code = GET_CODE (x);
2724 int i;
2726 switch (code)
2728 case SET:
2729 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2730 break;
2732 case CLOBBER:
2733 flags |= DF_REF_MUST_CLOBBER;
2734 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2735 break;
2737 case COND_EXEC:
2738 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2739 bb, insn_info, DF_REF_CONDITIONAL);
2740 break;
2742 case PARALLEL:
2743 for (i = 0; i < XVECLEN (x, 0); i++)
2744 df_defs_record (collection_rec, XVECEXP (x, 0, i),
2745 bb, insn_info, flags);
2746 break;
2747 default:
2748 /* No DEFs to record in other cases */
2749 break;
2753 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2754 destination of a set or clobber. This has to match the logic in
2755 df_defs_record_1. */
2757 static void
2758 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2760 /* It is legal to have a set destination be a parallel. */
2761 if (GET_CODE (dst) == PARALLEL)
2763 int i;
2764 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2766 rtx temp = XVECEXP (dst, 0, i);
2767 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2768 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2770 return;
2773 if (GET_CODE (dst) == STRICT_LOW_PART)
2774 dst = XEXP (dst, 0);
2776 if (GET_CODE (dst) == ZERO_EXTRACT)
2777 dst = XEXP (dst, 0);
2779 /* At this point if we do not have a reg or a subreg, just return. */
2780 if (REG_P (dst) && HARD_REGISTER_P (dst))
2781 SET_HARD_REG_BIT (*defs, REGNO (dst));
2782 else if (GET_CODE (dst) == SUBREG
2783 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2784 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2787 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2788 has to match the logic in df_defs_record. */
2790 static void
2791 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2793 RTX_CODE code = GET_CODE (x);
2794 int i;
2796 switch (code)
2798 case SET:
2799 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2800 break;
2802 case CLOBBER:
2803 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2804 break;
2806 case COND_EXEC:
2807 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2808 break;
2810 case PARALLEL:
2811 for (i = 0; i < XVECLEN (x, 0); i++)
2812 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2813 break;
2814 default:
2815 /* No DEFs to record in other cases */
2816 break;
2821 /* Process all the registers used in the rtx at address LOC. */
2823 static void
2824 df_uses_record (struct df_collection_rec *collection_rec,
2825 rtx *loc, enum df_ref_type ref_type,
2826 basic_block bb, struct df_insn_info *insn_info,
2827 int flags)
2829 RTX_CODE code;
2830 rtx x;
2832 retry:
2833 x = *loc;
2834 if (!x)
2835 return;
2836 code = GET_CODE (x);
2837 switch (code)
2839 case LABEL_REF:
2840 case SYMBOL_REF:
2841 case CONST:
2842 CASE_CONST_ANY:
2843 case PC:
2844 case CC0:
2845 case ADDR_VEC:
2846 case ADDR_DIFF_VEC:
2847 return;
2849 case CLOBBER:
2850 /* If we are clobbering a MEM, mark any registers inside the address
2851 as being used. */
2852 if (MEM_P (XEXP (x, 0)))
2853 df_uses_record (collection_rec,
2854 &XEXP (XEXP (x, 0), 0),
2855 DF_REF_REG_MEM_STORE,
2856 bb, insn_info,
2857 flags);
2859 /* If we're clobbering a REG then we have a def so ignore. */
2860 return;
2862 case MEM:
2863 df_uses_record (collection_rec,
2864 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2865 bb, insn_info, flags & DF_REF_IN_NOTE);
2866 return;
2868 case SUBREG:
2869 /* While we're here, optimize this case. */
2870 flags |= DF_REF_PARTIAL;
2871 /* In case the SUBREG is not of a REG, do not optimize. */
2872 if (!REG_P (SUBREG_REG (x)))
2874 loc = &SUBREG_REG (x);
2875 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2876 return;
2878 /* ... Fall through ... */
2880 case REG:
2881 df_ref_record (DF_REF_REGULAR, collection_rec,
2882 x, loc, bb, insn_info,
2883 ref_type, flags);
2884 return;
2886 case SIGN_EXTRACT:
2887 case ZERO_EXTRACT:
2889 df_uses_record (collection_rec,
2890 &XEXP (x, 1), ref_type, bb, insn_info, flags);
2891 df_uses_record (collection_rec,
2892 &XEXP (x, 2), ref_type, bb, insn_info, flags);
2894 /* If the parameters to the zero or sign extract are
2895 constants, strip them off and recurse, otherwise there is
2896 no information that we can gain from this operation. */
2897 if (code == ZERO_EXTRACT)
2898 flags |= DF_REF_ZERO_EXTRACT;
2899 else
2900 flags |= DF_REF_SIGN_EXTRACT;
2902 df_uses_record (collection_rec,
2903 &XEXP (x, 0), ref_type, bb, insn_info, flags);
2904 return;
2906 break;
2908 case SET:
2910 rtx dst = SET_DEST (x);
2911 gcc_assert (!(flags & DF_REF_IN_NOTE));
2912 df_uses_record (collection_rec,
2913 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2915 switch (GET_CODE (dst))
2917 case SUBREG:
2918 if (df_read_modify_subreg_p (dst))
2920 df_uses_record (collection_rec, &SUBREG_REG (dst),
2921 DF_REF_REG_USE, bb, insn_info,
2922 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2923 break;
2925 /* Fall through. */
2926 case REG:
2927 case PARALLEL:
2928 case SCRATCH:
2929 case PC:
2930 case CC0:
2931 break;
2932 case MEM:
2933 df_uses_record (collection_rec, &XEXP (dst, 0),
2934 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2935 break;
2936 case STRICT_LOW_PART:
2938 rtx *temp = &XEXP (dst, 0);
2939 /* A strict_low_part uses the whole REG and not just the
2940 SUBREG. */
2941 dst = XEXP (dst, 0);
2942 df_uses_record (collection_rec,
2943 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2944 DF_REF_REG_USE, bb, insn_info,
2945 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2947 break;
2948 case ZERO_EXTRACT:
2950 df_uses_record (collection_rec, &XEXP (dst, 1),
2951 DF_REF_REG_USE, bb, insn_info, flags);
2952 df_uses_record (collection_rec, &XEXP (dst, 2),
2953 DF_REF_REG_USE, bb, insn_info, flags);
2954 if (GET_CODE (XEXP (dst,0)) == MEM)
2955 df_uses_record (collection_rec, &XEXP (dst, 0),
2956 DF_REF_REG_USE, bb, insn_info,
2957 flags);
2958 else
2959 df_uses_record (collection_rec, &XEXP (dst, 0),
2960 DF_REF_REG_USE, bb, insn_info,
2961 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2963 break;
2965 default:
2966 gcc_unreachable ();
2968 return;
2971 case RETURN:
2972 case SIMPLE_RETURN:
2973 break;
2975 case ASM_OPERANDS:
2976 case UNSPEC_VOLATILE:
2977 case TRAP_IF:
2978 case ASM_INPUT:
2980 /* Traditional and volatile asm instructions must be
2981 considered to use and clobber all hard registers, all
2982 pseudo-registers and all of memory. So must TRAP_IF and
2983 UNSPEC_VOLATILE operations.
2985 Consider for instance a volatile asm that changes the fpu
2986 rounding mode. An insn should not be moved across this
2987 even if it only uses pseudo-regs because it might give an
2988 incorrectly rounded result.
2990 However, flow.c's liveness computation did *not* do this,
2991 giving the reasoning as " ?!? Unfortunately, marking all
2992 hard registers as live causes massive problems for the
2993 register allocator and marking all pseudos as live creates
2994 mountains of uninitialized variable warnings."
2996 In order to maintain the status quo with regard to liveness
2997 and uses, we do what flow.c did and just mark any regs we
2998 can find in ASM_OPERANDS as used. In global asm insns are
2999 scanned and regs_asm_clobbered is filled out.
3001 For all ASM_OPERANDS, we must traverse the vector of input
3002 operands. We can not just fall through here since then we
3003 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3004 which do not indicate traditional asms unlike their normal
3005 usage. */
3006 if (code == ASM_OPERANDS)
3008 int j;
3010 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3011 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
3012 DF_REF_REG_USE, bb, insn_info, flags);
3013 return;
3015 break;
3018 case VAR_LOCATION:
3019 df_uses_record (collection_rec,
3020 &PAT_VAR_LOCATION_LOC (x),
3021 DF_REF_REG_USE, bb, insn_info, flags);
3022 return;
3024 case PRE_DEC:
3025 case POST_DEC:
3026 case PRE_INC:
3027 case POST_INC:
3028 case PRE_MODIFY:
3029 case POST_MODIFY:
3030 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3031 /* Catch the def of the register being modified. */
3032 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3033 bb, insn_info,
3034 DF_REF_REG_DEF,
3035 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3037 /* ... Fall through to handle uses ... */
3039 default:
3040 break;
3043 /* Recursively scan the operands of this expression. */
3045 const char *fmt = GET_RTX_FORMAT (code);
3046 int i;
3048 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3050 if (fmt[i] == 'e')
3052 /* Tail recursive case: save a function call level. */
3053 if (i == 0)
3055 loc = &XEXP (x, 0);
3056 goto retry;
3058 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3059 bb, insn_info, flags);
3061 else if (fmt[i] == 'E')
3063 int j;
3064 for (j = 0; j < XVECLEN (x, i); j++)
3065 df_uses_record (collection_rec,
3066 &XVECEXP (x, i, j), ref_type,
3067 bb, insn_info, flags);
3072 return;
3076 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3078 static void
3079 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3081 unsigned int ix;
3082 df_ref ref;
3084 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3086 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3088 df_ref use;
3090 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3091 DF_REF_LOC (ref), DF_REF_BB (ref),
3092 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3093 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3094 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3100 /* Get call's extra defs and uses (track caller-saved registers). */
3102 static void
3103 df_get_call_refs (struct df_collection_rec *collection_rec,
3104 basic_block bb,
3105 struct df_insn_info *insn_info,
3106 int flags)
3108 rtx note;
3109 bool is_sibling_call;
3110 unsigned int i;
3111 HARD_REG_SET defs_generated;
3112 HARD_REG_SET fn_reg_set_usage;
3114 CLEAR_HARD_REG_SET (defs_generated);
3115 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3116 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3117 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3118 regs_invalidated_by_call);
3120 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3122 if (i == STACK_POINTER_REGNUM)
3123 /* The stack ptr is used (honorarily) by a CALL insn. */
3124 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3125 NULL, bb, insn_info, DF_REF_REG_USE,
3126 DF_REF_CALL_STACK_USAGE | flags);
3127 else if (global_regs[i])
3129 /* Calls to const functions cannot access any global registers and
3130 calls to pure functions cannot set them. All other calls may
3131 reference any of the global registers, so they are recorded as
3132 used. */
3133 if (!RTL_CONST_CALL_P (insn_info->insn))
3135 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3136 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3137 if (!RTL_PURE_CALL_P (insn_info->insn))
3138 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3139 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3142 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3143 /* no clobbers for regs that are the result of the call */
3144 && !TEST_HARD_REG_BIT (defs_generated, i)
3145 && (!is_sibling_call
3146 || !bitmap_bit_p (df->exit_block_uses, i)
3147 || refers_to_regno_p (i, crtl->return_rtx)))
3148 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3149 NULL, bb, insn_info, DF_REF_REG_DEF,
3150 DF_REF_MAY_CLOBBER | flags);
3153 /* Record the registers used to pass arguments, and explicitly
3154 noted as clobbered. */
3155 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3156 note = XEXP (note, 1))
3158 if (GET_CODE (XEXP (note, 0)) == USE)
3159 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3160 DF_REF_REG_USE, bb, insn_info, flags);
3161 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3163 if (REG_P (XEXP (XEXP (note, 0), 0)))
3165 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3166 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3167 df_defs_record (collection_rec, XEXP (note, 0), bb,
3168 insn_info, flags);
3170 else
3171 df_uses_record (collection_rec, &XEXP (note, 0),
3172 DF_REF_REG_USE, bb, insn_info, flags);
3176 return;
3179 /* Collect all refs in the INSN. This function is free of any
3180 side-effect - it will create and return a lists of df_ref's in the
3181 COLLECTION_REC without putting those refs into existing ref chains
3182 and reg chains. */
3184 static void
3185 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3186 basic_block bb, struct df_insn_info *insn_info)
3188 rtx note;
3189 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3191 /* Clear out the collection record. */
3192 collection_rec->def_vec.truncate (0);
3193 collection_rec->use_vec.truncate (0);
3194 collection_rec->eq_use_vec.truncate (0);
3195 collection_rec->mw_vec.truncate (0);
3197 /* Process REG_EQUIV/REG_EQUAL notes. */
3198 for (note = REG_NOTES (insn_info->insn); note;
3199 note = XEXP (note, 1))
3201 switch (REG_NOTE_KIND (note))
3203 case REG_EQUIV:
3204 case REG_EQUAL:
3205 df_uses_record (collection_rec,
3206 &XEXP (note, 0), DF_REF_REG_USE,
3207 bb, insn_info, DF_REF_IN_NOTE);
3208 break;
3209 case REG_NON_LOCAL_GOTO:
3210 /* The frame ptr is used by a non-local goto. */
3211 df_ref_record (DF_REF_BASE, collection_rec,
3212 regno_reg_rtx[FRAME_POINTER_REGNUM],
3213 NULL, bb, insn_info,
3214 DF_REF_REG_USE, 0);
3215 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3216 df_ref_record (DF_REF_BASE, collection_rec,
3217 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3218 NULL, bb, insn_info,
3219 DF_REF_REG_USE, 0);
3220 break;
3221 default:
3222 break;
3226 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3227 uses from CALL_INSN_FUNCTION_USAGE. */
3228 if (CALL_P (insn_info->insn))
3229 df_get_call_refs (collection_rec, bb, insn_info,
3230 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3232 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3233 that a qsort on the defs is unnecessary in most cases. */
3234 df_defs_record (collection_rec,
3235 PATTERN (insn_info->insn), bb, insn_info, 0);
3237 /* Record the register uses. */
3238 df_uses_record (collection_rec,
3239 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3241 /* DF_REF_CONDITIONAL needs corresponding USES. */
3242 if (is_cond_exec)
3243 df_get_conditional_uses (collection_rec);
3245 df_canonize_collection_rec (collection_rec);
3248 /* Recompute the luids for the insns in BB. */
3250 void
3251 df_recompute_luids (basic_block bb)
3253 rtx_insn *insn;
3254 int luid = 0;
3256 df_grow_insn_info ();
3258 /* Scan the block an insn at a time from beginning to end. */
3259 FOR_BB_INSNS (bb, insn)
3261 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3262 /* Inserting labels does not always trigger the incremental
3263 rescanning. */
3264 if (!insn_info)
3266 gcc_assert (!INSN_P (insn));
3267 insn_info = df_insn_create_insn_record (insn);
3270 DF_INSN_INFO_LUID (insn_info) = luid;
3271 if (INSN_P (insn))
3272 luid++;
3277 /* Collect all artificial refs at the block level for BB and add them
3278 to COLLECTION_REC. */
3280 static void
3281 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3283 collection_rec->def_vec.truncate (0);
3284 collection_rec->use_vec.truncate (0);
3285 collection_rec->eq_use_vec.truncate (0);
3286 collection_rec->mw_vec.truncate (0);
3288 if (bb->index == ENTRY_BLOCK)
3290 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3291 return;
3293 else if (bb->index == EXIT_BLOCK)
3295 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3296 return;
3299 if (bb_has_eh_pred (bb))
3301 unsigned int i;
3302 /* Mark the registers that will contain data for the handler. */
3303 for (i = 0; ; ++i)
3305 unsigned regno = EH_RETURN_DATA_REGNO (i);
3306 if (regno == INVALID_REGNUM)
3307 break;
3308 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3309 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3313 /* Add the hard_frame_pointer if this block is the target of a
3314 non-local goto. */
3315 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3316 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3317 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3319 /* Add the artificial uses. */
3320 if (bb->index >= NUM_FIXED_BLOCKS)
3322 bitmap_iterator bi;
3323 unsigned int regno;
3324 bitmap au = bb_has_eh_pred (bb)
3325 ? &df->eh_block_artificial_uses
3326 : &df->regular_block_artificial_uses;
3328 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3330 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3331 bb, NULL, DF_REF_REG_USE, 0);
3335 df_canonize_collection_rec (collection_rec);
3339 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3341 void
3342 df_bb_refs_record (int bb_index, bool scan_insns)
3344 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3345 rtx_insn *insn;
3346 int luid = 0;
3348 if (!df)
3349 return;
3351 df_collection_rec collection_rec;
3352 df_grow_bb_info (df_scan);
3353 if (scan_insns)
3354 /* Scan the block an insn at a time from beginning to end. */
3355 FOR_BB_INSNS (bb, insn)
3357 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3358 gcc_assert (!insn_info);
3360 insn_info = df_insn_create_insn_record (insn);
3361 if (INSN_P (insn))
3363 /* Record refs within INSN. */
3364 DF_INSN_INFO_LUID (insn_info) = luid++;
3365 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3366 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3368 DF_INSN_INFO_LUID (insn_info) = luid;
3371 /* Other block level artificial refs */
3372 df_bb_refs_collect (&collection_rec, bb);
3373 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3375 /* Now that the block has been processed, set the block as dirty so
3376 LR and LIVE will get it processed. */
3377 df_set_bb_dirty (bb);
3381 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3382 block. */
3384 static void
3385 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3387 #ifdef EH_USES
3388 unsigned int i;
3389 #endif
3391 bitmap_clear (regular_block_artificial_uses);
3393 if (reload_completed)
3395 if (frame_pointer_needed)
3396 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3398 else
3399 /* Before reload, there are a few registers that must be forced
3400 live everywhere -- which might not already be the case for
3401 blocks within infinite loops. */
3403 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3405 /* Any reference to any pseudo before reload is a potential
3406 reference of the frame pointer. */
3407 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3409 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3410 bitmap_set_bit (regular_block_artificial_uses,
3411 HARD_FRAME_POINTER_REGNUM);
3413 /* Pseudos with argument area equivalences may require
3414 reloading via the argument pointer. */
3415 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3416 && fixed_regs[ARG_POINTER_REGNUM])
3417 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3419 /* Any constant, or pseudo with constant equivalences, may
3420 require reloading from memory using the pic register. */
3421 if (picreg != INVALID_REGNUM
3422 && fixed_regs[picreg])
3423 bitmap_set_bit (regular_block_artificial_uses, picreg);
3425 /* The all-important stack pointer must always be live. */
3426 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3428 #ifdef EH_USES
3429 /* EH_USES registers are used:
3430 1) at all insns that might throw (calls or with -fnon-call-exceptions
3431 trapping insns)
3432 2) in all EH edges
3433 3) to support backtraces and/or debugging, anywhere between their
3434 initialization and where they the saved registers are restored
3435 from them, including the cases where we don't reach the epilogue
3436 (noreturn call or infinite loop). */
3437 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3438 if (EH_USES (i))
3439 bitmap_set_bit (regular_block_artificial_uses, i);
3440 #endif
3444 /* Get the artificial use set for an eh block. */
3446 static void
3447 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3449 bitmap_clear (eh_block_artificial_uses);
3451 /* The following code (down through the arg_pointer setting APPEARS
3452 to be necessary because there is nothing that actually
3453 describes what the exception handling code may actually need
3454 to keep alive. */
3455 if (reload_completed)
3457 if (frame_pointer_needed)
3459 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3460 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3461 bitmap_set_bit (eh_block_artificial_uses,
3462 HARD_FRAME_POINTER_REGNUM);
3464 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3465 && fixed_regs[ARG_POINTER_REGNUM])
3466 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3472 /*----------------------------------------------------------------------------
3473 Specialized hard register scanning functions.
3474 ----------------------------------------------------------------------------*/
3477 /* Mark a register in SET. Hard registers in large modes get all
3478 of their component registers set as well. */
3480 static void
3481 df_mark_reg (rtx reg, void *vset)
3483 bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3487 /* Set the bit for regs that are considered being defined at the entry. */
3489 static void
3490 df_get_entry_block_def_set (bitmap entry_block_defs)
3492 rtx r;
3493 int i;
3495 bitmap_clear (entry_block_defs);
3497 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3499 if (global_regs[i])
3500 bitmap_set_bit (entry_block_defs, i);
3501 if (FUNCTION_ARG_REGNO_P (i))
3502 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3505 /* The always important stack pointer. */
3506 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3508 /* Once the prologue has been generated, all of these registers
3509 should just show up in the first regular block. */
3510 if (targetm.have_prologue () && epilogue_completed)
3512 /* Defs for the callee saved registers are inserted so that the
3513 pushes have some defining location. */
3514 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3515 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3516 bitmap_set_bit (entry_block_defs, i);
3519 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3520 if (r && REG_P (r))
3521 bitmap_set_bit (entry_block_defs, REGNO (r));
3523 /* If the function has an incoming STATIC_CHAIN, it has to show up
3524 in the entry def set. */
3525 r = targetm.calls.static_chain (current_function_decl, true);
3526 if (r && REG_P (r))
3527 bitmap_set_bit (entry_block_defs, REGNO (r));
3529 if ((!reload_completed) || frame_pointer_needed)
3531 /* Any reference to any pseudo before reload is a potential
3532 reference of the frame pointer. */
3533 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3535 /* If they are different, also mark the hard frame pointer as live. */
3536 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3537 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3538 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3541 /* These registers are live everywhere. */
3542 if (!reload_completed)
3544 /* Pseudos with argument area equivalences may require
3545 reloading via the argument pointer. */
3546 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3547 && fixed_regs[ARG_POINTER_REGNUM])
3548 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3550 /* Any constant, or pseudo with constant equivalences, may
3551 require reloading from memory using the pic register. */
3552 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3553 if (picreg != INVALID_REGNUM
3554 && fixed_regs[picreg])
3555 bitmap_set_bit (entry_block_defs, picreg);
3558 #ifdef INCOMING_RETURN_ADDR_RTX
3559 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3560 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3561 #endif
3563 targetm.extra_live_on_entry (entry_block_defs);
3567 /* Return the (conservative) set of hard registers that are defined on
3568 entry to the function.
3569 It uses df->entry_block_defs to determine which register
3570 reference to include. */
3572 static void
3573 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3574 bitmap entry_block_defs)
3576 unsigned int i;
3577 bitmap_iterator bi;
3579 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3581 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3582 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3585 df_canonize_collection_rec (collection_rec);
3589 /* Record the (conservative) set of hard registers that are defined on
3590 entry to the function. */
3592 static void
3593 df_record_entry_block_defs (bitmap entry_block_defs)
3595 struct df_collection_rec collection_rec;
3596 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3598 /* Process bb_refs chain */
3599 df_refs_add_to_chains (&collection_rec,
3600 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3601 NULL,
3602 copy_defs);
3606 /* Update the defs in the entry block. */
3608 void
3609 df_update_entry_block_defs (void)
3611 bitmap_head refs;
3612 bool changed = false;
3614 bitmap_initialize (&refs, &df_bitmap_obstack);
3615 df_get_entry_block_def_set (&refs);
3616 if (df->entry_block_defs)
3618 if (!bitmap_equal_p (df->entry_block_defs, &refs))
3620 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3621 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3622 df_ref_chain_delete (bb_info->artificial_defs);
3623 bb_info->artificial_defs = NULL;
3624 changed = true;
3627 else
3629 struct df_scan_problem_data *problem_data
3630 = (struct df_scan_problem_data *) df_scan->problem_data;
3631 gcc_unreachable ();
3632 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3633 changed = true;
3636 if (changed)
3638 df_record_entry_block_defs (&refs);
3639 bitmap_copy (df->entry_block_defs, &refs);
3640 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3642 bitmap_clear (&refs);
3646 /* Set the bit for regs that are considered being used at the exit. */
3648 static void
3649 df_get_exit_block_use_set (bitmap exit_block_uses)
3651 unsigned int i;
3652 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3654 bitmap_clear (exit_block_uses);
3656 /* Stack pointer is always live at the exit. */
3657 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3659 /* Mark the frame pointer if needed at the end of the function.
3660 If we end up eliminating it, it will be removed from the live
3661 list of each basic block by reload. */
3663 if ((!reload_completed) || frame_pointer_needed)
3665 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3667 /* If they are different, also mark the hard frame pointer as live. */
3668 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3669 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3670 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3673 /* Many architectures have a GP register even without flag_pic.
3674 Assume the pic register is not in use, or will be handled by
3675 other means, if it is not fixed. */
3676 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3677 && picreg != INVALID_REGNUM
3678 && fixed_regs[picreg])
3679 bitmap_set_bit (exit_block_uses, picreg);
3681 /* Mark all global registers, and all registers used by the
3682 epilogue as being live at the end of the function since they
3683 may be referenced by our caller. */
3684 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3685 if (global_regs[i] || EPILOGUE_USES (i))
3686 bitmap_set_bit (exit_block_uses, i);
3688 if (targetm.have_epilogue () && epilogue_completed)
3690 /* Mark all call-saved registers that we actually used. */
3691 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3692 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3693 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3694 bitmap_set_bit (exit_block_uses, i);
3697 /* Mark the registers that will contain data for the handler. */
3698 if (reload_completed && crtl->calls_eh_return)
3699 for (i = 0; ; ++i)
3701 unsigned regno = EH_RETURN_DATA_REGNO (i);
3702 if (regno == INVALID_REGNUM)
3703 break;
3704 bitmap_set_bit (exit_block_uses, regno);
3707 #ifdef EH_RETURN_STACKADJ_RTX
3708 if ((!targetm.have_epilogue () || ! epilogue_completed)
3709 && crtl->calls_eh_return)
3711 rtx tmp = EH_RETURN_STACKADJ_RTX;
3712 if (tmp && REG_P (tmp))
3713 df_mark_reg (tmp, exit_block_uses);
3715 #endif
3717 #ifdef EH_RETURN_HANDLER_RTX
3718 if ((!targetm.have_epilogue () || ! epilogue_completed)
3719 && crtl->calls_eh_return)
3721 rtx tmp = EH_RETURN_HANDLER_RTX;
3722 if (tmp && REG_P (tmp))
3723 df_mark_reg (tmp, exit_block_uses);
3725 #endif
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 bitmap_head refs;
3782 bool changed = false;
3784 bitmap_initialize (&refs, &df_bitmap_obstack);
3785 df_get_exit_block_use_set (&refs);
3786 if (df->exit_block_uses)
3788 if (!bitmap_equal_p (df->exit_block_uses, &refs))
3790 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3791 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3792 df_ref_chain_delete (bb_info->artificial_uses);
3793 bb_info->artificial_uses = NULL;
3794 changed = true;
3797 else
3799 struct df_scan_problem_data *problem_data
3800 = (struct df_scan_problem_data *) df_scan->problem_data;
3801 gcc_unreachable ();
3802 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3803 changed = true;
3806 if (changed)
3808 df_record_exit_block_uses (&refs);
3809 bitmap_copy (df->exit_block_uses,& refs);
3810 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3812 bitmap_clear (&refs);
3815 static bool initialized = false;
3818 /* Initialize some platform specific structures. */
3820 void
3821 df_hard_reg_init (void)
3823 #ifdef ELIMINABLE_REGS
3824 int i;
3825 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3826 #endif
3827 if (initialized)
3828 return;
3830 /* Record which registers will be eliminated. We use this in
3831 mark_used_regs. */
3832 CLEAR_HARD_REG_SET (elim_reg_set);
3834 #ifdef ELIMINABLE_REGS
3835 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3836 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3837 #else
3838 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3839 #endif
3841 initialized = true;
3845 /* Recompute the parts of scanning that are based on regs_ever_live
3846 because something changed in that array. */
3848 void
3849 df_update_entry_exit_and_calls (void)
3851 basic_block bb;
3853 df_update_entry_block_defs ();
3854 df_update_exit_block_uses ();
3856 /* The call insns need to be rescanned because there may be changes
3857 in the set of registers clobbered across the call. */
3858 FOR_EACH_BB_FN (bb, cfun)
3860 rtx_insn *insn;
3861 FOR_BB_INSNS (bb, insn)
3863 if (INSN_P (insn) && CALL_P (insn))
3864 df_insn_rescan (insn);
3870 /* Return true if hard REG is actually used in the some instruction.
3871 There are a fair number of conditions that affect the setting of
3872 this array. See the comment in df.h for df->hard_regs_live_count
3873 for the conditions that this array is set. */
3875 bool
3876 df_hard_reg_used_p (unsigned int reg)
3878 return df->hard_regs_live_count[reg] != 0;
3882 /* A count of the number of times REG is actually used in the some
3883 instruction. There are a fair number of conditions that affect the
3884 setting of this array. See the comment in df.h for
3885 df->hard_regs_live_count for the conditions that this array is
3886 set. */
3889 unsigned int
3890 df_hard_reg_used_count (unsigned int reg)
3892 return df->hard_regs_live_count[reg];
3896 /* Get the value of regs_ever_live[REGNO]. */
3898 bool
3899 df_regs_ever_live_p (unsigned int regno)
3901 return regs_ever_live[regno];
3905 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3906 to change, schedule that change for the next update. */
3908 void
3909 df_set_regs_ever_live (unsigned int regno, bool value)
3911 if (regs_ever_live[regno] == value)
3912 return;
3914 regs_ever_live[regno] = value;
3915 if (df)
3916 df->redo_entry_and_exit = true;
3920 /* Compute "regs_ever_live" information from the underlying df
3921 information. Set the vector to all false if RESET. */
3923 void
3924 df_compute_regs_ever_live (bool reset)
3926 unsigned int i;
3927 bool changed = df->redo_entry_and_exit;
3929 if (reset)
3930 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3932 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3933 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3935 regs_ever_live[i] = true;
3936 changed = true;
3938 if (changed)
3939 df_update_entry_exit_and_calls ();
3940 df->redo_entry_and_exit = false;
3944 /*----------------------------------------------------------------------------
3945 Dataflow ref information verification functions.
3947 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3948 df_reg_chain_verify_unmarked (refs)
3949 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3950 df_mws_verify (mw*, mw*, bool)
3951 df_insn_refs_verify (collection_rec, bb, insn, bool)
3952 df_bb_refs_verify (bb, refs, bool)
3953 df_bb_verify (bb)
3954 df_exit_block_bitmap_verify (bool)
3955 df_entry_block_bitmap_verify (bool)
3956 df_scan_verify ()
3957 ----------------------------------------------------------------------------*/
3960 /* Mark all refs in the reg chain. Verify that all of the registers
3961 are in the correct chain. */
3963 static unsigned int
3964 df_reg_chain_mark (df_ref refs, unsigned int regno,
3965 bool is_def, bool is_eq_use)
3967 unsigned int count = 0;
3968 df_ref ref;
3969 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3971 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3973 /* If there are no def-use or use-def chains, make sure that all
3974 of the chains are clear. */
3975 if (!df_chain)
3976 gcc_assert (!DF_REF_CHAIN (ref));
3978 /* Check to make sure the ref is in the correct chain. */
3979 gcc_assert (DF_REF_REGNO (ref) == regno);
3980 if (is_def)
3981 gcc_assert (DF_REF_REG_DEF_P (ref));
3982 else
3983 gcc_assert (!DF_REF_REG_DEF_P (ref));
3985 if (is_eq_use)
3986 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
3987 else
3988 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
3990 if (DF_REF_NEXT_REG (ref))
3991 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
3992 count++;
3993 DF_REF_REG_MARK (ref);
3995 return count;
3999 /* Verify that all of the registers in the chain are unmarked. */
4001 static void
4002 df_reg_chain_verify_unmarked (df_ref refs)
4004 df_ref ref;
4005 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4006 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4010 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4012 static bool
4013 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4014 bool abort_if_fail)
4016 unsigned int ix;
4017 df_ref new_ref;
4019 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4021 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4023 if (abort_if_fail)
4024 gcc_assert (0);
4025 else
4026 return false;
4029 /* Abort if fail is called from the function level verifier. If
4030 that is the context, mark this reg as being seem. */
4031 if (abort_if_fail)
4033 gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4034 DF_REF_REG_UNMARK (old_rec);
4037 old_rec = DF_REF_NEXT_LOC (old_rec);
4040 if (abort_if_fail)
4041 gcc_assert (old_rec == NULL);
4042 else
4043 return old_rec == NULL;
4044 return false;
4048 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4050 static bool
4051 df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec,
4052 struct df_mw_hardreg *old_rec,
4053 bool abort_if_fail)
4055 unsigned int ix;
4056 struct df_mw_hardreg *new_reg;
4058 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4060 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4062 if (abort_if_fail)
4063 gcc_assert (0);
4064 else
4065 return false;
4067 old_rec = DF_MWS_NEXT (old_rec);
4070 if (abort_if_fail)
4071 gcc_assert (old_rec == NULL);
4072 else
4073 return old_rec == NULL;
4074 return false;
4078 /* Return true if the existing insn refs information is complete and
4079 correct. Otherwise (i.e. if there's any missing or extra refs),
4080 return the correct df_ref chain in REFS_RETURN.
4082 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4083 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4084 verification mode instead of the whole function, so unmark
4085 everything.
4087 If ABORT_IF_FAIL is set, this function never returns false. */
4089 static bool
4090 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4091 basic_block bb,
4092 rtx_insn *insn,
4093 bool abort_if_fail)
4095 bool ret1, ret2, ret3, ret4;
4096 unsigned int uid = INSN_UID (insn);
4097 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4099 df_insn_refs_collect (collection_rec, bb, insn_info);
4101 /* Unfortunately we cannot opt out early if one of these is not
4102 right because the marks will not get cleared. */
4103 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4104 abort_if_fail);
4105 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4106 abort_if_fail);
4107 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4108 abort_if_fail);
4109 ret4 = df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4110 abort_if_fail);
4111 return (ret1 && ret2 && ret3 && ret4);
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 bitmap_head entry_block_defs;
4154 bool is_eq;
4156 bitmap_initialize (&entry_block_defs, &df_bitmap_obstack);
4157 df_get_entry_block_def_set (&entry_block_defs);
4159 is_eq = bitmap_equal_p (&entry_block_defs, df->entry_block_defs);
4161 if (!is_eq && abort_if_fail)
4163 fprintf (stderr, "entry_block_defs = ");
4164 df_print_regset (stderr, &entry_block_defs);
4165 fprintf (stderr, "df->entry_block_defs = ");
4166 df_print_regset (stderr, df->entry_block_defs);
4167 gcc_assert (0);
4170 bitmap_clear (&entry_block_defs);
4172 return is_eq;
4176 /* Returns true if the exit block has correct and complete df_ref set.
4177 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4179 static bool
4180 df_exit_block_bitmap_verify (bool abort_if_fail)
4182 bitmap_head exit_block_uses;
4183 bool is_eq;
4185 bitmap_initialize (&exit_block_uses, &df_bitmap_obstack);
4186 df_get_exit_block_use_set (&exit_block_uses);
4188 is_eq = bitmap_equal_p (&exit_block_uses, df->exit_block_uses);
4190 if (!is_eq && abort_if_fail)
4192 fprintf (stderr, "exit_block_uses = ");
4193 df_print_regset (stderr, &exit_block_uses);
4194 fprintf (stderr, "df->exit_block_uses = ");
4195 df_print_regset (stderr, df->exit_block_uses);
4196 gcc_assert (0);
4199 bitmap_clear (&exit_block_uses);
4201 return is_eq;
4205 /* Return true if df_ref information for all insns in all blocks are
4206 correct and complete. */
4208 void
4209 df_scan_verify (void)
4211 unsigned int i;
4212 basic_block bb;
4213 bitmap_head regular_block_artificial_uses;
4214 bitmap_head eh_block_artificial_uses;
4216 if (!df)
4217 return;
4219 /* Verification is a 4 step process. */
4221 /* (1) All of the refs are marked by going through the reg chains. */
4222 for (i = 0; i < DF_REG_SIZE (df); i++)
4224 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4225 == DF_REG_DEF_COUNT (i));
4226 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4227 == DF_REG_USE_COUNT (i));
4228 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4229 == DF_REG_EQ_USE_COUNT (i));
4232 /* (2) There are various bitmaps whose value may change over the
4233 course of the compilation. This step recomputes them to make
4234 sure that they have not slipped out of date. */
4235 bitmap_initialize (&regular_block_artificial_uses, &df_bitmap_obstack);
4236 bitmap_initialize (&eh_block_artificial_uses, &df_bitmap_obstack);
4238 df_get_regular_block_artificial_uses (&regular_block_artificial_uses);
4239 df_get_eh_block_artificial_uses (&eh_block_artificial_uses);
4241 bitmap_ior_into (&eh_block_artificial_uses,
4242 &regular_block_artificial_uses);
4244 /* Check artificial_uses bitmaps didn't change. */
4245 gcc_assert (bitmap_equal_p (&regular_block_artificial_uses,
4246 &df->regular_block_artificial_uses));
4247 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses,
4248 &df->eh_block_artificial_uses));
4250 bitmap_clear (&regular_block_artificial_uses);
4251 bitmap_clear (&eh_block_artificial_uses);
4253 /* Verify entry block and exit block. These only verify the bitmaps,
4254 the refs are verified in df_bb_verify. */
4255 df_entry_block_bitmap_verify (true);
4256 df_exit_block_bitmap_verify (true);
4258 /* (3) All of the insns in all of the blocks are traversed and the
4259 marks are cleared both in the artificial refs attached to the
4260 blocks and the real refs inside the insns. It is a failure to
4261 clear a mark that has not been set as this means that the ref in
4262 the block or insn was not in the reg chain. */
4264 FOR_ALL_BB_FN (bb, cfun)
4265 df_bb_verify (bb);
4267 /* (4) See if all reg chains are traversed a second time. This time
4268 a check is made that the marks are clear. A set mark would be a
4269 from a reg that is not in any insn or basic block. */
4271 for (i = 0; i < DF_REG_SIZE (df); i++)
4273 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4274 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4275 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));