gcc/
[official-gcc.git] / gcc / df-scan.c
blob22942407f260b1e097afac1177386921c0215954
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 "tm.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "insn-config.h"
31 #include "recog.h"
32 #include "alias.h"
33 #include "symtab.h"
34 #include "hard-reg-set.h"
35 #include "function.h"
36 #include "regs.h"
37 #include "alloc-pool.h"
38 #include "flags.h"
39 #include "predict.h"
40 #include "dominance.h"
41 #include "cfg.h"
42 #include "basic-block.h"
43 #include "sbitmap.h"
44 #include "bitmap.h"
45 #include "dumpfile.h"
46 #include "tree.h"
47 #include "target.h"
48 #include "df.h"
49 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
52 typedef struct df_mw_hardreg *df_mw_hardreg_ptr;
55 /* The set of hard registers in eliminables[i].from. */
57 static HARD_REG_SET elim_reg_set;
59 /* Initialize ur_in and ur_out as if all hard registers were partially
60 available. */
62 struct df_collection_rec
64 auto_vec<df_ref, 128> def_vec;
65 auto_vec<df_ref, 32> use_vec;
66 auto_vec<df_ref, 32> eq_use_vec;
67 auto_vec<df_mw_hardreg_ptr, 32> mw_vec;
70 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
71 rtx, rtx *,
72 basic_block, struct df_insn_info *,
73 enum df_ref_type, int ref_flags);
74 static void df_def_record_1 (struct df_collection_rec *, rtx *,
75 basic_block, struct df_insn_info *,
76 int ref_flags);
77 static void df_defs_record (struct df_collection_rec *, rtx,
78 basic_block, struct df_insn_info *,
79 int ref_flags);
80 static void df_uses_record (struct df_collection_rec *,
81 rtx *, enum df_ref_type,
82 basic_block, struct df_insn_info *,
83 int ref_flags);
85 static void df_install_ref_incremental (df_ref);
86 static void df_insn_refs_collect (struct df_collection_rec*,
87 basic_block, struct df_insn_info *);
88 static void df_canonize_collection_rec (struct df_collection_rec *);
90 static void df_get_regular_block_artificial_uses (bitmap);
91 static void df_get_eh_block_artificial_uses (bitmap);
93 static void df_record_entry_block_defs (bitmap);
94 static void df_record_exit_block_uses (bitmap);
95 static void df_get_exit_block_use_set (bitmap);
96 static void df_get_entry_block_def_set (bitmap);
97 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
98 static void df_ref_chain_delete_du_chain (df_ref);
99 static void df_ref_chain_delete (df_ref);
101 static void df_refs_add_to_chains (struct df_collection_rec *,
102 basic_block, rtx_insn *, unsigned int);
104 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block,
105 rtx_insn *, bool);
106 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
107 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
108 static void df_install_ref (df_ref, struct df_reg_info *,
109 struct df_ref_info *, bool);
111 static int df_ref_compare (df_ref, df_ref);
112 static int df_ref_ptr_compare (const void *, const void *);
113 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
114 static int df_mw_ptr_compare (const void *, const void *);
116 static void df_insn_info_delete (unsigned int);
118 /* Indexed by hardware reg number, is true if that register is ever
119 used in the current function.
121 In df-scan.c, this is set up to record the hard regs used
122 explicitly. Reload adds in the hard regs used for holding pseudo
123 regs. Final uses it to generate the code in the function prologue
124 and epilogue to save and restore registers as needed. */
126 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
128 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
129 static const unsigned int copy_defs = 0x1;
130 static const unsigned int copy_uses = 0x2;
131 static const unsigned int copy_eq_uses = 0x4;
132 static const unsigned int copy_mw = 0x8;
133 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
134 | copy_mw;
136 /*----------------------------------------------------------------------------
137 SCANNING DATAFLOW PROBLEM
139 There are several ways in which scanning looks just like the other
140 dataflow problems. It shares the all the mechanisms for local info
141 as well as basic block info. Where it differs is when and how often
142 it gets run. It also has no need for the iterative solver.
143 ----------------------------------------------------------------------------*/
145 #define SCAN_PROBLEM_DATA_BLOCK_SIZE 512
147 /* Problem data for the scanning dataflow function. */
148 struct df_scan_problem_data
150 pool_allocator<df_base_ref> *ref_base_pool;
151 pool_allocator<df_artificial_ref> *ref_artificial_pool;
152 pool_allocator<df_regular_ref> *ref_regular_pool;
153 pool_allocator<df_insn_info> *insn_pool;
154 pool_allocator<df_reg_info> *reg_pool;
155 pool_allocator<df_mw_hardreg> *mw_reg_pool;
157 bitmap_obstack reg_bitmaps;
158 bitmap_obstack insn_bitmaps;
161 typedef struct df_scan_bb_info *df_scan_bb_info_t;
164 /* Internal function to shut down the scanning problem. */
165 static void
166 df_scan_free_internal (void)
168 struct df_scan_problem_data *problem_data
169 = (struct df_scan_problem_data *) df_scan->problem_data;
171 free (df->def_info.refs);
172 free (df->def_info.begin);
173 free (df->def_info.count);
174 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
176 free (df->use_info.refs);
177 free (df->use_info.begin);
178 free (df->use_info.count);
179 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
181 free (df->def_regs);
182 df->def_regs = NULL;
183 free (df->use_regs);
184 df->use_regs = NULL;
185 free (df->eq_use_regs);
186 df->eq_use_regs = NULL;
187 df->regs_size = 0;
188 DF_REG_SIZE (df) = 0;
190 free (df->insns);
191 df->insns = NULL;
192 DF_INSN_SIZE () = 0;
194 free (df_scan->block_info);
195 df_scan->block_info = NULL;
196 df_scan->block_info_size = 0;
198 bitmap_clear (&df->hardware_regs_used);
199 bitmap_clear (&df->regular_block_artificial_uses);
200 bitmap_clear (&df->eh_block_artificial_uses);
201 BITMAP_FREE (df->entry_block_defs);
202 BITMAP_FREE (df->exit_block_uses);
203 bitmap_clear (&df->insns_to_delete);
204 bitmap_clear (&df->insns_to_rescan);
205 bitmap_clear (&df->insns_to_notes_rescan);
207 delete problem_data->ref_base_pool;
208 delete problem_data->ref_artificial_pool;
209 delete problem_data->ref_regular_pool;
210 delete problem_data->insn_pool;
211 delete problem_data->reg_pool;
212 delete problem_data->mw_reg_pool;
213 bitmap_obstack_release (&problem_data->reg_bitmaps);
214 bitmap_obstack_release (&problem_data->insn_bitmaps);
215 free (df_scan->problem_data);
219 /* Free basic block info. */
221 static void
222 df_scan_free_bb_info (basic_block bb, void *vbb_info)
224 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
225 unsigned int bb_index = bb->index;
226 rtx_insn *insn;
228 FOR_BB_INSNS (bb, insn)
229 if (INSN_P (insn))
230 df_insn_info_delete (INSN_UID (insn));
232 if (bb_index < df_scan->block_info_size)
233 bb_info = df_scan_get_bb_info (bb_index);
235 /* Get rid of any artificial uses or defs. */
236 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
237 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
238 df_ref_chain_delete (bb_info->artificial_defs);
239 df_ref_chain_delete (bb_info->artificial_uses);
240 bb_info->artificial_defs = NULL;
241 bb_info->artificial_uses = NULL;
245 /* Allocate the problem data for the scanning problem. This should be
246 called when the problem is created or when the entire function is to
247 be rescanned. */
248 void
249 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
251 struct df_scan_problem_data *problem_data;
252 unsigned int insn_num = get_max_uid () + 1;
253 basic_block bb;
255 /* Given the number of pools, this is really faster than tearing
256 everything apart. */
257 if (df_scan->problem_data)
258 df_scan_free_internal ();
260 problem_data = XNEW (struct df_scan_problem_data);
261 df_scan->problem_data = problem_data;
262 df_scan->computed = true;
264 problem_data->ref_base_pool = new pool_allocator<df_base_ref>
265 ("df_scan ref base", SCAN_PROBLEM_DATA_BLOCK_SIZE);
266 problem_data->ref_artificial_pool = new pool_allocator<df_artificial_ref>
267 ("df_scan ref artificial", SCAN_PROBLEM_DATA_BLOCK_SIZE);
268 problem_data->ref_regular_pool = new pool_allocator<df_regular_ref>
269 ("df_scan ref regular", SCAN_PROBLEM_DATA_BLOCK_SIZE);
270 problem_data->insn_pool = new pool_allocator<df_insn_info>
271 ("df_scan insn", SCAN_PROBLEM_DATA_BLOCK_SIZE);
272 problem_data->reg_pool = new pool_allocator<df_reg_info>
273 ("df_scan reg", SCAN_PROBLEM_DATA_BLOCK_SIZE);
274 problem_data->mw_reg_pool = new pool_allocator<df_mw_hardreg>
275 ("df_scan mw_reg", SCAN_PROBLEM_DATA_BLOCK_SIZE / 16);
277 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
278 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
280 insn_num += insn_num / 4;
281 df_grow_reg_info ();
283 df_grow_insn_info ();
284 df_grow_bb_info (df_scan);
286 FOR_ALL_BB_FN (bb, cfun)
288 unsigned int bb_index = bb->index;
289 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
290 bb_info->artificial_defs = NULL;
291 bb_info->artificial_uses = NULL;
294 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
295 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
296 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
297 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
298 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
299 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
300 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
301 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
302 df_scan->optional_p = false;
306 /* Free all of the data associated with the scan problem. */
308 static void
309 df_scan_free (void)
311 if (df_scan->problem_data)
312 df_scan_free_internal ();
314 if (df->blocks_to_analyze)
316 BITMAP_FREE (df->blocks_to_analyze);
317 df->blocks_to_analyze = NULL;
320 free (df_scan);
323 /* Dump the preamble for DF_SCAN dump. */
324 static void
325 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
327 int i;
328 int dcount = 0;
329 int ucount = 0;
330 int ecount = 0;
331 int icount = 0;
332 int ccount = 0;
333 basic_block bb;
334 rtx_insn *insn;
336 fprintf (file, ";; invalidated by call \t");
337 df_print_regset (file, regs_invalidated_by_call_regset);
338 fprintf (file, ";; hardware regs used \t");
339 df_print_regset (file, &df->hardware_regs_used);
340 fprintf (file, ";; regular block artificial uses \t");
341 df_print_regset (file, &df->regular_block_artificial_uses);
342 fprintf (file, ";; eh block artificial uses \t");
343 df_print_regset (file, &df->eh_block_artificial_uses);
344 fprintf (file, ";; entry block defs \t");
345 df_print_regset (file, df->entry_block_defs);
346 fprintf (file, ";; exit block uses \t");
347 df_print_regset (file, df->exit_block_uses);
348 fprintf (file, ";; regs ever live \t");
349 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
350 if (df_regs_ever_live_p (i))
351 fprintf (file, " %d [%s]", i, reg_names[i]);
352 fprintf (file, "\n;; ref usage \t");
354 for (i = 0; i < (int)df->regs_inited; i++)
355 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
357 const char * sep = "";
359 fprintf (file, "r%d={", i);
360 if (DF_REG_DEF_COUNT (i))
362 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
363 sep = ",";
364 dcount += DF_REG_DEF_COUNT (i);
366 if (DF_REG_USE_COUNT (i))
368 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
369 sep = ",";
370 ucount += DF_REG_USE_COUNT (i);
372 if (DF_REG_EQ_USE_COUNT (i))
374 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
375 ecount += DF_REG_EQ_USE_COUNT (i);
377 fprintf (file, "} ");
380 FOR_EACH_BB_FN (bb, cfun)
381 FOR_BB_INSNS (bb, insn)
382 if (INSN_P (insn))
384 if (CALL_P (insn))
385 ccount++;
386 else
387 icount++;
390 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
391 " in %d{%d regular + %d call} insns.\n",
392 dcount + ucount + ecount, dcount, ucount, ecount,
393 icount + ccount, icount, ccount);
396 /* Dump the bb_info for a given basic block. */
397 static void
398 df_scan_start_block (basic_block bb, FILE *file)
400 struct df_scan_bb_info *bb_info
401 = df_scan_get_bb_info (bb->index);
403 if (bb_info)
405 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
406 df_refs_chain_dump (bb_info->artificial_defs, true, file);
407 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
408 df_refs_chain_dump (bb_info->artificial_uses, true, file);
409 fprintf (file, "\n");
411 #if 0
413 rtx_insn *insn;
414 FOR_BB_INSNS (bb, insn)
415 if (INSN_P (insn))
416 df_insn_debug (insn, false, file);
418 #endif
421 static struct df_problem problem_SCAN =
423 DF_SCAN, /* Problem id. */
424 DF_NONE, /* Direction. */
425 df_scan_alloc, /* Allocate the problem specific data. */
426 NULL, /* Reset global information. */
427 df_scan_free_bb_info, /* Free basic block info. */
428 NULL, /* Local compute function. */
429 NULL, /* Init the solution specific data. */
430 NULL, /* Iterative solver. */
431 NULL, /* Confluence operator 0. */
432 NULL, /* Confluence operator n. */
433 NULL, /* Transfer function. */
434 NULL, /* Finalize function. */
435 df_scan_free, /* Free all of the problem information. */
436 NULL, /* Remove this problem from the stack of dataflow problems. */
437 df_scan_start_dump, /* Debugging. */
438 df_scan_start_block, /* Debugging start block. */
439 NULL, /* Debugging end block. */
440 NULL, /* Debugging start insn. */
441 NULL, /* Debugging end insn. */
442 NULL, /* Incremental solution verify start. */
443 NULL, /* Incremental solution verify end. */
444 NULL, /* Dependent problem. */
445 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
446 TV_DF_SCAN, /* Timing variable. */
447 false /* Reset blocks on dropping out of blocks_to_analyze. */
451 /* Create a new DATAFLOW instance and add it to an existing instance
452 of DF. The returned structure is what is used to get at the
453 solution. */
455 void
456 df_scan_add_problem (void)
458 df_add_problem (&problem_SCAN);
462 /*----------------------------------------------------------------------------
463 Storage Allocation Utilities
464 ----------------------------------------------------------------------------*/
467 /* First, grow the reg_info information. If the current size is less than
468 the number of pseudos, grow to 25% more than the number of
469 pseudos.
471 Second, assure that all of the slots up to max_reg_num have been
472 filled with reg_info structures. */
474 void
475 df_grow_reg_info (void)
477 unsigned int max_reg = max_reg_num ();
478 unsigned int new_size = max_reg;
479 struct df_scan_problem_data *problem_data
480 = (struct df_scan_problem_data *) df_scan->problem_data;
481 unsigned int i;
483 if (df->regs_size < new_size)
485 new_size += new_size / 4;
486 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
487 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
488 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
489 new_size);
490 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
491 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
492 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
493 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
494 df->regs_size = new_size;
497 for (i = df->regs_inited; i < max_reg; i++)
499 struct df_reg_info *reg_info;
501 // TODO
502 reg_info = problem_data->reg_pool->allocate ();
503 memset (reg_info, 0, sizeof (struct df_reg_info));
504 df->def_regs[i] = reg_info;
505 reg_info = problem_data->reg_pool->allocate ();
506 memset (reg_info, 0, sizeof (struct df_reg_info));
507 df->use_regs[i] = reg_info;
508 reg_info = problem_data->reg_pool->allocate ();
509 memset (reg_info, 0, sizeof (struct df_reg_info));
510 df->eq_use_regs[i] = reg_info;
511 df->def_info.begin[i] = 0;
512 df->def_info.count[i] = 0;
513 df->use_info.begin[i] = 0;
514 df->use_info.count[i] = 0;
517 df->regs_inited = max_reg;
521 /* Grow the ref information. */
523 static void
524 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
526 if (ref_info->refs_size < new_size)
528 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
529 memset (ref_info->refs + ref_info->refs_size, 0,
530 (new_size - ref_info->refs_size) *sizeof (df_ref));
531 ref_info->refs_size = new_size;
536 /* Check and grow the ref information if necessary. This routine
537 guarantees total_size + BITMAP_ADDEND amount of entries in refs
538 array. It updates ref_info->refs_size only and does not change
539 ref_info->total_size. */
541 static void
542 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
543 unsigned bitmap_addend)
545 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
547 int new_size = ref_info->total_size + bitmap_addend;
548 new_size += ref_info->total_size / 4;
549 df_grow_ref_info (ref_info, new_size);
554 /* Grow the ref information. If the current size is less than the
555 number of instructions, grow to 25% more than the number of
556 instructions. */
558 void
559 df_grow_insn_info (void)
561 unsigned int new_size = get_max_uid () + 1;
562 if (DF_INSN_SIZE () < new_size)
564 new_size += new_size / 4;
565 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
566 memset (df->insns + df->insns_size, 0,
567 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
568 DF_INSN_SIZE () = new_size;
575 /*----------------------------------------------------------------------------
576 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
577 ----------------------------------------------------------------------------*/
579 /* Rescan all of the block_to_analyze or all of the blocks in the
580 function if df_set_blocks if blocks_to_analyze is NULL; */
582 void
583 df_scan_blocks (void)
585 basic_block bb;
587 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
588 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
590 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
591 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
593 bitmap_ior_into (&df->eh_block_artificial_uses,
594 &df->regular_block_artificial_uses);
596 /* ENTRY and EXIT blocks have special defs/uses. */
597 df_get_entry_block_def_set (df->entry_block_defs);
598 df_record_entry_block_defs (df->entry_block_defs);
599 df_get_exit_block_use_set (df->exit_block_uses);
600 df_record_exit_block_uses (df->exit_block_uses);
601 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
602 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
604 /* Regular blocks */
605 FOR_EACH_BB_FN (bb, cfun)
607 unsigned int bb_index = bb->index;
608 df_bb_refs_record (bb_index, true);
612 /* Create new refs under address LOC within INSN. This function is
613 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
614 depending on whether LOC is inside PATTERN (INSN) or a note. */
616 void
617 df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
619 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
620 df_uses_record (NULL, loc, DF_REF_REG_USE,
621 BLOCK_FOR_INSN (insn),
622 DF_INSN_INFO_GET (insn),
623 ref_flags);
626 static void
627 df_install_ref_incremental (df_ref ref)
629 struct df_reg_info **reg_info;
630 struct df_ref_info *ref_info;
631 df_ref *ref_ptr;
632 bool add_to_table;
634 rtx_insn *insn = DF_REF_INSN (ref);
635 basic_block bb = BLOCK_FOR_INSN (insn);
637 if (DF_REF_REG_DEF_P (ref))
639 reg_info = df->def_regs;
640 ref_info = &df->def_info;
641 ref_ptr = &DF_INSN_DEFS (insn);
642 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
644 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
646 reg_info = df->eq_use_regs;
647 ref_info = &df->use_info;
648 ref_ptr = &DF_INSN_EQ_USES (insn);
649 switch (ref_info->ref_order)
651 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
652 case DF_REF_ORDER_BY_REG_WITH_NOTES:
653 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
654 add_to_table = true;
655 break;
656 default:
657 add_to_table = false;
658 break;
661 else
663 reg_info = df->use_regs;
664 ref_info = &df->use_info;
665 ref_ptr = &DF_INSN_USES (insn);
666 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
669 /* Do not add if ref is not in the right blocks. */
670 if (add_to_table && df->analyze_subset)
671 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
673 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
675 if (add_to_table)
676 switch (ref_info->ref_order)
678 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
679 case DF_REF_ORDER_BY_REG_WITH_NOTES:
680 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
681 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
682 break;
683 default:
684 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
685 break;
688 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
689 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
691 DF_REF_NEXT_LOC (ref) = *ref_ptr;
692 *ref_ptr = ref;
694 #if 0
695 if (dump_file)
697 fprintf (dump_file, "adding ref ");
698 df_ref_debug (ref, dump_file);
700 #endif
701 /* By adding the ref directly, df_insn_rescan my not find any
702 differences even though the block will have changed. So we need
703 to mark the block dirty ourselves. */
704 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
705 df_set_bb_dirty (bb);
710 /*----------------------------------------------------------------------------
711 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
712 ----------------------------------------------------------------------------*/
714 static void
715 df_free_ref (df_ref ref)
717 struct df_scan_problem_data *problem_data
718 = (struct df_scan_problem_data *) df_scan->problem_data;
720 switch (DF_REF_CLASS (ref))
722 case DF_REF_BASE:
723 problem_data->ref_base_pool->remove ((df_base_ref *) (ref));
724 break;
726 case DF_REF_ARTIFICIAL:
727 problem_data->ref_artificial_pool->remove
728 ((df_artificial_ref *) (ref));
729 break;
731 case DF_REF_REGULAR:
732 problem_data->ref_regular_pool->remove
733 ((df_regular_ref *) (ref));
734 break;
739 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
740 Also delete the def-use or use-def chain if it exists. */
742 static void
743 df_reg_chain_unlink (df_ref ref)
745 df_ref next = DF_REF_NEXT_REG (ref);
746 df_ref prev = DF_REF_PREV_REG (ref);
747 int id = DF_REF_ID (ref);
748 struct df_reg_info *reg_info;
749 df_ref *refs = NULL;
751 if (DF_REF_REG_DEF_P (ref))
753 int regno = DF_REF_REGNO (ref);
754 reg_info = DF_REG_DEF_GET (regno);
755 refs = df->def_info.refs;
757 else
759 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
761 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
762 switch (df->use_info.ref_order)
764 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
765 case DF_REF_ORDER_BY_REG_WITH_NOTES:
766 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
767 refs = df->use_info.refs;
768 break;
769 default:
770 break;
773 else
775 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
776 refs = df->use_info.refs;
780 if (refs)
782 if (df->analyze_subset)
784 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
785 refs[id] = NULL;
787 else
788 refs[id] = NULL;
791 /* Delete any def-use or use-def chains that start here. It is
792 possible that there is trash in this field. This happens for
793 insns that have been deleted when rescanning has been deferred
794 and the chain problem has also been deleted. The chain tear down
795 code skips deleted insns. */
796 if (df_chain && DF_REF_CHAIN (ref))
797 df_chain_unlink (ref);
799 reg_info->n_refs--;
800 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
802 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
803 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
806 /* Unlink from the reg chain. If there is no prev, this is the
807 first of the list. If not, just join the next and prev. */
808 if (prev)
809 DF_REF_NEXT_REG (prev) = next;
810 else
812 gcc_assert (reg_info->reg_chain == ref);
813 reg_info->reg_chain = next;
815 if (next)
816 DF_REF_PREV_REG (next) = prev;
818 df_free_ref (ref);
822 /* Create the insn record for INSN. If there was one there, zero it
823 out. */
825 struct df_insn_info *
826 df_insn_create_insn_record (rtx_insn *insn)
828 struct df_scan_problem_data *problem_data
829 = (struct df_scan_problem_data *) df_scan->problem_data;
830 struct df_insn_info *insn_rec;
832 df_grow_insn_info ();
833 insn_rec = DF_INSN_INFO_GET (insn);
834 if (!insn_rec)
836 insn_rec = problem_data->insn_pool->allocate ();
837 DF_INSN_INFO_SET (insn, insn_rec);
839 memset (insn_rec, 0, sizeof (struct df_insn_info));
840 insn_rec->insn = insn;
841 return insn_rec;
845 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
847 static void
848 df_ref_chain_delete_du_chain (df_ref ref)
850 for (; ref; ref = DF_REF_NEXT_LOC (ref))
851 /* CHAIN is allocated by DF_CHAIN. So make sure to
852 pass df_scan instance for the problem. */
853 if (DF_REF_CHAIN (ref))
854 df_chain_unlink (ref);
858 /* Delete all refs in the ref chain. */
860 static void
861 df_ref_chain_delete (df_ref ref)
863 df_ref next;
864 for (; ref; ref = next)
866 next = DF_REF_NEXT_LOC (ref);
867 df_reg_chain_unlink (ref);
872 /* Delete the hardreg chain. */
874 static void
875 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
877 struct df_scan_problem_data *problem_data
878 = (struct df_scan_problem_data *) df_scan->problem_data;
879 df_mw_hardreg *next;
881 for (; hardregs; hardregs = next)
883 next = DF_MWS_NEXT (hardregs);
884 problem_data->mw_reg_pool->remove (hardregs);
889 /* Delete all of the refs information from the insn with UID.
890 Internal helper for df_insn_delete, df_insn_rescan, and other
891 df-scan routines that don't have to work in deferred mode
892 and do not have to mark basic blocks for re-processing. */
894 static void
895 df_insn_info_delete (unsigned int uid)
897 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
899 bitmap_clear_bit (&df->insns_to_delete, uid);
900 bitmap_clear_bit (&df->insns_to_rescan, uid);
901 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
902 if (insn_info)
904 struct df_scan_problem_data *problem_data
905 = (struct df_scan_problem_data *) df_scan->problem_data;
907 /* In general, notes do not have the insn_info fields
908 initialized. However, combine deletes insns by changing them
909 to notes. How clever. So we cannot just check if it is a
910 valid insn before short circuiting this code, we need to see
911 if we actually initialized it. */
912 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
914 if (df_chain)
916 df_ref_chain_delete_du_chain (insn_info->defs);
917 df_ref_chain_delete_du_chain (insn_info->uses);
918 df_ref_chain_delete_du_chain (insn_info->eq_uses);
921 df_ref_chain_delete (insn_info->defs);
922 df_ref_chain_delete (insn_info->uses);
923 df_ref_chain_delete (insn_info->eq_uses);
925 problem_data->insn_pool->remove (insn_info);
926 DF_INSN_UID_SET (uid, NULL);
930 /* Delete all of the refs information from INSN, either right now
931 or marked for later in deferred mode. */
933 void
934 df_insn_delete (rtx_insn *insn)
936 unsigned int uid;
937 basic_block bb;
939 gcc_checking_assert (INSN_P (insn));
941 if (!df)
942 return;
944 uid = INSN_UID (insn);
945 bb = BLOCK_FOR_INSN (insn);
947 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
948 not exist anymore (as mentioned in df-core.c: "The only requirement
949 [for DF] is that there be a correct control flow graph." Clearly
950 that isn't the case after pass_free_cfg. But DF is freed much later
951 because some back-ends want to use DF info even though the CFG is
952 already gone. It's not clear to me whether that is safe, actually.
953 In any case, we expect BB to be non-NULL at least up to register
954 allocation, so disallow a non-NULL BB up to there. Not perfect
955 but better than nothing... */
956 gcc_checking_assert (bb != NULL || reload_completed);
958 df_grow_bb_info (df_scan);
959 df_grow_reg_info ();
961 /* The block must be marked as dirty now, rather than later as in
962 df_insn_rescan and df_notes_rescan because it may not be there at
963 rescanning time and the mark would blow up.
964 DEBUG_INSNs do not make a block's data flow solution dirty (at
965 worst the LUIDs are no longer contiguous). */
966 if (bb != NULL && NONDEBUG_INSN_P (insn))
967 df_set_bb_dirty (bb);
969 /* The client has deferred rescanning. */
970 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
972 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
973 if (insn_info)
975 bitmap_clear_bit (&df->insns_to_rescan, uid);
976 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
977 bitmap_set_bit (&df->insns_to_delete, uid);
979 if (dump_file)
980 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
981 return;
984 if (dump_file)
985 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
987 df_insn_info_delete (uid);
991 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
993 static void
994 df_free_collection_rec (struct df_collection_rec *collection_rec)
996 unsigned int ix;
997 struct df_scan_problem_data *problem_data
998 = (struct df_scan_problem_data *) df_scan->problem_data;
999 df_ref ref;
1000 struct df_mw_hardreg *mw;
1002 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
1003 df_free_ref (ref);
1004 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
1005 df_free_ref (ref);
1006 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1007 df_free_ref (ref);
1008 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1009 problem_data->mw_reg_pool->remove (mw);
1011 collection_rec->def_vec.release ();
1012 collection_rec->use_vec.release ();
1013 collection_rec->eq_use_vec.release ();
1014 collection_rec->mw_vec.release ();
1017 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1019 bool
1020 df_insn_rescan (rtx_insn *insn)
1022 unsigned int uid = INSN_UID (insn);
1023 struct df_insn_info *insn_info = NULL;
1024 basic_block bb = BLOCK_FOR_INSN (insn);
1025 struct df_collection_rec collection_rec;
1027 if ((!df) || (!INSN_P (insn)))
1028 return false;
1030 if (!bb)
1032 if (dump_file)
1033 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1034 return false;
1037 /* The client has disabled rescanning and plans to do it itself. */
1038 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1039 return false;
1041 df_grow_bb_info (df_scan);
1042 df_grow_reg_info ();
1044 insn_info = DF_INSN_UID_SAFE_GET (uid);
1046 /* The client has deferred rescanning. */
1047 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1049 if (!insn_info)
1051 insn_info = df_insn_create_insn_record (insn);
1052 insn_info->defs = 0;
1053 insn_info->uses = 0;
1054 insn_info->eq_uses = 0;
1055 insn_info->mw_hardregs = 0;
1057 if (dump_file)
1058 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1060 bitmap_clear_bit (&df->insns_to_delete, uid);
1061 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1062 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1063 return false;
1066 bitmap_clear_bit (&df->insns_to_delete, uid);
1067 bitmap_clear_bit (&df->insns_to_rescan, uid);
1068 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1069 if (insn_info)
1071 int luid;
1072 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1073 /* If there's no change, return false. */
1074 if (the_same)
1076 df_free_collection_rec (&collection_rec);
1077 if (dump_file)
1078 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1079 return false;
1081 if (dump_file)
1082 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1084 /* There's change - we need to delete the existing info.
1085 Since the insn isn't moved, we can salvage its LUID. */
1086 luid = DF_INSN_LUID (insn);
1087 df_insn_info_delete (uid);
1088 df_insn_create_insn_record (insn);
1089 DF_INSN_LUID (insn) = luid;
1091 else
1093 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1094 df_insn_refs_collect (&collection_rec, bb, insn_info);
1095 if (dump_file)
1096 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1099 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1100 if (!DEBUG_INSN_P (insn))
1101 df_set_bb_dirty (bb);
1103 return true;
1106 /* Same as df_insn_rescan, but don't mark the basic block as
1107 dirty. */
1109 bool
1110 df_insn_rescan_debug_internal (rtx_insn *insn)
1112 unsigned int uid = INSN_UID (insn);
1113 struct df_insn_info *insn_info;
1115 gcc_assert (DEBUG_INSN_P (insn)
1116 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1118 if (!df)
1119 return false;
1121 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1122 if (!insn_info)
1123 return false;
1125 if (dump_file)
1126 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1128 bitmap_clear_bit (&df->insns_to_delete, uid);
1129 bitmap_clear_bit (&df->insns_to_rescan, uid);
1130 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1132 if (insn_info->defs == 0
1133 && insn_info->uses == 0
1134 && insn_info->eq_uses == 0
1135 && insn_info->mw_hardregs == 0)
1136 return false;
1138 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1140 if (df_chain)
1142 df_ref_chain_delete_du_chain (insn_info->defs);
1143 df_ref_chain_delete_du_chain (insn_info->uses);
1144 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1147 df_ref_chain_delete (insn_info->defs);
1148 df_ref_chain_delete (insn_info->uses);
1149 df_ref_chain_delete (insn_info->eq_uses);
1151 insn_info->defs = 0;
1152 insn_info->uses = 0;
1153 insn_info->eq_uses = 0;
1154 insn_info->mw_hardregs = 0;
1156 return true;
1160 /* Rescan all of the insns in the function. Note that the artificial
1161 uses and defs are not touched. This function will destroy def-use
1162 or use-def chains. */
1164 void
1165 df_insn_rescan_all (void)
1167 bool no_insn_rescan = false;
1168 bool defer_insn_rescan = false;
1169 basic_block bb;
1170 bitmap_iterator bi;
1171 unsigned int uid;
1172 bitmap_head tmp;
1174 bitmap_initialize (&tmp, &df_bitmap_obstack);
1176 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1178 df_clear_flags (DF_NO_INSN_RESCAN);
1179 no_insn_rescan = true;
1182 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1184 df_clear_flags (DF_DEFER_INSN_RESCAN);
1185 defer_insn_rescan = true;
1188 bitmap_copy (&tmp, &df->insns_to_delete);
1189 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1191 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1192 if (insn_info)
1193 df_insn_info_delete (uid);
1196 bitmap_clear (&tmp);
1197 bitmap_clear (&df->insns_to_delete);
1198 bitmap_clear (&df->insns_to_rescan);
1199 bitmap_clear (&df->insns_to_notes_rescan);
1201 FOR_EACH_BB_FN (bb, cfun)
1203 rtx_insn *insn;
1204 FOR_BB_INSNS (bb, insn)
1206 df_insn_rescan (insn);
1210 if (no_insn_rescan)
1211 df_set_flags (DF_NO_INSN_RESCAN);
1212 if (defer_insn_rescan)
1213 df_set_flags (DF_DEFER_INSN_RESCAN);
1217 /* Process all of the deferred rescans or deletions. */
1219 void
1220 df_process_deferred_rescans (void)
1222 bool no_insn_rescan = false;
1223 bool defer_insn_rescan = false;
1224 bitmap_iterator bi;
1225 unsigned int uid;
1226 bitmap_head tmp;
1228 bitmap_initialize (&tmp, &df_bitmap_obstack);
1230 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1232 df_clear_flags (DF_NO_INSN_RESCAN);
1233 no_insn_rescan = true;
1236 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1238 df_clear_flags (DF_DEFER_INSN_RESCAN);
1239 defer_insn_rescan = true;
1242 if (dump_file)
1243 fprintf (dump_file, "starting the processing of deferred insns\n");
1245 bitmap_copy (&tmp, &df->insns_to_delete);
1246 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1248 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1249 if (insn_info)
1250 df_insn_info_delete (uid);
1253 bitmap_copy (&tmp, &df->insns_to_rescan);
1254 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1256 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1257 if (insn_info)
1258 df_insn_rescan (insn_info->insn);
1261 bitmap_copy (&tmp, &df->insns_to_notes_rescan);
1262 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1264 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1265 if (insn_info)
1266 df_notes_rescan (insn_info->insn);
1269 if (dump_file)
1270 fprintf (dump_file, "ending the processing of deferred insns\n");
1272 bitmap_clear (&tmp);
1273 bitmap_clear (&df->insns_to_delete);
1274 bitmap_clear (&df->insns_to_rescan);
1275 bitmap_clear (&df->insns_to_notes_rescan);
1277 if (no_insn_rescan)
1278 df_set_flags (DF_NO_INSN_RESCAN);
1279 if (defer_insn_rescan)
1280 df_set_flags (DF_DEFER_INSN_RESCAN);
1282 /* If someone changed regs_ever_live during this pass, fix up the
1283 entry and exit blocks. */
1284 if (df->redo_entry_and_exit)
1286 df_update_entry_exit_and_calls ();
1287 df->redo_entry_and_exit = false;
1292 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1293 the uses if INCLUDE_USES. Include the eq_uses if
1294 INCLUDE_EQ_USES. */
1296 static unsigned int
1297 df_count_refs (bool include_defs, bool include_uses,
1298 bool include_eq_uses)
1300 unsigned int regno;
1301 int size = 0;
1302 unsigned int m = df->regs_inited;
1304 for (regno = 0; regno < m; regno++)
1306 if (include_defs)
1307 size += DF_REG_DEF_COUNT (regno);
1308 if (include_uses)
1309 size += DF_REG_USE_COUNT (regno);
1310 if (include_eq_uses)
1311 size += DF_REG_EQ_USE_COUNT (regno);
1313 return size;
1317 /* Take build ref table for either the uses or defs from the reg-use
1318 or reg-def chains. This version processes the refs in reg order
1319 which is likely to be best if processing the whole function. */
1321 static void
1322 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1323 bool include_defs,
1324 bool include_uses,
1325 bool include_eq_uses)
1327 unsigned int m = df->regs_inited;
1328 unsigned int regno;
1329 unsigned int offset = 0;
1330 unsigned int start;
1332 if (df->changeable_flags & DF_NO_HARD_REGS)
1334 start = FIRST_PSEUDO_REGISTER;
1335 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1336 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1338 else
1339 start = 0;
1341 ref_info->total_size
1342 = df_count_refs (include_defs, include_uses, include_eq_uses);
1344 df_check_and_grow_ref_info (ref_info, 1);
1346 for (regno = start; regno < m; regno++)
1348 int count = 0;
1349 ref_info->begin[regno] = offset;
1350 if (include_defs)
1352 df_ref ref = DF_REG_DEF_CHAIN (regno);
1353 while (ref)
1355 ref_info->refs[offset] = ref;
1356 DF_REF_ID (ref) = offset++;
1357 count++;
1358 ref = DF_REF_NEXT_REG (ref);
1359 gcc_checking_assert (offset < ref_info->refs_size);
1362 if (include_uses)
1364 df_ref ref = DF_REG_USE_CHAIN (regno);
1365 while (ref)
1367 ref_info->refs[offset] = ref;
1368 DF_REF_ID (ref) = offset++;
1369 count++;
1370 ref = DF_REF_NEXT_REG (ref);
1371 gcc_checking_assert (offset < ref_info->refs_size);
1374 if (include_eq_uses)
1376 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1377 while (ref)
1379 ref_info->refs[offset] = ref;
1380 DF_REF_ID (ref) = offset++;
1381 count++;
1382 ref = DF_REF_NEXT_REG (ref);
1383 gcc_checking_assert (offset < ref_info->refs_size);
1386 ref_info->count[regno] = count;
1389 /* The bitmap size is not decremented when refs are deleted. So
1390 reset it now that we have squished out all of the empty
1391 slots. */
1392 ref_info->table_size = offset;
1396 /* Take build ref table for either the uses or defs from the reg-use
1397 or reg-def chains. This version processes the refs in insn order
1398 which is likely to be best if processing some segment of the
1399 function. */
1401 static void
1402 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1403 bool include_defs,
1404 bool include_uses,
1405 bool include_eq_uses)
1407 bitmap_iterator bi;
1408 unsigned int bb_index;
1409 unsigned int m = df->regs_inited;
1410 unsigned int offset = 0;
1411 unsigned int r;
1412 unsigned int start
1413 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1415 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1416 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1418 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1419 df_check_and_grow_ref_info (ref_info, 1);
1421 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1423 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1424 rtx_insn *insn;
1425 df_ref def, use;
1427 if (include_defs)
1428 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1430 unsigned int regno = DF_REF_REGNO (def);
1431 ref_info->count[regno]++;
1433 if (include_uses)
1434 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1436 unsigned int regno = DF_REF_REGNO (use);
1437 ref_info->count[regno]++;
1440 FOR_BB_INSNS (bb, insn)
1442 if (INSN_P (insn))
1444 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1446 if (include_defs)
1447 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1449 unsigned int regno = DF_REF_REGNO (def);
1450 ref_info->count[regno]++;
1452 if (include_uses)
1453 FOR_EACH_INSN_INFO_USE (use, insn_info)
1455 unsigned int regno = DF_REF_REGNO (use);
1456 ref_info->count[regno]++;
1458 if (include_eq_uses)
1459 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1461 unsigned int regno = DF_REF_REGNO (use);
1462 ref_info->count[regno]++;
1468 for (r = start; r < m; r++)
1470 ref_info->begin[r] = offset;
1471 offset += ref_info->count[r];
1472 ref_info->count[r] = 0;
1475 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1477 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1478 rtx_insn *insn;
1479 df_ref def, use;
1481 if (include_defs)
1482 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1484 unsigned int regno = DF_REF_REGNO (def);
1485 if (regno >= start)
1487 unsigned int id
1488 = ref_info->begin[regno] + ref_info->count[regno]++;
1489 DF_REF_ID (def) = id;
1490 ref_info->refs[id] = def;
1493 if (include_uses)
1494 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1496 unsigned int regno = DF_REF_REGNO (def);
1497 if (regno >= start)
1499 unsigned int id
1500 = ref_info->begin[regno] + ref_info->count[regno]++;
1501 DF_REF_ID (use) = id;
1502 ref_info->refs[id] = use;
1506 FOR_BB_INSNS (bb, insn)
1508 if (INSN_P (insn))
1510 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1512 if (include_defs)
1513 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1515 unsigned int regno = DF_REF_REGNO (def);
1516 if (regno >= start)
1518 unsigned int id
1519 = ref_info->begin[regno] + ref_info->count[regno]++;
1520 DF_REF_ID (def) = id;
1521 ref_info->refs[id] = def;
1524 if (include_uses)
1525 FOR_EACH_INSN_INFO_USE (use, insn_info)
1527 unsigned int regno = DF_REF_REGNO (use);
1528 if (regno >= start)
1530 unsigned int id
1531 = ref_info->begin[regno] + ref_info->count[regno]++;
1532 DF_REF_ID (use) = id;
1533 ref_info->refs[id] = use;
1536 if (include_eq_uses)
1537 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1539 unsigned int regno = DF_REF_REGNO (use);
1540 if (regno >= start)
1542 unsigned int id
1543 = ref_info->begin[regno] + ref_info->count[regno]++;
1544 DF_REF_ID (use) = id;
1545 ref_info->refs[id] = use;
1552 /* The bitmap size is not decremented when refs are deleted. So
1553 reset it now that we have squished out all of the empty
1554 slots. */
1556 ref_info->table_size = offset;
1559 /* Take build ref table for either the uses or defs from the reg-use
1560 or reg-def chains. */
1562 static void
1563 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1564 bool include_defs,
1565 bool include_uses,
1566 bool include_eq_uses)
1568 if (df->analyze_subset)
1569 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1570 include_uses, include_eq_uses);
1571 else
1572 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1573 include_uses, include_eq_uses);
1577 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1578 static unsigned int
1579 df_add_refs_to_table (unsigned int offset,
1580 struct df_ref_info *ref_info,
1581 df_ref ref)
1583 for (; ref; ref = DF_REF_NEXT_LOC (ref))
1584 if (!(df->changeable_flags & DF_NO_HARD_REGS)
1585 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1587 ref_info->refs[offset] = ref;
1588 DF_REF_ID (ref) = offset++;
1590 return offset;
1594 /* Count the number of refs in all of the insns of BB. Include the
1595 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1596 eq_uses if INCLUDE_EQ_USES. */
1598 static unsigned int
1599 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1600 struct df_ref_info *ref_info,
1601 bool include_defs, bool include_uses,
1602 bool include_eq_uses)
1604 rtx_insn *insn;
1606 if (include_defs)
1607 offset = df_add_refs_to_table (offset, ref_info,
1608 df_get_artificial_defs (bb->index));
1609 if (include_uses)
1610 offset = df_add_refs_to_table (offset, ref_info,
1611 df_get_artificial_uses (bb->index));
1613 FOR_BB_INSNS (bb, insn)
1614 if (INSN_P (insn))
1616 unsigned int uid = INSN_UID (insn);
1617 if (include_defs)
1618 offset = df_add_refs_to_table (offset, ref_info,
1619 DF_INSN_UID_DEFS (uid));
1620 if (include_uses)
1621 offset = df_add_refs_to_table (offset, ref_info,
1622 DF_INSN_UID_USES (uid));
1623 if (include_eq_uses)
1624 offset = df_add_refs_to_table (offset, ref_info,
1625 DF_INSN_UID_EQ_USES (uid));
1627 return offset;
1631 /* Organize the refs by insn into the table in REF_INFO. If
1632 blocks_to_analyze is defined, use that set, otherwise the entire
1633 program. Include the defs if INCLUDE_DEFS. Include the uses if
1634 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1636 static void
1637 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1638 bool include_defs, bool include_uses,
1639 bool include_eq_uses)
1641 basic_block bb;
1642 unsigned int offset = 0;
1644 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1645 df_check_and_grow_ref_info (ref_info, 1);
1646 if (df->blocks_to_analyze)
1648 bitmap_iterator bi;
1649 unsigned int index;
1651 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1653 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1654 index),
1655 offset, ref_info,
1656 include_defs, include_uses,
1657 include_eq_uses);
1660 ref_info->table_size = offset;
1662 else
1664 FOR_ALL_BB_FN (bb, cfun)
1665 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1666 include_defs, include_uses,
1667 include_eq_uses);
1668 ref_info->table_size = offset;
1673 /* If the use refs in DF are not organized, reorganize them. */
1675 void
1676 df_maybe_reorganize_use_refs (enum df_ref_order order)
1678 if (order == df->use_info.ref_order)
1679 return;
1681 switch (order)
1683 case DF_REF_ORDER_BY_REG:
1684 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1685 break;
1687 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1688 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1689 break;
1691 case DF_REF_ORDER_BY_INSN:
1692 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1693 break;
1695 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1696 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1697 break;
1699 case DF_REF_ORDER_NO_TABLE:
1700 free (df->use_info.refs);
1701 df->use_info.refs = NULL;
1702 df->use_info.refs_size = 0;
1703 break;
1705 case DF_REF_ORDER_UNORDERED:
1706 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1707 gcc_unreachable ();
1708 break;
1711 df->use_info.ref_order = order;
1715 /* If the def refs in DF are not organized, reorganize them. */
1717 void
1718 df_maybe_reorganize_def_refs (enum df_ref_order order)
1720 if (order == df->def_info.ref_order)
1721 return;
1723 switch (order)
1725 case DF_REF_ORDER_BY_REG:
1726 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1727 break;
1729 case DF_REF_ORDER_BY_INSN:
1730 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1731 break;
1733 case DF_REF_ORDER_NO_TABLE:
1734 free (df->def_info.refs);
1735 df->def_info.refs = NULL;
1736 df->def_info.refs_size = 0;
1737 break;
1739 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1740 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1741 case DF_REF_ORDER_UNORDERED:
1742 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1743 gcc_unreachable ();
1744 break;
1747 df->def_info.ref_order = order;
1751 /* Change all of the basic block references in INSN to use the insn's
1752 current basic block. This function is called from routines that move
1753 instructions from one block to another. */
1755 void
1756 df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1758 basic_block old_bb = BLOCK_FOR_INSN (insn);
1759 struct df_insn_info *insn_info;
1760 unsigned int uid = INSN_UID (insn);
1762 if (old_bb == new_bb)
1763 return;
1765 set_block_for_insn (insn, new_bb);
1767 if (!df)
1768 return;
1770 if (dump_file)
1771 fprintf (dump_file, "changing bb of uid %d\n", uid);
1773 insn_info = DF_INSN_UID_SAFE_GET (uid);
1774 if (insn_info == NULL)
1776 if (dump_file)
1777 fprintf (dump_file, " unscanned insn\n");
1778 df_insn_rescan (insn);
1779 return;
1782 if (!INSN_P (insn))
1783 return;
1785 df_set_bb_dirty (new_bb);
1786 if (old_bb)
1788 if (dump_file)
1789 fprintf (dump_file, " from %d to %d\n",
1790 old_bb->index, new_bb->index);
1791 df_set_bb_dirty (old_bb);
1793 else
1794 if (dump_file)
1795 fprintf (dump_file, " to %d\n", new_bb->index);
1799 /* Helper function for df_ref_change_reg_with_loc. */
1801 static void
1802 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1803 struct df_reg_info *new_df,
1804 unsigned int new_regno, rtx loc)
1806 df_ref the_ref = old_df->reg_chain;
1808 while (the_ref)
1810 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1811 && DF_REF_LOC (the_ref)
1812 && (*DF_REF_LOC (the_ref) == loc))
1814 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1815 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1816 df_ref *ref_ptr;
1817 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1819 DF_REF_REGNO (the_ref) = new_regno;
1820 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1822 /* Pull the_ref out of the old regno chain. */
1823 if (prev_ref)
1824 DF_REF_NEXT_REG (prev_ref) = next_ref;
1825 else
1826 old_df->reg_chain = next_ref;
1827 if (next_ref)
1828 DF_REF_PREV_REG (next_ref) = prev_ref;
1829 old_df->n_refs--;
1831 /* Put the ref into the new regno chain. */
1832 DF_REF_PREV_REG (the_ref) = NULL;
1833 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1834 if (new_df->reg_chain)
1835 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1836 new_df->reg_chain = the_ref;
1837 new_df->n_refs++;
1838 if (DF_REF_BB (the_ref))
1839 df_set_bb_dirty (DF_REF_BB (the_ref));
1841 /* Need to sort the record again that the ref was in because
1842 the regno is a sorting key. First, find the right
1843 record. */
1844 if (DF_REF_REG_DEF_P (the_ref))
1845 ref_ptr = &insn_info->defs;
1846 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1847 ref_ptr = &insn_info->eq_uses;
1848 else
1849 ref_ptr = &insn_info->uses;
1850 if (dump_file)
1851 fprintf (dump_file, "changing reg in insn %d\n",
1852 DF_REF_INSN_UID (the_ref));
1854 /* Stop if we find the current reference or where the reference
1855 needs to be. */
1856 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1857 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1858 if (*ref_ptr != the_ref)
1860 /* The reference needs to be promoted up the list. */
1861 df_ref next = DF_REF_NEXT_LOC (the_ref);
1862 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1863 *ref_ptr = the_ref;
1865 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1866 while (*ref_ptr != the_ref);
1867 *ref_ptr = next;
1869 else if (DF_REF_NEXT_LOC (the_ref)
1870 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1872 /* The reference needs to be demoted down the list. */
1873 *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1875 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1876 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1877 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1878 *ref_ptr = the_ref;
1881 the_ref = next_ref;
1883 else
1884 the_ref = DF_REF_NEXT_REG (the_ref);
1889 /* Change the regno of register LOC to NEW_REGNO and update the df
1890 information accordingly. Refs that do not match LOC are not changed
1891 which means that artificial refs are not changed since they have no loc.
1892 This call is to support the SET_REGNO macro. */
1894 void
1895 df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1897 unsigned int old_regno = REGNO (loc);
1898 if (old_regno == new_regno)
1899 return;
1901 if (df)
1903 df_grow_reg_info ();
1905 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1906 DF_REG_DEF_GET (new_regno),
1907 new_regno, loc);
1908 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1909 DF_REG_USE_GET (new_regno),
1910 new_regno, loc);
1911 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1912 DF_REG_EQ_USE_GET (new_regno),
1913 new_regno, loc);
1915 set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1919 /* Delete the mw_hardregs that point into the eq_notes. */
1921 static void
1922 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1924 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1925 struct df_scan_problem_data *problem_data
1926 = (struct df_scan_problem_data *) df_scan->problem_data;
1928 while (*mw_ptr)
1930 df_mw_hardreg *mw = *mw_ptr;
1931 if (mw->flags & DF_REF_IN_NOTE)
1933 *mw_ptr = DF_MWS_NEXT (mw);
1934 problem_data->mw_reg_pool->remove (mw);
1936 else
1937 mw_ptr = &DF_MWS_NEXT (mw);
1942 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1944 void
1945 df_notes_rescan (rtx_insn *insn)
1947 struct df_insn_info *insn_info;
1948 unsigned int uid = INSN_UID (insn);
1950 if (!df)
1951 return;
1953 /* The client has disabled rescanning and plans to do it itself. */
1954 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1955 return;
1957 /* Do nothing if the insn hasn't been emitted yet. */
1958 if (!BLOCK_FOR_INSN (insn))
1959 return;
1961 df_grow_bb_info (df_scan);
1962 df_grow_reg_info ();
1964 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1966 /* The client has deferred rescanning. */
1967 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1969 if (!insn_info)
1971 insn_info = df_insn_create_insn_record (insn);
1972 insn_info->defs = 0;
1973 insn_info->uses = 0;
1974 insn_info->eq_uses = 0;
1975 insn_info->mw_hardregs = 0;
1978 bitmap_clear_bit (&df->insns_to_delete, uid);
1979 /* If the insn is set to be rescanned, it does not need to also
1980 be notes rescanned. */
1981 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1982 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1983 return;
1986 bitmap_clear_bit (&df->insns_to_delete, uid);
1987 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1989 if (insn_info)
1991 basic_block bb = BLOCK_FOR_INSN (insn);
1992 rtx note;
1993 struct df_collection_rec collection_rec;
1994 unsigned int i;
1996 df_mw_hardreg_chain_delete_eq_uses (insn_info);
1997 df_ref_chain_delete (insn_info->eq_uses);
1998 insn_info->eq_uses = NULL;
2000 /* Process REG_EQUIV/REG_EQUAL notes */
2001 for (note = REG_NOTES (insn); note;
2002 note = XEXP (note, 1))
2004 switch (REG_NOTE_KIND (note))
2006 case REG_EQUIV:
2007 case REG_EQUAL:
2008 df_uses_record (&collection_rec,
2009 &XEXP (note, 0), DF_REF_REG_USE,
2010 bb, insn_info, DF_REF_IN_NOTE);
2011 default:
2012 break;
2016 /* Find some place to put any new mw_hardregs. */
2017 df_canonize_collection_rec (&collection_rec);
2018 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2019 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2021 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2022 mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2023 DF_MWS_NEXT (mw) = *mw_ptr;
2024 *mw_ptr = mw;
2025 mw_ptr = &DF_MWS_NEXT (mw);
2027 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2029 else
2030 df_insn_rescan (insn);
2035 /*----------------------------------------------------------------------------
2036 Hard core instruction scanning code. No external interfaces here,
2037 just a lot of routines that look inside insns.
2038 ----------------------------------------------------------------------------*/
2041 /* Return true if the contents of two df_ref's are identical.
2042 It ignores DF_REF_MARKER. */
2044 static bool
2045 df_ref_equal_p (df_ref ref1, df_ref ref2)
2047 if (!ref2)
2048 return false;
2050 if (ref1 == ref2)
2051 return true;
2053 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2054 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2055 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2056 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2057 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2058 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2059 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2060 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2061 return false;
2063 switch (DF_REF_CLASS (ref1))
2065 case DF_REF_ARTIFICIAL:
2066 case DF_REF_BASE:
2067 return true;
2069 case DF_REF_REGULAR:
2070 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2072 default:
2073 gcc_unreachable ();
2075 return false;
2079 /* Compare REF1 and REF2 for sorting. This is only called from places
2080 where all of the refs are of the same type, in the same insn, and
2081 have the same bb. So these fields are not checked. */
2083 static int
2084 df_ref_compare (df_ref ref1, df_ref ref2)
2086 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2087 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2089 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2090 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2092 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2093 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2095 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2096 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2098 /* Cannot look at the LOC field on artificial refs. */
2099 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2100 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2101 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2103 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2105 /* If two refs are identical except that one of them has is from
2106 a mw and one is not, we need to have the one with the mw
2107 first. */
2108 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2109 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2110 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2111 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2112 return -1;
2113 else
2114 return 1;
2117 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2120 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2122 static int
2123 df_ref_ptr_compare (const void *r1, const void *r2)
2125 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2128 /* Sort and compress a set of refs. */
2130 static void
2131 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2133 unsigned int count;
2134 unsigned int i;
2135 unsigned int dist = 0;
2137 count = ref_vec->length ();
2139 /* If there are 1 or 0 elements, there is nothing to do. */
2140 if (count < 2)
2141 return;
2142 else if (count == 2)
2144 df_ref r0 = (*ref_vec)[0];
2145 df_ref r1 = (*ref_vec)[1];
2146 if (df_ref_compare (r0, r1) > 0)
2147 std::swap ((*ref_vec)[0], (*ref_vec)[1]);
2149 else
2151 for (i = 0; i < count - 1; i++)
2153 df_ref r0 = (*ref_vec)[i];
2154 df_ref r1 = (*ref_vec)[i + 1];
2155 if (df_ref_compare (r0, r1) >= 0)
2156 break;
2158 /* If the array is already strictly ordered,
2159 which is the most common case for large COUNT case
2160 (which happens for CALL INSNs),
2161 no need to sort and filter out duplicate.
2162 Simply return the count.
2163 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2164 of DF_REF_COMPARE. */
2165 if (i == count - 1)
2166 return;
2167 ref_vec->qsort (df_ref_ptr_compare);
2170 for (i=0; i<count-dist; i++)
2172 /* Find the next ref that is not equal to the current ref. */
2173 while (i + dist + 1 < count
2174 && df_ref_equal_p ((*ref_vec)[i],
2175 (*ref_vec)[i + dist + 1]))
2177 df_free_ref ((*ref_vec)[i + dist + 1]);
2178 dist++;
2180 /* Copy it down to the next position. */
2181 if (dist && i + dist + 1 < count)
2182 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2185 count -= dist;
2186 ref_vec->truncate (count);
2190 /* Return true if the contents of two df_ref's are identical.
2191 It ignores DF_REF_MARKER. */
2193 static bool
2194 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2196 if (!mw2)
2197 return false;
2198 return (mw1 == mw2) ||
2199 (mw1->mw_reg == mw2->mw_reg
2200 && mw1->type == mw2->type
2201 && mw1->flags == mw2->flags
2202 && mw1->start_regno == mw2->start_regno
2203 && mw1->end_regno == mw2->end_regno);
2207 /* Compare MW1 and MW2 for sorting. */
2209 static int
2210 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2212 if (mw1->type != mw2->type)
2213 return mw1->type - mw2->type;
2215 if (mw1->flags != mw2->flags)
2216 return mw1->flags - mw2->flags;
2218 if (mw1->start_regno != mw2->start_regno)
2219 return mw1->start_regno - mw2->start_regno;
2221 if (mw1->end_regno != mw2->end_regno)
2222 return mw1->end_regno - mw2->end_regno;
2224 if (mw1->mw_reg != mw2->mw_reg)
2225 return mw1->mw_order - mw2->mw_order;
2227 return 0;
2230 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2232 static int
2233 df_mw_ptr_compare (const void *m1, const void *m2)
2235 return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2236 *(const df_mw_hardreg *const *) m2);
2239 /* Sort and compress a set of refs. */
2241 static void
2242 df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec)
2244 unsigned int count;
2245 struct df_scan_problem_data *problem_data
2246 = (struct df_scan_problem_data *) df_scan->problem_data;
2247 unsigned int i;
2248 unsigned int dist = 0;
2250 count = mw_vec->length ();
2251 if (count < 2)
2252 return;
2253 else if (count == 2)
2255 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2256 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2257 if (df_mw_compare (m0, m1) > 0)
2259 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2260 (*mw_vec)[0] = (*mw_vec)[1];
2261 (*mw_vec)[1] = tmp;
2264 else
2265 mw_vec->qsort (df_mw_ptr_compare);
2267 for (i=0; i<count-dist; i++)
2269 /* Find the next ref that is not equal to the current ref. */
2270 while (i + dist + 1 < count
2271 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2273 problem_data->mw_reg_pool->remove ((*mw_vec)[i + dist + 1]);
2274 dist++;
2276 /* Copy it down to the next position. */
2277 if (dist && i + dist + 1 < count)
2278 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2281 count -= dist;
2282 mw_vec->truncate (count);
2286 /* Sort and remove duplicates from the COLLECTION_REC. */
2288 static void
2289 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2291 df_sort_and_compress_refs (&collection_rec->def_vec);
2292 df_sort_and_compress_refs (&collection_rec->use_vec);
2293 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2294 df_sort_and_compress_mws (&collection_rec->mw_vec);
2298 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2300 static void
2301 df_install_ref (df_ref this_ref,
2302 struct df_reg_info *reg_info,
2303 struct df_ref_info *ref_info,
2304 bool add_to_table)
2306 unsigned int regno = DF_REF_REGNO (this_ref);
2307 /* Add the ref to the reg_{def,use,eq_use} chain. */
2308 df_ref head = reg_info->reg_chain;
2310 reg_info->reg_chain = this_ref;
2311 reg_info->n_refs++;
2313 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2315 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2316 df->hard_regs_live_count[regno]++;
2319 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2320 && DF_REF_PREV_REG (this_ref) == NULL);
2322 DF_REF_NEXT_REG (this_ref) = head;
2324 /* We cannot actually link to the head of the chain. */
2325 DF_REF_PREV_REG (this_ref) = NULL;
2327 if (head)
2328 DF_REF_PREV_REG (head) = this_ref;
2330 if (add_to_table)
2332 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2333 df_check_and_grow_ref_info (ref_info, 1);
2334 DF_REF_ID (this_ref) = ref_info->table_size;
2335 /* Add the ref to the big array of defs. */
2336 ref_info->refs[ref_info->table_size] = this_ref;
2337 ref_info->table_size++;
2339 else
2340 DF_REF_ID (this_ref) = -1;
2342 ref_info->total_size++;
2346 /* This function takes one of the groups of refs (defs, uses or
2347 eq_uses) and installs the entire group into the insn. It also adds
2348 each of these refs into the appropriate chains. */
2350 static df_ref
2351 df_install_refs (basic_block bb,
2352 const vec<df_ref, va_heap> *old_vec,
2353 struct df_reg_info **reg_info,
2354 struct df_ref_info *ref_info,
2355 bool is_notes)
2357 unsigned int count = old_vec->length ();
2358 if (count)
2360 bool add_to_table;
2361 df_ref this_ref;
2362 unsigned int ix;
2364 switch (ref_info->ref_order)
2366 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2367 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2368 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2369 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2370 add_to_table = true;
2371 break;
2372 case DF_REF_ORDER_UNORDERED:
2373 case DF_REF_ORDER_BY_REG:
2374 case DF_REF_ORDER_BY_INSN:
2375 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2376 add_to_table = !is_notes;
2377 break;
2378 default:
2379 add_to_table = false;
2380 break;
2383 /* Do not add if ref is not in the right blocks. */
2384 if (add_to_table && df->analyze_subset)
2385 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2387 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2389 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2390 ? (*old_vec)[ix + 1]
2391 : NULL);
2392 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2393 ref_info, add_to_table);
2395 return (*old_vec)[0];
2397 else
2398 return 0;
2402 /* This function takes the mws installs the entire group into the
2403 insn. */
2405 static struct df_mw_hardreg *
2406 df_install_mws (const vec<df_mw_hardreg_ptr, va_heap> *old_vec)
2408 unsigned int count = old_vec->length ();
2409 if (count)
2411 for (unsigned int i = 0; i < count - 1; i++)
2412 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2413 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2414 return (*old_vec)[0];
2416 else
2417 return 0;
2421 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2422 chains and update other necessary information. */
2424 static void
2425 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2426 basic_block bb, rtx_insn *insn, unsigned int flags)
2428 if (insn)
2430 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2431 /* If there is a vector in the collection rec, add it to the
2432 insn. A null rec is a signal that the caller will handle the
2433 chain specially. */
2434 if (flags & copy_defs)
2436 gcc_checking_assert (!insn_rec->defs);
2437 insn_rec->defs
2438 = df_install_refs (bb, &collection_rec->def_vec,
2439 df->def_regs,
2440 &df->def_info, false);
2442 if (flags & copy_uses)
2444 gcc_checking_assert (!insn_rec->uses);
2445 insn_rec->uses
2446 = df_install_refs (bb, &collection_rec->use_vec,
2447 df->use_regs,
2448 &df->use_info, false);
2450 if (flags & copy_eq_uses)
2452 gcc_checking_assert (!insn_rec->eq_uses);
2453 insn_rec->eq_uses
2454 = df_install_refs (bb, &collection_rec->eq_use_vec,
2455 df->eq_use_regs,
2456 &df->use_info, true);
2458 if (flags & copy_mw)
2460 gcc_checking_assert (!insn_rec->mw_hardregs);
2461 insn_rec->mw_hardregs
2462 = df_install_mws (&collection_rec->mw_vec);
2465 else
2467 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2469 gcc_checking_assert (!bb_info->artificial_defs);
2470 bb_info->artificial_defs
2471 = df_install_refs (bb, &collection_rec->def_vec,
2472 df->def_regs,
2473 &df->def_info, false);
2474 gcc_checking_assert (!bb_info->artificial_uses);
2475 bb_info->artificial_uses
2476 = df_install_refs (bb, &collection_rec->use_vec,
2477 df->use_regs,
2478 &df->use_info, false);
2483 /* Allocate a ref and initialize its fields. */
2485 static df_ref
2486 df_ref_create_structure (enum df_ref_class cl,
2487 struct df_collection_rec *collection_rec,
2488 rtx reg, rtx *loc,
2489 basic_block bb, struct df_insn_info *info,
2490 enum df_ref_type ref_type,
2491 int ref_flags)
2493 df_ref this_ref = NULL;
2494 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2495 struct df_scan_problem_data *problem_data
2496 = (struct df_scan_problem_data *) df_scan->problem_data;
2498 switch (cl)
2500 case DF_REF_BASE:
2501 this_ref = (df_ref) (problem_data->ref_base_pool->allocate ());
2502 gcc_checking_assert (loc == NULL);
2503 break;
2505 case DF_REF_ARTIFICIAL:
2506 this_ref = (df_ref) (problem_data->ref_artificial_pool->allocate ());
2507 this_ref->artificial_ref.bb = bb;
2508 gcc_checking_assert (loc == NULL);
2509 break;
2511 case DF_REF_REGULAR:
2512 this_ref = (df_ref) (problem_data->ref_regular_pool->allocate ());
2513 this_ref->regular_ref.loc = loc;
2514 gcc_checking_assert (loc);
2515 break;
2518 DF_REF_CLASS (this_ref) = cl;
2519 DF_REF_ID (this_ref) = -1;
2520 DF_REF_REG (this_ref) = reg;
2521 DF_REF_REGNO (this_ref) = regno;
2522 DF_REF_TYPE (this_ref) = ref_type;
2523 DF_REF_INSN_INFO (this_ref) = info;
2524 DF_REF_CHAIN (this_ref) = NULL;
2525 DF_REF_FLAGS (this_ref) = ref_flags;
2526 DF_REF_NEXT_REG (this_ref) = NULL;
2527 DF_REF_PREV_REG (this_ref) = NULL;
2528 DF_REF_ORDER (this_ref) = df->ref_order++;
2530 /* We need to clear this bit because fwprop, and in the future
2531 possibly other optimizations sometimes create new refs using ond
2532 refs as the model. */
2533 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2535 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2536 if (regno < FIRST_PSEUDO_REGISTER
2537 && !DF_REF_IS_ARTIFICIAL (this_ref)
2538 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2540 if (DF_REF_REG_DEF_P (this_ref))
2542 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2543 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2545 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2546 && (regno == FRAME_POINTER_REGNUM
2547 || regno == ARG_POINTER_REGNUM)))
2548 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2551 if (collection_rec)
2553 if (DF_REF_REG_DEF_P (this_ref))
2554 collection_rec->def_vec.safe_push (this_ref);
2555 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2556 collection_rec->eq_use_vec.safe_push (this_ref);
2557 else
2558 collection_rec->use_vec.safe_push (this_ref);
2560 else
2561 df_install_ref_incremental (this_ref);
2563 return this_ref;
2567 /* Create new references of type DF_REF_TYPE for each part of register REG
2568 at address LOC within INSN of BB. */
2571 static void
2572 df_ref_record (enum df_ref_class cl,
2573 struct df_collection_rec *collection_rec,
2574 rtx reg, rtx *loc,
2575 basic_block bb, struct df_insn_info *insn_info,
2576 enum df_ref_type ref_type,
2577 int ref_flags)
2579 unsigned int regno;
2581 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2583 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2584 if (regno < FIRST_PSEUDO_REGISTER)
2586 struct df_mw_hardreg *hardreg = NULL;
2587 struct df_scan_problem_data *problem_data
2588 = (struct df_scan_problem_data *) df_scan->problem_data;
2589 unsigned int i;
2590 unsigned int endregno;
2591 df_ref ref;
2593 if (GET_CODE (reg) == SUBREG)
2595 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2596 SUBREG_BYTE (reg), GET_MODE (reg));
2597 endregno = regno + subreg_nregs (reg);
2599 else
2600 endregno = END_REGNO (reg);
2602 /* If this is a multiword hardreg, we create some extra
2603 datastructures that will enable us to easily build REG_DEAD
2604 and REG_UNUSED notes. */
2605 if (collection_rec
2606 && (endregno != regno + 1) && insn_info)
2608 /* Sets to a subreg of a multiword register are partial.
2609 Sets to a non-subreg of a multiword register are not. */
2610 if (GET_CODE (reg) == SUBREG)
2611 ref_flags |= DF_REF_PARTIAL;
2612 ref_flags |= DF_REF_MW_HARDREG;
2614 hardreg = problem_data->mw_reg_pool->allocate ();
2615 hardreg->type = ref_type;
2616 hardreg->flags = ref_flags;
2617 hardreg->mw_reg = reg;
2618 hardreg->start_regno = regno;
2619 hardreg->end_regno = endregno - 1;
2620 hardreg->mw_order = df->ref_order++;
2621 collection_rec->mw_vec.safe_push (hardreg);
2624 for (i = regno; i < endregno; i++)
2626 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2627 bb, insn_info, ref_type, ref_flags);
2629 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2632 else
2634 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2635 ref_type, ref_flags);
2640 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2641 covered by the outer mode is smaller than that covered by the inner mode,
2642 is a read-modify-write operation.
2643 This function returns true iff the SUBREG X is such a SUBREG. */
2645 bool
2646 df_read_modify_subreg_p (rtx x)
2648 unsigned int isize, osize;
2649 if (GET_CODE (x) != SUBREG)
2650 return false;
2651 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2652 osize = GET_MODE_SIZE (GET_MODE (x));
2653 return isize > osize
2654 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2658 /* Process all the registers defined in the rtx pointed by LOC.
2659 Autoincrement/decrement definitions will be picked up by df_uses_record.
2660 Any change here has to be matched in df_find_hard_reg_defs_1. */
2662 static void
2663 df_def_record_1 (struct df_collection_rec *collection_rec,
2664 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2665 int flags)
2667 rtx dst = *loc;
2669 /* It is legal to have a set destination be a parallel. */
2670 if (GET_CODE (dst) == PARALLEL)
2672 int i;
2673 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2675 rtx temp = XVECEXP (dst, 0, i);
2676 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2677 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2678 bb, insn_info, flags);
2680 return;
2683 if (GET_CODE (dst) == STRICT_LOW_PART)
2685 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2687 loc = &XEXP (dst, 0);
2688 dst = *loc;
2691 if (GET_CODE (dst) == ZERO_EXTRACT)
2693 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2695 loc = &XEXP (dst, 0);
2696 dst = *loc;
2699 /* At this point if we do not have a reg or a subreg, just return. */
2700 if (REG_P (dst))
2702 df_ref_record (DF_REF_REGULAR, collection_rec,
2703 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2705 /* We want to keep sp alive everywhere - by making all
2706 writes to sp also use of sp. */
2707 if (REGNO (dst) == STACK_POINTER_REGNUM)
2708 df_ref_record (DF_REF_BASE, collection_rec,
2709 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2711 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2713 if (df_read_modify_subreg_p (dst))
2714 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2716 flags |= DF_REF_SUBREG;
2718 df_ref_record (DF_REF_REGULAR, collection_rec,
2719 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2724 /* Process all the registers defined in the pattern rtx, X. Any change
2725 here has to be matched in df_find_hard_reg_defs. */
2727 static void
2728 df_defs_record (struct df_collection_rec *collection_rec,
2729 rtx x, basic_block bb, struct df_insn_info *insn_info,
2730 int flags)
2732 RTX_CODE code = GET_CODE (x);
2733 int i;
2735 switch (code)
2737 case SET:
2738 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2739 break;
2741 case CLOBBER:
2742 flags |= DF_REF_MUST_CLOBBER;
2743 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2744 break;
2746 case COND_EXEC:
2747 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2748 bb, insn_info, DF_REF_CONDITIONAL);
2749 break;
2751 case PARALLEL:
2752 for (i = 0; i < XVECLEN (x, 0); i++)
2753 df_defs_record (collection_rec, XVECEXP (x, 0, i),
2754 bb, insn_info, flags);
2755 break;
2756 default:
2757 /* No DEFs to record in other cases */
2758 break;
2762 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2763 destination of a set or clobber. This has to match the logic in
2764 df_defs_record_1. */
2766 static void
2767 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2769 /* It is legal to have a set destination be a parallel. */
2770 if (GET_CODE (dst) == PARALLEL)
2772 int i;
2773 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2775 rtx temp = XVECEXP (dst, 0, i);
2776 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2777 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2779 return;
2782 if (GET_CODE (dst) == STRICT_LOW_PART)
2783 dst = XEXP (dst, 0);
2785 if (GET_CODE (dst) == ZERO_EXTRACT)
2786 dst = XEXP (dst, 0);
2788 /* At this point if we do not have a reg or a subreg, just return. */
2789 if (REG_P (dst) && HARD_REGISTER_P (dst))
2790 SET_HARD_REG_BIT (*defs, REGNO (dst));
2791 else if (GET_CODE (dst) == SUBREG
2792 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2793 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2796 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2797 has to match the logic in df_defs_record. */
2799 static void
2800 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2802 RTX_CODE code = GET_CODE (x);
2803 int i;
2805 switch (code)
2807 case SET:
2808 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2809 break;
2811 case CLOBBER:
2812 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2813 break;
2815 case COND_EXEC:
2816 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2817 break;
2819 case PARALLEL:
2820 for (i = 0; i < XVECLEN (x, 0); i++)
2821 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2822 break;
2823 default:
2824 /* No DEFs to record in other cases */
2825 break;
2830 /* Process all the registers used in the rtx at address LOC. */
2832 static void
2833 df_uses_record (struct df_collection_rec *collection_rec,
2834 rtx *loc, enum df_ref_type ref_type,
2835 basic_block bb, struct df_insn_info *insn_info,
2836 int flags)
2838 RTX_CODE code;
2839 rtx x;
2841 retry:
2842 x = *loc;
2843 if (!x)
2844 return;
2845 code = GET_CODE (x);
2846 switch (code)
2848 case LABEL_REF:
2849 case SYMBOL_REF:
2850 case CONST:
2851 CASE_CONST_ANY:
2852 case PC:
2853 case CC0:
2854 case ADDR_VEC:
2855 case ADDR_DIFF_VEC:
2856 return;
2858 case CLOBBER:
2859 /* If we are clobbering a MEM, mark any registers inside the address
2860 as being used. */
2861 if (MEM_P (XEXP (x, 0)))
2862 df_uses_record (collection_rec,
2863 &XEXP (XEXP (x, 0), 0),
2864 DF_REF_REG_MEM_STORE,
2865 bb, insn_info,
2866 flags);
2868 /* If we're clobbering a REG then we have a def so ignore. */
2869 return;
2871 case MEM:
2872 df_uses_record (collection_rec,
2873 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2874 bb, insn_info, flags & DF_REF_IN_NOTE);
2875 return;
2877 case SUBREG:
2878 /* While we're here, optimize this case. */
2879 flags |= DF_REF_PARTIAL;
2880 /* In case the SUBREG is not of a REG, do not optimize. */
2881 if (!REG_P (SUBREG_REG (x)))
2883 loc = &SUBREG_REG (x);
2884 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2885 return;
2887 /* ... Fall through ... */
2889 case REG:
2890 df_ref_record (DF_REF_REGULAR, collection_rec,
2891 x, loc, bb, insn_info,
2892 ref_type, flags);
2893 return;
2895 case SIGN_EXTRACT:
2896 case ZERO_EXTRACT:
2898 df_uses_record (collection_rec,
2899 &XEXP (x, 1), ref_type, bb, insn_info, flags);
2900 df_uses_record (collection_rec,
2901 &XEXP (x, 2), ref_type, bb, insn_info, flags);
2903 /* If the parameters to the zero or sign extract are
2904 constants, strip them off and recurse, otherwise there is
2905 no information that we can gain from this operation. */
2906 if (code == ZERO_EXTRACT)
2907 flags |= DF_REF_ZERO_EXTRACT;
2908 else
2909 flags |= DF_REF_SIGN_EXTRACT;
2911 df_uses_record (collection_rec,
2912 &XEXP (x, 0), ref_type, bb, insn_info, flags);
2913 return;
2915 break;
2917 case SET:
2919 rtx dst = SET_DEST (x);
2920 gcc_assert (!(flags & DF_REF_IN_NOTE));
2921 df_uses_record (collection_rec,
2922 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2924 switch (GET_CODE (dst))
2926 case SUBREG:
2927 if (df_read_modify_subreg_p (dst))
2929 df_uses_record (collection_rec, &SUBREG_REG (dst),
2930 DF_REF_REG_USE, bb, insn_info,
2931 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2932 break;
2934 /* Fall through. */
2935 case REG:
2936 case PARALLEL:
2937 case SCRATCH:
2938 case PC:
2939 case CC0:
2940 break;
2941 case MEM:
2942 df_uses_record (collection_rec, &XEXP (dst, 0),
2943 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2944 break;
2945 case STRICT_LOW_PART:
2947 rtx *temp = &XEXP (dst, 0);
2948 /* A strict_low_part uses the whole REG and not just the
2949 SUBREG. */
2950 dst = XEXP (dst, 0);
2951 df_uses_record (collection_rec,
2952 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2953 DF_REF_REG_USE, bb, insn_info,
2954 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2956 break;
2957 case ZERO_EXTRACT:
2959 df_uses_record (collection_rec, &XEXP (dst, 1),
2960 DF_REF_REG_USE, bb, insn_info, flags);
2961 df_uses_record (collection_rec, &XEXP (dst, 2),
2962 DF_REF_REG_USE, bb, insn_info, flags);
2963 if (GET_CODE (XEXP (dst,0)) == MEM)
2964 df_uses_record (collection_rec, &XEXP (dst, 0),
2965 DF_REF_REG_USE, bb, insn_info,
2966 flags);
2967 else
2968 df_uses_record (collection_rec, &XEXP (dst, 0),
2969 DF_REF_REG_USE, bb, insn_info,
2970 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2972 break;
2974 default:
2975 gcc_unreachable ();
2977 return;
2980 case RETURN:
2981 case SIMPLE_RETURN:
2982 break;
2984 case ASM_OPERANDS:
2985 case UNSPEC_VOLATILE:
2986 case TRAP_IF:
2987 case ASM_INPUT:
2989 /* Traditional and volatile asm instructions must be
2990 considered to use and clobber all hard registers, all
2991 pseudo-registers and all of memory. So must TRAP_IF and
2992 UNSPEC_VOLATILE operations.
2994 Consider for instance a volatile asm that changes the fpu
2995 rounding mode. An insn should not be moved across this
2996 even if it only uses pseudo-regs because it might give an
2997 incorrectly rounded result.
2999 However, flow.c's liveness computation did *not* do this,
3000 giving the reasoning as " ?!? Unfortunately, marking all
3001 hard registers as live causes massive problems for the
3002 register allocator and marking all pseudos as live creates
3003 mountains of uninitialized variable warnings."
3005 In order to maintain the status quo with regard to liveness
3006 and uses, we do what flow.c did and just mark any regs we
3007 can find in ASM_OPERANDS as used. In global asm insns are
3008 scanned and regs_asm_clobbered is filled out.
3010 For all ASM_OPERANDS, we must traverse the vector of input
3011 operands. We can not just fall through here since then we
3012 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3013 which do not indicate traditional asms unlike their normal
3014 usage. */
3015 if (code == ASM_OPERANDS)
3017 int j;
3019 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3020 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
3021 DF_REF_REG_USE, bb, insn_info, flags);
3022 return;
3024 break;
3027 case VAR_LOCATION:
3028 df_uses_record (collection_rec,
3029 &PAT_VAR_LOCATION_LOC (x),
3030 DF_REF_REG_USE, bb, insn_info, flags);
3031 return;
3033 case PRE_DEC:
3034 case POST_DEC:
3035 case PRE_INC:
3036 case POST_INC:
3037 case PRE_MODIFY:
3038 case POST_MODIFY:
3039 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3040 /* Catch the def of the register being modified. */
3041 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3042 bb, insn_info,
3043 DF_REF_REG_DEF,
3044 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3046 /* ... Fall through to handle uses ... */
3048 default:
3049 break;
3052 /* Recursively scan the operands of this expression. */
3054 const char *fmt = GET_RTX_FORMAT (code);
3055 int i;
3057 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3059 if (fmt[i] == 'e')
3061 /* Tail recursive case: save a function call level. */
3062 if (i == 0)
3064 loc = &XEXP (x, 0);
3065 goto retry;
3067 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3068 bb, insn_info, flags);
3070 else if (fmt[i] == 'E')
3072 int j;
3073 for (j = 0; j < XVECLEN (x, i); j++)
3074 df_uses_record (collection_rec,
3075 &XVECEXP (x, i, j), ref_type,
3076 bb, insn_info, flags);
3081 return;
3085 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3087 static void
3088 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3090 unsigned int ix;
3091 df_ref ref;
3093 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3095 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3097 df_ref use;
3099 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3100 DF_REF_LOC (ref), DF_REF_BB (ref),
3101 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3102 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3103 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3109 /* Get call's extra defs and uses (track caller-saved registers). */
3111 static void
3112 df_get_call_refs (struct df_collection_rec *collection_rec,
3113 basic_block bb,
3114 struct df_insn_info *insn_info,
3115 int flags)
3117 rtx note;
3118 bool is_sibling_call;
3119 unsigned int i;
3120 HARD_REG_SET defs_generated;
3121 HARD_REG_SET fn_reg_set_usage;
3123 CLEAR_HARD_REG_SET (defs_generated);
3124 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3125 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3126 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3127 regs_invalidated_by_call);
3129 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3131 if (i == STACK_POINTER_REGNUM)
3132 /* The stack ptr is used (honorarily) by a CALL insn. */
3133 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3134 NULL, bb, insn_info, DF_REF_REG_USE,
3135 DF_REF_CALL_STACK_USAGE | flags);
3136 else if (global_regs[i])
3138 /* Calls to const functions cannot access any global registers and
3139 calls to pure functions cannot set them. All other calls may
3140 reference any of the global registers, so they are recorded as
3141 used. */
3142 if (!RTL_CONST_CALL_P (insn_info->insn))
3144 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3145 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3146 if (!RTL_PURE_CALL_P (insn_info->insn))
3147 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3148 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3151 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3152 /* no clobbers for regs that are the result of the call */
3153 && !TEST_HARD_REG_BIT (defs_generated, i)
3154 && (!is_sibling_call
3155 || !bitmap_bit_p (df->exit_block_uses, i)
3156 || refers_to_regno_p (i, crtl->return_rtx)))
3157 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3158 NULL, bb, insn_info, DF_REF_REG_DEF,
3159 DF_REF_MAY_CLOBBER | flags);
3162 /* Record the registers used to pass arguments, and explicitly
3163 noted as clobbered. */
3164 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3165 note = XEXP (note, 1))
3167 if (GET_CODE (XEXP (note, 0)) == USE)
3168 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3169 DF_REF_REG_USE, bb, insn_info, flags);
3170 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3172 if (REG_P (XEXP (XEXP (note, 0), 0)))
3174 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3175 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3176 df_defs_record (collection_rec, XEXP (note, 0), bb,
3177 insn_info, flags);
3179 else
3180 df_uses_record (collection_rec, &XEXP (note, 0),
3181 DF_REF_REG_USE, bb, insn_info, flags);
3185 return;
3188 /* Collect all refs in the INSN. This function is free of any
3189 side-effect - it will create and return a lists of df_ref's in the
3190 COLLECTION_REC without putting those refs into existing ref chains
3191 and reg chains. */
3193 static void
3194 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3195 basic_block bb, struct df_insn_info *insn_info)
3197 rtx note;
3198 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3200 /* Clear out the collection record. */
3201 collection_rec->def_vec.truncate (0);
3202 collection_rec->use_vec.truncate (0);
3203 collection_rec->eq_use_vec.truncate (0);
3204 collection_rec->mw_vec.truncate (0);
3206 /* Process REG_EQUIV/REG_EQUAL notes. */
3207 for (note = REG_NOTES (insn_info->insn); note;
3208 note = XEXP (note, 1))
3210 switch (REG_NOTE_KIND (note))
3212 case REG_EQUIV:
3213 case REG_EQUAL:
3214 df_uses_record (collection_rec,
3215 &XEXP (note, 0), DF_REF_REG_USE,
3216 bb, insn_info, DF_REF_IN_NOTE);
3217 break;
3218 case REG_NON_LOCAL_GOTO:
3219 /* The frame ptr is used by a non-local goto. */
3220 df_ref_record (DF_REF_BASE, collection_rec,
3221 regno_reg_rtx[FRAME_POINTER_REGNUM],
3222 NULL, bb, insn_info,
3223 DF_REF_REG_USE, 0);
3224 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3225 df_ref_record (DF_REF_BASE, collection_rec,
3226 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3227 NULL, bb, insn_info,
3228 DF_REF_REG_USE, 0);
3229 break;
3230 default:
3231 break;
3235 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3236 uses from CALL_INSN_FUNCTION_USAGE. */
3237 if (CALL_P (insn_info->insn))
3238 df_get_call_refs (collection_rec, bb, insn_info,
3239 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3241 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3242 that a qsort on the defs is unnecessary in most cases. */
3243 df_defs_record (collection_rec,
3244 PATTERN (insn_info->insn), bb, insn_info, 0);
3246 /* Record the register uses. */
3247 df_uses_record (collection_rec,
3248 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3250 /* DF_REF_CONDITIONAL needs corresponding USES. */
3251 if (is_cond_exec)
3252 df_get_conditional_uses (collection_rec);
3254 df_canonize_collection_rec (collection_rec);
3257 /* Recompute the luids for the insns in BB. */
3259 void
3260 df_recompute_luids (basic_block bb)
3262 rtx_insn *insn;
3263 int luid = 0;
3265 df_grow_insn_info ();
3267 /* Scan the block an insn at a time from beginning to end. */
3268 FOR_BB_INSNS (bb, insn)
3270 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3271 /* Inserting labels does not always trigger the incremental
3272 rescanning. */
3273 if (!insn_info)
3275 gcc_assert (!INSN_P (insn));
3276 insn_info = df_insn_create_insn_record (insn);
3279 DF_INSN_INFO_LUID (insn_info) = luid;
3280 if (INSN_P (insn))
3281 luid++;
3286 /* Collect all artificial refs at the block level for BB and add them
3287 to COLLECTION_REC. */
3289 static void
3290 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3292 collection_rec->def_vec.truncate (0);
3293 collection_rec->use_vec.truncate (0);
3294 collection_rec->eq_use_vec.truncate (0);
3295 collection_rec->mw_vec.truncate (0);
3297 if (bb->index == ENTRY_BLOCK)
3299 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3300 return;
3302 else if (bb->index == EXIT_BLOCK)
3304 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3305 return;
3308 if (bb_has_eh_pred (bb))
3310 unsigned int i;
3311 /* Mark the registers that will contain data for the handler. */
3312 for (i = 0; ; ++i)
3314 unsigned regno = EH_RETURN_DATA_REGNO (i);
3315 if (regno == INVALID_REGNUM)
3316 break;
3317 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3318 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3322 /* Add the hard_frame_pointer if this block is the target of a
3323 non-local goto. */
3324 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3325 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3326 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3328 /* Add the artificial uses. */
3329 if (bb->index >= NUM_FIXED_BLOCKS)
3331 bitmap_iterator bi;
3332 unsigned int regno;
3333 bitmap au = bb_has_eh_pred (bb)
3334 ? &df->eh_block_artificial_uses
3335 : &df->regular_block_artificial_uses;
3337 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3339 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3340 bb, NULL, DF_REF_REG_USE, 0);
3344 df_canonize_collection_rec (collection_rec);
3348 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3350 void
3351 df_bb_refs_record (int bb_index, bool scan_insns)
3353 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3354 rtx_insn *insn;
3355 int luid = 0;
3357 if (!df)
3358 return;
3360 df_collection_rec collection_rec;
3361 df_grow_bb_info (df_scan);
3362 if (scan_insns)
3363 /* Scan the block an insn at a time from beginning to end. */
3364 FOR_BB_INSNS (bb, insn)
3366 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3367 gcc_assert (!insn_info);
3369 insn_info = df_insn_create_insn_record (insn);
3370 if (INSN_P (insn))
3372 /* Record refs within INSN. */
3373 DF_INSN_INFO_LUID (insn_info) = luid++;
3374 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3375 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3377 DF_INSN_INFO_LUID (insn_info) = luid;
3380 /* Other block level artificial refs */
3381 df_bb_refs_collect (&collection_rec, bb);
3382 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3384 /* Now that the block has been processed, set the block as dirty so
3385 LR and LIVE will get it processed. */
3386 df_set_bb_dirty (bb);
3390 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3391 block. */
3393 static void
3394 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3396 #ifdef EH_USES
3397 unsigned int i;
3398 #endif
3400 bitmap_clear (regular_block_artificial_uses);
3402 if (reload_completed)
3404 if (frame_pointer_needed)
3405 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3407 else
3408 /* Before reload, there are a few registers that must be forced
3409 live everywhere -- which might not already be the case for
3410 blocks within infinite loops. */
3412 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3414 /* Any reference to any pseudo before reload is a potential
3415 reference of the frame pointer. */
3416 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3418 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3419 bitmap_set_bit (regular_block_artificial_uses,
3420 HARD_FRAME_POINTER_REGNUM);
3422 /* Pseudos with argument area equivalences may require
3423 reloading via the argument pointer. */
3424 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3425 && fixed_regs[ARG_POINTER_REGNUM])
3426 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3428 /* Any constant, or pseudo with constant equivalences, may
3429 require reloading from memory using the pic register. */
3430 if (picreg != INVALID_REGNUM
3431 && fixed_regs[picreg])
3432 bitmap_set_bit (regular_block_artificial_uses, picreg);
3434 /* The all-important stack pointer must always be live. */
3435 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3437 #ifdef EH_USES
3438 /* EH_USES registers are used:
3439 1) at all insns that might throw (calls or with -fnon-call-exceptions
3440 trapping insns)
3441 2) in all EH edges
3442 3) to support backtraces and/or debugging, anywhere between their
3443 initialization and where they the saved registers are restored
3444 from them, including the cases where we don't reach the epilogue
3445 (noreturn call or infinite loop). */
3446 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3447 if (EH_USES (i))
3448 bitmap_set_bit (regular_block_artificial_uses, i);
3449 #endif
3453 /* Get the artificial use set for an eh block. */
3455 static void
3456 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3458 bitmap_clear (eh_block_artificial_uses);
3460 /* The following code (down through the arg_pointer setting APPEARS
3461 to be necessary because there is nothing that actually
3462 describes what the exception handling code may actually need
3463 to keep alive. */
3464 if (reload_completed)
3466 if (frame_pointer_needed)
3468 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3469 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3470 bitmap_set_bit (eh_block_artificial_uses,
3471 HARD_FRAME_POINTER_REGNUM);
3473 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3474 && fixed_regs[ARG_POINTER_REGNUM])
3475 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3481 /*----------------------------------------------------------------------------
3482 Specialized hard register scanning functions.
3483 ----------------------------------------------------------------------------*/
3486 /* Mark a register in SET. Hard registers in large modes get all
3487 of their component registers set as well. */
3489 static void
3490 df_mark_reg (rtx reg, void *vset)
3492 bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3496 /* Set the bit for regs that are considered being defined at the entry. */
3498 static void
3499 df_get_entry_block_def_set (bitmap entry_block_defs)
3501 rtx r;
3502 int i;
3504 bitmap_clear (entry_block_defs);
3506 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3508 if (global_regs[i])
3509 bitmap_set_bit (entry_block_defs, i);
3510 if (FUNCTION_ARG_REGNO_P (i))
3511 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3514 /* The always important stack pointer. */
3515 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3517 /* Once the prologue has been generated, all of these registers
3518 should just show up in the first regular block. */
3519 if (targetm.have_prologue () && epilogue_completed)
3521 /* Defs for the callee saved registers are inserted so that the
3522 pushes have some defining location. */
3523 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3524 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3525 bitmap_set_bit (entry_block_defs, i);
3528 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3529 if (r && REG_P (r))
3530 bitmap_set_bit (entry_block_defs, REGNO (r));
3532 /* If the function has an incoming STATIC_CHAIN, it has to show up
3533 in the entry def set. */
3534 r = targetm.calls.static_chain (current_function_decl, true);
3535 if (r && REG_P (r))
3536 bitmap_set_bit (entry_block_defs, REGNO (r));
3538 if ((!reload_completed) || frame_pointer_needed)
3540 /* Any reference to any pseudo before reload is a potential
3541 reference of the frame pointer. */
3542 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3544 /* If they are different, also mark the hard frame pointer as live. */
3545 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3546 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3547 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3550 /* These registers are live everywhere. */
3551 if (!reload_completed)
3553 /* Pseudos with argument area equivalences may require
3554 reloading via the argument pointer. */
3555 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3556 && fixed_regs[ARG_POINTER_REGNUM])
3557 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3559 /* Any constant, or pseudo with constant equivalences, may
3560 require reloading from memory using the pic register. */
3561 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3562 if (picreg != INVALID_REGNUM
3563 && fixed_regs[picreg])
3564 bitmap_set_bit (entry_block_defs, picreg);
3567 #ifdef INCOMING_RETURN_ADDR_RTX
3568 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3569 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3570 #endif
3572 targetm.extra_live_on_entry (entry_block_defs);
3576 /* Return the (conservative) set of hard registers that are defined on
3577 entry to the function.
3578 It uses df->entry_block_defs to determine which register
3579 reference to include. */
3581 static void
3582 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3583 bitmap entry_block_defs)
3585 unsigned int i;
3586 bitmap_iterator bi;
3588 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3590 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3591 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3594 df_canonize_collection_rec (collection_rec);
3598 /* Record the (conservative) set of hard registers that are defined on
3599 entry to the function. */
3601 static void
3602 df_record_entry_block_defs (bitmap entry_block_defs)
3604 struct df_collection_rec collection_rec;
3605 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3607 /* Process bb_refs chain */
3608 df_refs_add_to_chains (&collection_rec,
3609 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3610 NULL,
3611 copy_defs);
3615 /* Update the defs in the entry block. */
3617 void
3618 df_update_entry_block_defs (void)
3620 bitmap_head refs;
3621 bool changed = false;
3623 bitmap_initialize (&refs, &df_bitmap_obstack);
3624 df_get_entry_block_def_set (&refs);
3625 if (df->entry_block_defs)
3627 if (!bitmap_equal_p (df->entry_block_defs, &refs))
3629 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3630 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3631 df_ref_chain_delete (bb_info->artificial_defs);
3632 bb_info->artificial_defs = NULL;
3633 changed = true;
3636 else
3638 struct df_scan_problem_data *problem_data
3639 = (struct df_scan_problem_data *) df_scan->problem_data;
3640 gcc_unreachable ();
3641 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3642 changed = true;
3645 if (changed)
3647 df_record_entry_block_defs (&refs);
3648 bitmap_copy (df->entry_block_defs, &refs);
3649 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3651 bitmap_clear (&refs);
3655 /* Set the bit for regs that are considered being used at the exit. */
3657 static void
3658 df_get_exit_block_use_set (bitmap exit_block_uses)
3660 unsigned int i;
3661 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3663 bitmap_clear (exit_block_uses);
3665 /* Stack pointer is always live at the exit. */
3666 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3668 /* Mark the frame pointer if needed at the end of the function.
3669 If we end up eliminating it, it will be removed from the live
3670 list of each basic block by reload. */
3672 if ((!reload_completed) || frame_pointer_needed)
3674 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3676 /* If they are different, also mark the hard frame pointer as live. */
3677 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3678 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3679 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3682 /* Many architectures have a GP register even without flag_pic.
3683 Assume the pic register is not in use, or will be handled by
3684 other means, if it is not fixed. */
3685 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3686 && picreg != INVALID_REGNUM
3687 && fixed_regs[picreg])
3688 bitmap_set_bit (exit_block_uses, picreg);
3690 /* Mark all global registers, and all registers used by the
3691 epilogue as being live at the end of the function since they
3692 may be referenced by our caller. */
3693 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3694 if (global_regs[i] || EPILOGUE_USES (i))
3695 bitmap_set_bit (exit_block_uses, i);
3697 if (targetm.have_epilogue () && epilogue_completed)
3699 /* Mark all call-saved registers that we actually used. */
3700 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3701 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3702 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3703 bitmap_set_bit (exit_block_uses, i);
3706 /* Mark the registers that will contain data for the handler. */
3707 if (reload_completed && crtl->calls_eh_return)
3708 for (i = 0; ; ++i)
3710 unsigned regno = EH_RETURN_DATA_REGNO (i);
3711 if (regno == INVALID_REGNUM)
3712 break;
3713 bitmap_set_bit (exit_block_uses, regno);
3716 #ifdef EH_RETURN_STACKADJ_RTX
3717 if ((!targetm.have_epilogue () || ! epilogue_completed)
3718 && crtl->calls_eh_return)
3720 rtx tmp = EH_RETURN_STACKADJ_RTX;
3721 if (tmp && REG_P (tmp))
3722 df_mark_reg (tmp, exit_block_uses);
3724 #endif
3726 #ifdef EH_RETURN_HANDLER_RTX
3727 if ((!targetm.have_epilogue () || ! epilogue_completed)
3728 && crtl->calls_eh_return)
3730 rtx tmp = EH_RETURN_HANDLER_RTX;
3731 if (tmp && REG_P (tmp))
3732 df_mark_reg (tmp, exit_block_uses);
3734 #endif
3736 /* Mark function return value. */
3737 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3741 /* Return the refs of hard registers that are used in the exit block.
3742 It uses df->exit_block_uses to determine register to include. */
3744 static void
3745 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3747 unsigned int i;
3748 bitmap_iterator bi;
3750 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3751 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3752 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3754 /* It is deliberate that this is not put in the exit block uses but
3755 I do not know why. */
3756 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3757 && reload_completed
3758 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3759 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3760 && fixed_regs[ARG_POINTER_REGNUM])
3761 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3762 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3764 df_canonize_collection_rec (collection_rec);
3768 /* Record the set of hard registers that are used in the exit block.
3769 It uses df->exit_block_uses to determine which bit to include. */
3771 static void
3772 df_record_exit_block_uses (bitmap exit_block_uses)
3774 struct df_collection_rec collection_rec;
3775 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3777 /* Process bb_refs chain */
3778 df_refs_add_to_chains (&collection_rec,
3779 BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3780 NULL,
3781 copy_uses);
3785 /* Update the uses in the exit block. */
3787 void
3788 df_update_exit_block_uses (void)
3790 bitmap_head refs;
3791 bool changed = false;
3793 bitmap_initialize (&refs, &df_bitmap_obstack);
3794 df_get_exit_block_use_set (&refs);
3795 if (df->exit_block_uses)
3797 if (!bitmap_equal_p (df->exit_block_uses, &refs))
3799 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3800 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3801 df_ref_chain_delete (bb_info->artificial_uses);
3802 bb_info->artificial_uses = NULL;
3803 changed = true;
3806 else
3808 struct df_scan_problem_data *problem_data
3809 = (struct df_scan_problem_data *) df_scan->problem_data;
3810 gcc_unreachable ();
3811 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3812 changed = true;
3815 if (changed)
3817 df_record_exit_block_uses (&refs);
3818 bitmap_copy (df->exit_block_uses,& refs);
3819 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3821 bitmap_clear (&refs);
3824 static bool initialized = false;
3827 /* Initialize some platform specific structures. */
3829 void
3830 df_hard_reg_init (void)
3832 #ifdef ELIMINABLE_REGS
3833 int i;
3834 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3835 #endif
3836 if (initialized)
3837 return;
3839 /* Record which registers will be eliminated. We use this in
3840 mark_used_regs. */
3841 CLEAR_HARD_REG_SET (elim_reg_set);
3843 #ifdef ELIMINABLE_REGS
3844 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3845 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3846 #else
3847 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3848 #endif
3850 initialized = true;
3854 /* Recompute the parts of scanning that are based on regs_ever_live
3855 because something changed in that array. */
3857 void
3858 df_update_entry_exit_and_calls (void)
3860 basic_block bb;
3862 df_update_entry_block_defs ();
3863 df_update_exit_block_uses ();
3865 /* The call insns need to be rescanned because there may be changes
3866 in the set of registers clobbered across the call. */
3867 FOR_EACH_BB_FN (bb, cfun)
3869 rtx_insn *insn;
3870 FOR_BB_INSNS (bb, insn)
3872 if (INSN_P (insn) && CALL_P (insn))
3873 df_insn_rescan (insn);
3879 /* Return true if hard REG is actually used in the some instruction.
3880 There are a fair number of conditions that affect the setting of
3881 this array. See the comment in df.h for df->hard_regs_live_count
3882 for the conditions that this array is set. */
3884 bool
3885 df_hard_reg_used_p (unsigned int reg)
3887 return df->hard_regs_live_count[reg] != 0;
3891 /* A count of the number of times REG is actually used in the some
3892 instruction. There are a fair number of conditions that affect the
3893 setting of this array. See the comment in df.h for
3894 df->hard_regs_live_count for the conditions that this array is
3895 set. */
3898 unsigned int
3899 df_hard_reg_used_count (unsigned int reg)
3901 return df->hard_regs_live_count[reg];
3905 /* Get the value of regs_ever_live[REGNO]. */
3907 bool
3908 df_regs_ever_live_p (unsigned int regno)
3910 return regs_ever_live[regno];
3914 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3915 to change, schedule that change for the next update. */
3917 void
3918 df_set_regs_ever_live (unsigned int regno, bool value)
3920 if (regs_ever_live[regno] == value)
3921 return;
3923 regs_ever_live[regno] = value;
3924 if (df)
3925 df->redo_entry_and_exit = true;
3929 /* Compute "regs_ever_live" information from the underlying df
3930 information. Set the vector to all false if RESET. */
3932 void
3933 df_compute_regs_ever_live (bool reset)
3935 unsigned int i;
3936 bool changed = df->redo_entry_and_exit;
3938 if (reset)
3939 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3941 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3942 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3944 regs_ever_live[i] = true;
3945 changed = true;
3947 if (changed)
3948 df_update_entry_exit_and_calls ();
3949 df->redo_entry_and_exit = false;
3953 /*----------------------------------------------------------------------------
3954 Dataflow ref information verification functions.
3956 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3957 df_reg_chain_verify_unmarked (refs)
3958 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3959 df_mws_verify (mw*, mw*, bool)
3960 df_insn_refs_verify (collection_rec, bb, insn, bool)
3961 df_bb_refs_verify (bb, refs, bool)
3962 df_bb_verify (bb)
3963 df_exit_block_bitmap_verify (bool)
3964 df_entry_block_bitmap_verify (bool)
3965 df_scan_verify ()
3966 ----------------------------------------------------------------------------*/
3969 /* Mark all refs in the reg chain. Verify that all of the registers
3970 are in the correct chain. */
3972 static unsigned int
3973 df_reg_chain_mark (df_ref refs, unsigned int regno,
3974 bool is_def, bool is_eq_use)
3976 unsigned int count = 0;
3977 df_ref ref;
3978 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3980 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3982 /* If there are no def-use or use-def chains, make sure that all
3983 of the chains are clear. */
3984 if (!df_chain)
3985 gcc_assert (!DF_REF_CHAIN (ref));
3987 /* Check to make sure the ref is in the correct chain. */
3988 gcc_assert (DF_REF_REGNO (ref) == regno);
3989 if (is_def)
3990 gcc_assert (DF_REF_REG_DEF_P (ref));
3991 else
3992 gcc_assert (!DF_REF_REG_DEF_P (ref));
3994 if (is_eq_use)
3995 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
3996 else
3997 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
3999 if (DF_REF_NEXT_REG (ref))
4000 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
4001 count++;
4002 DF_REF_REG_MARK (ref);
4004 return count;
4008 /* Verify that all of the registers in the chain are unmarked. */
4010 static void
4011 df_reg_chain_verify_unmarked (df_ref refs)
4013 df_ref ref;
4014 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4015 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4019 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4021 static bool
4022 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4023 bool abort_if_fail)
4025 unsigned int ix;
4026 df_ref new_ref;
4028 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4030 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4032 if (abort_if_fail)
4033 gcc_assert (0);
4034 else
4035 return false;
4038 /* Abort if fail is called from the function level verifier. If
4039 that is the context, mark this reg as being seem. */
4040 if (abort_if_fail)
4042 gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4043 DF_REF_REG_UNMARK (old_rec);
4046 old_rec = DF_REF_NEXT_LOC (old_rec);
4049 if (abort_if_fail)
4050 gcc_assert (old_rec == NULL);
4051 else
4052 return old_rec == NULL;
4053 return false;
4057 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4059 static bool
4060 df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec,
4061 struct df_mw_hardreg *old_rec,
4062 bool abort_if_fail)
4064 unsigned int ix;
4065 struct df_mw_hardreg *new_reg;
4067 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4069 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4071 if (abort_if_fail)
4072 gcc_assert (0);
4073 else
4074 return false;
4076 old_rec = DF_MWS_NEXT (old_rec);
4079 if (abort_if_fail)
4080 gcc_assert (old_rec == NULL);
4081 else
4082 return old_rec == NULL;
4083 return false;
4087 /* Return true if the existing insn refs information is complete and
4088 correct. Otherwise (i.e. if there's any missing or extra refs),
4089 return the correct df_ref chain in REFS_RETURN.
4091 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4092 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4093 verification mode instead of the whole function, so unmark
4094 everything.
4096 If ABORT_IF_FAIL is set, this function never returns false. */
4098 static bool
4099 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4100 basic_block bb,
4101 rtx_insn *insn,
4102 bool abort_if_fail)
4104 bool ret1, ret2, ret3, ret4;
4105 unsigned int uid = INSN_UID (insn);
4106 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4108 df_insn_refs_collect (collection_rec, bb, insn_info);
4110 /* Unfortunately we cannot opt out early if one of these is not
4111 right because the marks will not get cleared. */
4112 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4113 abort_if_fail);
4114 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4115 abort_if_fail);
4116 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4117 abort_if_fail);
4118 ret4 = df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4119 abort_if_fail);
4120 return (ret1 && ret2 && ret3 && ret4);
4124 /* Return true if all refs in the basic block are correct and complete.
4125 Due to df_ref_chain_verify, it will cause all refs
4126 that are verified to have DF_REF_MARK bit set. */
4128 static bool
4129 df_bb_verify (basic_block bb)
4131 rtx_insn *insn;
4132 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4133 struct df_collection_rec collection_rec;
4135 gcc_assert (bb_info);
4137 /* Scan the block, one insn at a time, from beginning to end. */
4138 FOR_BB_INSNS_REVERSE (bb, insn)
4140 if (!INSN_P (insn))
4141 continue;
4142 df_insn_refs_verify (&collection_rec, bb, insn, true);
4143 df_free_collection_rec (&collection_rec);
4146 /* Do the artificial defs and uses. */
4147 df_bb_refs_collect (&collection_rec, bb);
4148 df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4149 df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4150 df_free_collection_rec (&collection_rec);
4152 return true;
4156 /* Returns true if the entry block has correct and complete df_ref set.
4157 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4159 static bool
4160 df_entry_block_bitmap_verify (bool abort_if_fail)
4162 bitmap_head entry_block_defs;
4163 bool is_eq;
4165 bitmap_initialize (&entry_block_defs, &df_bitmap_obstack);
4166 df_get_entry_block_def_set (&entry_block_defs);
4168 is_eq = bitmap_equal_p (&entry_block_defs, df->entry_block_defs);
4170 if (!is_eq && abort_if_fail)
4172 fprintf (stderr, "entry_block_defs = ");
4173 df_print_regset (stderr, &entry_block_defs);
4174 fprintf (stderr, "df->entry_block_defs = ");
4175 df_print_regset (stderr, df->entry_block_defs);
4176 gcc_assert (0);
4179 bitmap_clear (&entry_block_defs);
4181 return is_eq;
4185 /* Returns true if the exit block has correct and complete df_ref set.
4186 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4188 static bool
4189 df_exit_block_bitmap_verify (bool abort_if_fail)
4191 bitmap_head exit_block_uses;
4192 bool is_eq;
4194 bitmap_initialize (&exit_block_uses, &df_bitmap_obstack);
4195 df_get_exit_block_use_set (&exit_block_uses);
4197 is_eq = bitmap_equal_p (&exit_block_uses, df->exit_block_uses);
4199 if (!is_eq && abort_if_fail)
4201 fprintf (stderr, "exit_block_uses = ");
4202 df_print_regset (stderr, &exit_block_uses);
4203 fprintf (stderr, "df->exit_block_uses = ");
4204 df_print_regset (stderr, df->exit_block_uses);
4205 gcc_assert (0);
4208 bitmap_clear (&exit_block_uses);
4210 return is_eq;
4214 /* Return true if df_ref information for all insns in all blocks are
4215 correct and complete. */
4217 void
4218 df_scan_verify (void)
4220 unsigned int i;
4221 basic_block bb;
4222 bitmap_head regular_block_artificial_uses;
4223 bitmap_head eh_block_artificial_uses;
4225 if (!df)
4226 return;
4228 /* Verification is a 4 step process. */
4230 /* (1) All of the refs are marked by going through the reg chains. */
4231 for (i = 0; i < DF_REG_SIZE (df); i++)
4233 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4234 == DF_REG_DEF_COUNT (i));
4235 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4236 == DF_REG_USE_COUNT (i));
4237 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4238 == DF_REG_EQ_USE_COUNT (i));
4241 /* (2) There are various bitmaps whose value may change over the
4242 course of the compilation. This step recomputes them to make
4243 sure that they have not slipped out of date. */
4244 bitmap_initialize (&regular_block_artificial_uses, &df_bitmap_obstack);
4245 bitmap_initialize (&eh_block_artificial_uses, &df_bitmap_obstack);
4247 df_get_regular_block_artificial_uses (&regular_block_artificial_uses);
4248 df_get_eh_block_artificial_uses (&eh_block_artificial_uses);
4250 bitmap_ior_into (&eh_block_artificial_uses,
4251 &regular_block_artificial_uses);
4253 /* Check artificial_uses bitmaps didn't change. */
4254 gcc_assert (bitmap_equal_p (&regular_block_artificial_uses,
4255 &df->regular_block_artificial_uses));
4256 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses,
4257 &df->eh_block_artificial_uses));
4259 bitmap_clear (&regular_block_artificial_uses);
4260 bitmap_clear (&eh_block_artificial_uses);
4262 /* Verify entry block and exit block. These only verify the bitmaps,
4263 the refs are verified in df_bb_verify. */
4264 df_entry_block_bitmap_verify (true);
4265 df_exit_block_bitmap_verify (true);
4267 /* (3) All of the insns in all of the blocks are traversed and the
4268 marks are cleared both in the artificial refs attached to the
4269 blocks and the real refs inside the insns. It is a failure to
4270 clear a mark that has not been set as this means that the ref in
4271 the block or insn was not in the reg chain. */
4273 FOR_ALL_BB_FN (bb, cfun)
4274 df_bb_verify (bb);
4276 /* (4) See if all reg chains are traversed a second time. This time
4277 a check is made that the marks are clear. A set mark would be a
4278 from a reg that is not in any insn or basic block. */
4280 for (i = 0; i < DF_REG_SIZE (df); i++)
4282 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4283 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4284 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));