don't compare ARG_FRAME_POINTER_REGNUM and FRAME_POINTER_REGNUM with the preprocessor
[official-gcc.git] / gcc / df-scan.c
blobe32eaf5f0b15d75dce28ba06682a09e4d571f46e
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 "hashtab.h"
33 #include "hash-set.h"
34 #include "machmode.h"
35 #include "vec.h"
36 #include "double-int.h"
37 #include "input.h"
38 #include "alias.h"
39 #include "symtab.h"
40 #include "wide-int.h"
41 #include "inchash.h"
42 #include "hard-reg-set.h"
43 #include "input.h"
44 #include "function.h"
45 #include "regs.h"
46 #include "alloc-pool.h"
47 #include "flags.h"
48 #include "predict.h"
49 #include "dominance.h"
50 #include "cfg.h"
51 #include "basic-block.h"
52 #include "sbitmap.h"
53 #include "bitmap.h"
54 #include "dumpfile.h"
55 #include "tree.h"
56 #include "target.h"
57 #include "target-def.h"
58 #include "df.h"
59 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
62 typedef struct df_mw_hardreg *df_mw_hardreg_ptr;
65 #ifndef HAVE_prologue
66 #define HAVE_prologue 0
67 #endif
68 #ifndef HAVE_sibcall_epilogue
69 #define HAVE_sibcall_epilogue 0
70 #endif
72 /* The set of hard registers in eliminables[i].from. */
74 static HARD_REG_SET elim_reg_set;
76 /* Initialize ur_in and ur_out as if all hard registers were partially
77 available. */
79 struct df_collection_rec
81 auto_vec<df_ref, 128> def_vec;
82 auto_vec<df_ref, 32> use_vec;
83 auto_vec<df_ref, 32> eq_use_vec;
84 auto_vec<df_mw_hardreg_ptr, 32> mw_vec;
87 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
88 rtx, rtx *,
89 basic_block, struct df_insn_info *,
90 enum df_ref_type, int ref_flags);
91 static void df_def_record_1 (struct df_collection_rec *, rtx *,
92 basic_block, struct df_insn_info *,
93 int ref_flags);
94 static void df_defs_record (struct df_collection_rec *, rtx,
95 basic_block, struct df_insn_info *,
96 int ref_flags);
97 static void df_uses_record (struct df_collection_rec *,
98 rtx *, enum df_ref_type,
99 basic_block, struct df_insn_info *,
100 int ref_flags);
102 static void df_install_ref_incremental (df_ref);
103 static void df_insn_refs_collect (struct df_collection_rec*,
104 basic_block, struct df_insn_info *);
105 static void df_canonize_collection_rec (struct df_collection_rec *);
107 static void df_get_regular_block_artificial_uses (bitmap);
108 static void df_get_eh_block_artificial_uses (bitmap);
110 static void df_record_entry_block_defs (bitmap);
111 static void df_record_exit_block_uses (bitmap);
112 static void df_get_exit_block_use_set (bitmap);
113 static void df_get_entry_block_def_set (bitmap);
114 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
115 static void df_ref_chain_delete_du_chain (df_ref);
116 static void df_ref_chain_delete (df_ref);
118 static void df_refs_add_to_chains (struct df_collection_rec *,
119 basic_block, rtx_insn *, unsigned int);
121 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block,
122 rtx_insn *, bool);
123 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
124 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
125 static void df_install_ref (df_ref, struct df_reg_info *,
126 struct df_ref_info *, bool);
128 static int df_ref_compare (df_ref, df_ref);
129 static int df_ref_ptr_compare (const void *, const void *);
130 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
131 static int df_mw_ptr_compare (const void *, const void *);
133 static void df_insn_info_delete (unsigned int);
135 /* Indexed by hardware reg number, is true if that register is ever
136 used in the current function.
138 In df-scan.c, this is set up to record the hard regs used
139 explicitly. Reload adds in the hard regs used for holding pseudo
140 regs. Final uses it to generate the code in the function prologue
141 and epilogue to save and restore registers as needed. */
143 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
145 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
146 static const unsigned int copy_defs = 0x1;
147 static const unsigned int copy_uses = 0x2;
148 static const unsigned int copy_eq_uses = 0x4;
149 static const unsigned int copy_mw = 0x8;
150 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
151 | copy_mw;
153 /*----------------------------------------------------------------------------
154 SCANNING DATAFLOW PROBLEM
156 There are several ways in which scanning looks just like the other
157 dataflow problems. It shares the all the mechanisms for local info
158 as well as basic block info. Where it differs is when and how often
159 it gets run. It also has no need for the iterative solver.
160 ----------------------------------------------------------------------------*/
162 /* Problem data for the scanning dataflow function. */
163 struct df_scan_problem_data
165 alloc_pool ref_base_pool;
166 alloc_pool ref_artificial_pool;
167 alloc_pool ref_regular_pool;
168 alloc_pool insn_pool;
169 alloc_pool reg_pool;
170 alloc_pool mw_reg_pool;
171 bitmap_obstack reg_bitmaps;
172 bitmap_obstack insn_bitmaps;
175 typedef struct df_scan_bb_info *df_scan_bb_info_t;
178 /* Internal function to shut down the scanning problem. */
179 static void
180 df_scan_free_internal (void)
182 struct df_scan_problem_data *problem_data
183 = (struct df_scan_problem_data *) df_scan->problem_data;
185 free (df->def_info.refs);
186 free (df->def_info.begin);
187 free (df->def_info.count);
188 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
190 free (df->use_info.refs);
191 free (df->use_info.begin);
192 free (df->use_info.count);
193 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
195 free (df->def_regs);
196 df->def_regs = NULL;
197 free (df->use_regs);
198 df->use_regs = NULL;
199 free (df->eq_use_regs);
200 df->eq_use_regs = NULL;
201 df->regs_size = 0;
202 DF_REG_SIZE (df) = 0;
204 free (df->insns);
205 df->insns = NULL;
206 DF_INSN_SIZE () = 0;
208 free (df_scan->block_info);
209 df_scan->block_info = NULL;
210 df_scan->block_info_size = 0;
212 bitmap_clear (&df->hardware_regs_used);
213 bitmap_clear (&df->regular_block_artificial_uses);
214 bitmap_clear (&df->eh_block_artificial_uses);
215 BITMAP_FREE (df->entry_block_defs);
216 BITMAP_FREE (df->exit_block_uses);
217 bitmap_clear (&df->insns_to_delete);
218 bitmap_clear (&df->insns_to_rescan);
219 bitmap_clear (&df->insns_to_notes_rescan);
221 free_alloc_pool (problem_data->ref_base_pool);
222 free_alloc_pool (problem_data->ref_artificial_pool);
223 free_alloc_pool (problem_data->ref_regular_pool);
224 free_alloc_pool (problem_data->insn_pool);
225 free_alloc_pool (problem_data->reg_pool);
226 free_alloc_pool (problem_data->mw_reg_pool);
227 bitmap_obstack_release (&problem_data->reg_bitmaps);
228 bitmap_obstack_release (&problem_data->insn_bitmaps);
229 free (df_scan->problem_data);
233 /* Free basic block info. */
235 static void
236 df_scan_free_bb_info (basic_block bb, void *vbb_info)
238 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
239 unsigned int bb_index = bb->index;
240 rtx_insn *insn;
242 FOR_BB_INSNS (bb, insn)
243 if (INSN_P (insn))
244 df_insn_info_delete (INSN_UID (insn));
246 if (bb_index < df_scan->block_info_size)
247 bb_info = df_scan_get_bb_info (bb_index);
249 /* Get rid of any artificial uses or defs. */
250 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
251 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
252 df_ref_chain_delete (bb_info->artificial_defs);
253 df_ref_chain_delete (bb_info->artificial_uses);
254 bb_info->artificial_defs = NULL;
255 bb_info->artificial_uses = NULL;
259 /* Allocate the problem data for the scanning problem. This should be
260 called when the problem is created or when the entire function is to
261 be rescanned. */
262 void
263 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
265 struct df_scan_problem_data *problem_data;
266 unsigned int insn_num = get_max_uid () + 1;
267 unsigned int block_size = 512;
268 basic_block bb;
270 /* Given the number of pools, this is really faster than tearing
271 everything apart. */
272 if (df_scan->problem_data)
273 df_scan_free_internal ();
275 problem_data = XNEW (struct df_scan_problem_data);
276 df_scan->problem_data = problem_data;
277 df_scan->computed = true;
279 problem_data->ref_base_pool
280 = create_alloc_pool ("df_scan ref base",
281 sizeof (struct df_base_ref), block_size);
282 problem_data->ref_artificial_pool
283 = create_alloc_pool ("df_scan ref artificial",
284 sizeof (struct df_artificial_ref), block_size);
285 problem_data->ref_regular_pool
286 = create_alloc_pool ("df_scan ref regular",
287 sizeof (struct df_regular_ref), block_size);
288 problem_data->insn_pool
289 = create_alloc_pool ("df_scan insn",
290 sizeof (struct df_insn_info), block_size);
291 problem_data->reg_pool
292 = create_alloc_pool ("df_scan reg",
293 sizeof (struct df_reg_info), block_size);
294 problem_data->mw_reg_pool
295 = create_alloc_pool ("df_scan mw_reg",
296 sizeof (struct df_mw_hardreg), block_size / 16);
298 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
299 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
301 insn_num += insn_num / 4;
302 df_grow_reg_info ();
304 df_grow_insn_info ();
305 df_grow_bb_info (df_scan);
307 FOR_ALL_BB_FN (bb, cfun)
309 unsigned int bb_index = bb->index;
310 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
311 bb_info->artificial_defs = NULL;
312 bb_info->artificial_uses = NULL;
315 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
316 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
317 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
318 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
319 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
320 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
321 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
322 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
323 df_scan->optional_p = false;
327 /* Free all of the data associated with the scan problem. */
329 static void
330 df_scan_free (void)
332 if (df_scan->problem_data)
333 df_scan_free_internal ();
335 if (df->blocks_to_analyze)
337 BITMAP_FREE (df->blocks_to_analyze);
338 df->blocks_to_analyze = NULL;
341 free (df_scan);
344 /* Dump the preamble for DF_SCAN dump. */
345 static void
346 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
348 int i;
349 int dcount = 0;
350 int ucount = 0;
351 int ecount = 0;
352 int icount = 0;
353 int ccount = 0;
354 basic_block bb;
355 rtx_insn *insn;
357 fprintf (file, ";; invalidated by call \t");
358 df_print_regset (file, regs_invalidated_by_call_regset);
359 fprintf (file, ";; hardware regs used \t");
360 df_print_regset (file, &df->hardware_regs_used);
361 fprintf (file, ";; regular block artificial uses \t");
362 df_print_regset (file, &df->regular_block_artificial_uses);
363 fprintf (file, ";; eh block artificial uses \t");
364 df_print_regset (file, &df->eh_block_artificial_uses);
365 fprintf (file, ";; entry block defs \t");
366 df_print_regset (file, df->entry_block_defs);
367 fprintf (file, ";; exit block uses \t");
368 df_print_regset (file, df->exit_block_uses);
369 fprintf (file, ";; regs ever live \t");
370 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
371 if (df_regs_ever_live_p (i))
372 fprintf (file, " %d[%s]", i, reg_names[i]);
373 fprintf (file, "\n;; ref usage \t");
375 for (i = 0; i < (int)df->regs_inited; i++)
376 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
378 const char * sep = "";
380 fprintf (file, "r%d={", i);
381 if (DF_REG_DEF_COUNT (i))
383 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
384 sep = ",";
385 dcount += DF_REG_DEF_COUNT (i);
387 if (DF_REG_USE_COUNT (i))
389 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
390 sep = ",";
391 ucount += DF_REG_USE_COUNT (i);
393 if (DF_REG_EQ_USE_COUNT (i))
395 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
396 ecount += DF_REG_EQ_USE_COUNT (i);
398 fprintf (file, "} ");
401 FOR_EACH_BB_FN (bb, cfun)
402 FOR_BB_INSNS (bb, insn)
403 if (INSN_P (insn))
405 if (CALL_P (insn))
406 ccount++;
407 else
408 icount++;
411 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
412 " in %d{%d regular + %d call} insns.\n",
413 dcount + ucount + ecount, dcount, ucount, ecount,
414 icount + ccount, icount, ccount);
417 /* Dump the bb_info for a given basic block. */
418 static void
419 df_scan_start_block (basic_block bb, FILE *file)
421 struct df_scan_bb_info *bb_info
422 = df_scan_get_bb_info (bb->index);
424 if (bb_info)
426 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
427 df_refs_chain_dump (bb_info->artificial_defs, true, file);
428 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
429 df_refs_chain_dump (bb_info->artificial_uses, true, file);
430 fprintf (file, "\n");
432 #if 0
434 rtx_insn *insn;
435 FOR_BB_INSNS (bb, insn)
436 if (INSN_P (insn))
437 df_insn_debug (insn, false, file);
439 #endif
442 static struct df_problem problem_SCAN =
444 DF_SCAN, /* Problem id. */
445 DF_NONE, /* Direction. */
446 df_scan_alloc, /* Allocate the problem specific data. */
447 NULL, /* Reset global information. */
448 df_scan_free_bb_info, /* Free basic block info. */
449 NULL, /* Local compute function. */
450 NULL, /* Init the solution specific data. */
451 NULL, /* Iterative solver. */
452 NULL, /* Confluence operator 0. */
453 NULL, /* Confluence operator n. */
454 NULL, /* Transfer function. */
455 NULL, /* Finalize function. */
456 df_scan_free, /* Free all of the problem information. */
457 NULL, /* Remove this problem from the stack of dataflow problems. */
458 df_scan_start_dump, /* Debugging. */
459 df_scan_start_block, /* Debugging start block. */
460 NULL, /* Debugging end block. */
461 NULL, /* Debugging start insn. */
462 NULL, /* Debugging end insn. */
463 NULL, /* Incremental solution verify start. */
464 NULL, /* Incremental solution verify end. */
465 NULL, /* Dependent problem. */
466 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
467 TV_DF_SCAN, /* Timing variable. */
468 false /* Reset blocks on dropping out of blocks_to_analyze. */
472 /* Create a new DATAFLOW instance and add it to an existing instance
473 of DF. The returned structure is what is used to get at the
474 solution. */
476 void
477 df_scan_add_problem (void)
479 df_add_problem (&problem_SCAN);
483 /*----------------------------------------------------------------------------
484 Storage Allocation Utilities
485 ----------------------------------------------------------------------------*/
488 /* First, grow the reg_info information. If the current size is less than
489 the number of pseudos, grow to 25% more than the number of
490 pseudos.
492 Second, assure that all of the slots up to max_reg_num have been
493 filled with reg_info structures. */
495 void
496 df_grow_reg_info (void)
498 unsigned int max_reg = max_reg_num ();
499 unsigned int new_size = max_reg;
500 struct df_scan_problem_data *problem_data
501 = (struct df_scan_problem_data *) df_scan->problem_data;
502 unsigned int i;
504 if (df->regs_size < new_size)
506 new_size += new_size / 4;
507 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
508 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
509 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
510 new_size);
511 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
512 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
513 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
514 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
515 df->regs_size = new_size;
518 for (i = df->regs_inited; i < max_reg; i++)
520 struct df_reg_info *reg_info;
522 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
523 memset (reg_info, 0, sizeof (struct df_reg_info));
524 df->def_regs[i] = reg_info;
525 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
526 memset (reg_info, 0, sizeof (struct df_reg_info));
527 df->use_regs[i] = reg_info;
528 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
529 memset (reg_info, 0, sizeof (struct df_reg_info));
530 df->eq_use_regs[i] = reg_info;
531 df->def_info.begin[i] = 0;
532 df->def_info.count[i] = 0;
533 df->use_info.begin[i] = 0;
534 df->use_info.count[i] = 0;
537 df->regs_inited = max_reg;
541 /* Grow the ref information. */
543 static void
544 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
546 if (ref_info->refs_size < new_size)
548 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
549 memset (ref_info->refs + ref_info->refs_size, 0,
550 (new_size - ref_info->refs_size) *sizeof (df_ref));
551 ref_info->refs_size = new_size;
556 /* Check and grow the ref information if necessary. This routine
557 guarantees total_size + BITMAP_ADDEND amount of entries in refs
558 array. It updates ref_info->refs_size only and does not change
559 ref_info->total_size. */
561 static void
562 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
563 unsigned bitmap_addend)
565 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
567 int new_size = ref_info->total_size + bitmap_addend;
568 new_size += ref_info->total_size / 4;
569 df_grow_ref_info (ref_info, new_size);
574 /* Grow the ref information. If the current size is less than the
575 number of instructions, grow to 25% more than the number of
576 instructions. */
578 void
579 df_grow_insn_info (void)
581 unsigned int new_size = get_max_uid () + 1;
582 if (DF_INSN_SIZE () < new_size)
584 new_size += new_size / 4;
585 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
586 memset (df->insns + df->insns_size, 0,
587 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
588 DF_INSN_SIZE () = new_size;
595 /*----------------------------------------------------------------------------
596 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
597 ----------------------------------------------------------------------------*/
599 /* Rescan all of the block_to_analyze or all of the blocks in the
600 function if df_set_blocks if blocks_to_analyze is NULL; */
602 void
603 df_scan_blocks (void)
605 basic_block bb;
607 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
608 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
610 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
611 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
613 bitmap_ior_into (&df->eh_block_artificial_uses,
614 &df->regular_block_artificial_uses);
616 /* ENTRY and EXIT blocks have special defs/uses. */
617 df_get_entry_block_def_set (df->entry_block_defs);
618 df_record_entry_block_defs (df->entry_block_defs);
619 df_get_exit_block_use_set (df->exit_block_uses);
620 df_record_exit_block_uses (df->exit_block_uses);
621 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
622 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
624 /* Regular blocks */
625 FOR_EACH_BB_FN (bb, cfun)
627 unsigned int bb_index = bb->index;
628 df_bb_refs_record (bb_index, true);
632 /* Create new refs under address LOC within INSN. This function is
633 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
634 depending on whether LOC is inside PATTERN (INSN) or a note. */
636 void
637 df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
639 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
640 df_uses_record (NULL, loc, DF_REF_REG_USE,
641 BLOCK_FOR_INSN (insn),
642 DF_INSN_INFO_GET (insn),
643 ref_flags);
646 static void
647 df_install_ref_incremental (df_ref ref)
649 struct df_reg_info **reg_info;
650 struct df_ref_info *ref_info;
651 df_ref *ref_ptr;
652 bool add_to_table;
654 rtx_insn *insn = DF_REF_INSN (ref);
655 basic_block bb = BLOCK_FOR_INSN (insn);
657 if (DF_REF_REG_DEF_P (ref))
659 reg_info = df->def_regs;
660 ref_info = &df->def_info;
661 ref_ptr = &DF_INSN_DEFS (insn);
662 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
664 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
666 reg_info = df->eq_use_regs;
667 ref_info = &df->use_info;
668 ref_ptr = &DF_INSN_EQ_USES (insn);
669 switch (ref_info->ref_order)
671 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
672 case DF_REF_ORDER_BY_REG_WITH_NOTES:
673 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
674 add_to_table = true;
675 break;
676 default:
677 add_to_table = false;
678 break;
681 else
683 reg_info = df->use_regs;
684 ref_info = &df->use_info;
685 ref_ptr = &DF_INSN_USES (insn);
686 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
689 /* Do not add if ref is not in the right blocks. */
690 if (add_to_table && df->analyze_subset)
691 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
693 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
695 if (add_to_table)
696 switch (ref_info->ref_order)
698 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
699 case DF_REF_ORDER_BY_REG_WITH_NOTES:
700 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
701 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
702 break;
703 default:
704 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
705 break;
708 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
709 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
711 DF_REF_NEXT_LOC (ref) = *ref_ptr;
712 *ref_ptr = ref;
714 #if 0
715 if (dump_file)
717 fprintf (dump_file, "adding ref ");
718 df_ref_debug (ref, dump_file);
720 #endif
721 /* By adding the ref directly, df_insn_rescan my not find any
722 differences even though the block will have changed. So we need
723 to mark the block dirty ourselves. */
724 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
725 df_set_bb_dirty (bb);
730 /*----------------------------------------------------------------------------
731 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
732 ----------------------------------------------------------------------------*/
734 static void
735 df_free_ref (df_ref ref)
737 struct df_scan_problem_data *problem_data
738 = (struct df_scan_problem_data *) df_scan->problem_data;
740 switch (DF_REF_CLASS (ref))
742 case DF_REF_BASE:
743 pool_free (problem_data->ref_base_pool, ref);
744 break;
746 case DF_REF_ARTIFICIAL:
747 pool_free (problem_data->ref_artificial_pool, ref);
748 break;
750 case DF_REF_REGULAR:
751 pool_free (problem_data->ref_regular_pool, ref);
752 break;
757 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
758 Also delete the def-use or use-def chain if it exists. */
760 static void
761 df_reg_chain_unlink (df_ref ref)
763 df_ref next = DF_REF_NEXT_REG (ref);
764 df_ref prev = DF_REF_PREV_REG (ref);
765 int id = DF_REF_ID (ref);
766 struct df_reg_info *reg_info;
767 df_ref *refs = NULL;
769 if (DF_REF_REG_DEF_P (ref))
771 int regno = DF_REF_REGNO (ref);
772 reg_info = DF_REG_DEF_GET (regno);
773 refs = df->def_info.refs;
775 else
777 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
779 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
780 switch (df->use_info.ref_order)
782 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
783 case DF_REF_ORDER_BY_REG_WITH_NOTES:
784 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
785 refs = df->use_info.refs;
786 break;
787 default:
788 break;
791 else
793 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
794 refs = df->use_info.refs;
798 if (refs)
800 if (df->analyze_subset)
802 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
803 refs[id] = NULL;
805 else
806 refs[id] = NULL;
809 /* Delete any def-use or use-def chains that start here. It is
810 possible that there is trash in this field. This happens for
811 insns that have been deleted when rescanning has been deferred
812 and the chain problem has also been deleted. The chain tear down
813 code skips deleted insns. */
814 if (df_chain && DF_REF_CHAIN (ref))
815 df_chain_unlink (ref);
817 reg_info->n_refs--;
818 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
820 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
821 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
824 /* Unlink from the reg chain. If there is no prev, this is the
825 first of the list. If not, just join the next and prev. */
826 if (prev)
827 DF_REF_NEXT_REG (prev) = next;
828 else
830 gcc_assert (reg_info->reg_chain == ref);
831 reg_info->reg_chain = next;
833 if (next)
834 DF_REF_PREV_REG (next) = prev;
836 df_free_ref (ref);
840 /* Create the insn record for INSN. If there was one there, zero it
841 out. */
843 struct df_insn_info *
844 df_insn_create_insn_record (rtx_insn *insn)
846 struct df_scan_problem_data *problem_data
847 = (struct df_scan_problem_data *) df_scan->problem_data;
848 struct df_insn_info *insn_rec;
850 df_grow_insn_info ();
851 insn_rec = DF_INSN_INFO_GET (insn);
852 if (!insn_rec)
854 insn_rec = (struct df_insn_info *) pool_alloc (problem_data->insn_pool);
855 DF_INSN_INFO_SET (insn, insn_rec);
857 memset (insn_rec, 0, sizeof (struct df_insn_info));
858 insn_rec->insn = insn;
859 return insn_rec;
863 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
865 static void
866 df_ref_chain_delete_du_chain (df_ref ref)
868 for (; ref; ref = DF_REF_NEXT_LOC (ref))
869 /* CHAIN is allocated by DF_CHAIN. So make sure to
870 pass df_scan instance for the problem. */
871 if (DF_REF_CHAIN (ref))
872 df_chain_unlink (ref);
876 /* Delete all refs in the ref chain. */
878 static void
879 df_ref_chain_delete (df_ref ref)
881 df_ref next;
882 for (; ref; ref = next)
884 next = DF_REF_NEXT_LOC (ref);
885 df_reg_chain_unlink (ref);
890 /* Delete the hardreg chain. */
892 static void
893 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
895 struct df_scan_problem_data *problem_data
896 = (struct df_scan_problem_data *) df_scan->problem_data;
897 df_mw_hardreg *next;
899 for (; hardregs; hardregs = next)
901 next = DF_MWS_NEXT (hardregs);
902 pool_free (problem_data->mw_reg_pool, hardregs);
907 /* Delete all of the refs information from the insn with UID.
908 Internal helper for df_insn_delete, df_insn_rescan, and other
909 df-scan routines that don't have to work in deferred mode
910 and do not have to mark basic blocks for re-processing. */
912 static void
913 df_insn_info_delete (unsigned int uid)
915 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
917 bitmap_clear_bit (&df->insns_to_delete, uid);
918 bitmap_clear_bit (&df->insns_to_rescan, uid);
919 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
920 if (insn_info)
922 struct df_scan_problem_data *problem_data
923 = (struct df_scan_problem_data *) df_scan->problem_data;
925 /* In general, notes do not have the insn_info fields
926 initialized. However, combine deletes insns by changing them
927 to notes. How clever. So we cannot just check if it is a
928 valid insn before short circuiting this code, we need to see
929 if we actually initialized it. */
930 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
932 if (df_chain)
934 df_ref_chain_delete_du_chain (insn_info->defs);
935 df_ref_chain_delete_du_chain (insn_info->uses);
936 df_ref_chain_delete_du_chain (insn_info->eq_uses);
939 df_ref_chain_delete (insn_info->defs);
940 df_ref_chain_delete (insn_info->uses);
941 df_ref_chain_delete (insn_info->eq_uses);
943 pool_free (problem_data->insn_pool, insn_info);
944 DF_INSN_UID_SET (uid, NULL);
948 /* Delete all of the refs information from INSN, either right now
949 or marked for later in deferred mode. */
951 void
952 df_insn_delete (rtx_insn *insn)
954 unsigned int uid;
955 basic_block bb;
957 gcc_checking_assert (INSN_P (insn));
959 if (!df)
960 return;
962 uid = INSN_UID (insn);
963 bb = BLOCK_FOR_INSN (insn);
965 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
966 not exist anymore (as mentioned in df-core.c: "The only requirement
967 [for DF] is that there be a correct control flow graph." Clearly
968 that isn't the case after pass_free_cfg. But DF is freed much later
969 because some back-ends want to use DF info even though the CFG is
970 already gone. It's not clear to me whether that is safe, actually.
971 In any case, we expect BB to be non-NULL at least up to register
972 allocation, so disallow a non-NULL BB up to there. Not perfect
973 but better than nothing... */
974 gcc_checking_assert (bb != NULL || reload_completed);
976 df_grow_bb_info (df_scan);
977 df_grow_reg_info ();
979 /* The block must be marked as dirty now, rather than later as in
980 df_insn_rescan and df_notes_rescan because it may not be there at
981 rescanning time and the mark would blow up.
982 DEBUG_INSNs do not make a block's data flow solution dirty (at
983 worst the LUIDs are no longer contiguous). */
984 if (bb != NULL && NONDEBUG_INSN_P (insn))
985 df_set_bb_dirty (bb);
987 /* The client has deferred rescanning. */
988 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
990 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
991 if (insn_info)
993 bitmap_clear_bit (&df->insns_to_rescan, uid);
994 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
995 bitmap_set_bit (&df->insns_to_delete, uid);
997 if (dump_file)
998 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
999 return;
1002 if (dump_file)
1003 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
1005 df_insn_info_delete (uid);
1009 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
1011 static void
1012 df_free_collection_rec (struct df_collection_rec *collection_rec)
1014 unsigned int ix;
1015 struct df_scan_problem_data *problem_data
1016 = (struct df_scan_problem_data *) df_scan->problem_data;
1017 df_ref ref;
1018 struct df_mw_hardreg *mw;
1020 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
1021 df_free_ref (ref);
1022 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
1023 df_free_ref (ref);
1024 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1025 df_free_ref (ref);
1026 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1027 pool_free (problem_data->mw_reg_pool, mw);
1029 collection_rec->def_vec.release ();
1030 collection_rec->use_vec.release ();
1031 collection_rec->eq_use_vec.release ();
1032 collection_rec->mw_vec.release ();
1035 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1037 bool
1038 df_insn_rescan (rtx_insn *insn)
1040 unsigned int uid = INSN_UID (insn);
1041 struct df_insn_info *insn_info = NULL;
1042 basic_block bb = BLOCK_FOR_INSN (insn);
1043 struct df_collection_rec collection_rec;
1045 if ((!df) || (!INSN_P (insn)))
1046 return false;
1048 if (!bb)
1050 if (dump_file)
1051 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1052 return false;
1055 /* The client has disabled rescanning and plans to do it itself. */
1056 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1057 return false;
1059 df_grow_bb_info (df_scan);
1060 df_grow_reg_info ();
1062 insn_info = DF_INSN_UID_SAFE_GET (uid);
1064 /* The client has deferred rescanning. */
1065 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1067 if (!insn_info)
1069 insn_info = df_insn_create_insn_record (insn);
1070 insn_info->defs = 0;
1071 insn_info->uses = 0;
1072 insn_info->eq_uses = 0;
1073 insn_info->mw_hardregs = 0;
1075 if (dump_file)
1076 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1078 bitmap_clear_bit (&df->insns_to_delete, uid);
1079 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1080 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1081 return false;
1084 bitmap_clear_bit (&df->insns_to_delete, uid);
1085 bitmap_clear_bit (&df->insns_to_rescan, uid);
1086 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1087 if (insn_info)
1089 int luid;
1090 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1091 /* If there's no change, return false. */
1092 if (the_same)
1094 df_free_collection_rec (&collection_rec);
1095 if (dump_file)
1096 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1097 return false;
1099 if (dump_file)
1100 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1102 /* There's change - we need to delete the existing info.
1103 Since the insn isn't moved, we can salvage its LUID. */
1104 luid = DF_INSN_LUID (insn);
1105 df_insn_info_delete (uid);
1106 df_insn_create_insn_record (insn);
1107 DF_INSN_LUID (insn) = luid;
1109 else
1111 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1112 df_insn_refs_collect (&collection_rec, bb, insn_info);
1113 if (dump_file)
1114 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1117 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1118 if (!DEBUG_INSN_P (insn))
1119 df_set_bb_dirty (bb);
1121 return true;
1124 /* Same as df_insn_rescan, but don't mark the basic block as
1125 dirty. */
1127 bool
1128 df_insn_rescan_debug_internal (rtx_insn *insn)
1130 unsigned int uid = INSN_UID (insn);
1131 struct df_insn_info *insn_info;
1133 gcc_assert (DEBUG_INSN_P (insn)
1134 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1136 if (!df)
1137 return false;
1139 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1140 if (!insn_info)
1141 return false;
1143 if (dump_file)
1144 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1146 bitmap_clear_bit (&df->insns_to_delete, uid);
1147 bitmap_clear_bit (&df->insns_to_rescan, uid);
1148 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1150 if (insn_info->defs == 0
1151 && insn_info->uses == 0
1152 && insn_info->eq_uses == 0
1153 && insn_info->mw_hardregs == 0)
1154 return false;
1156 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1158 if (df_chain)
1160 df_ref_chain_delete_du_chain (insn_info->defs);
1161 df_ref_chain_delete_du_chain (insn_info->uses);
1162 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1165 df_ref_chain_delete (insn_info->defs);
1166 df_ref_chain_delete (insn_info->uses);
1167 df_ref_chain_delete (insn_info->eq_uses);
1169 insn_info->defs = 0;
1170 insn_info->uses = 0;
1171 insn_info->eq_uses = 0;
1172 insn_info->mw_hardregs = 0;
1174 return true;
1178 /* Rescan all of the insns in the function. Note that the artificial
1179 uses and defs are not touched. This function will destroy def-use
1180 or use-def chains. */
1182 void
1183 df_insn_rescan_all (void)
1185 bool no_insn_rescan = false;
1186 bool defer_insn_rescan = false;
1187 basic_block bb;
1188 bitmap_iterator bi;
1189 unsigned int uid;
1190 bitmap_head tmp;
1192 bitmap_initialize (&tmp, &df_bitmap_obstack);
1194 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1196 df_clear_flags (DF_NO_INSN_RESCAN);
1197 no_insn_rescan = true;
1200 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1202 df_clear_flags (DF_DEFER_INSN_RESCAN);
1203 defer_insn_rescan = true;
1206 bitmap_copy (&tmp, &df->insns_to_delete);
1207 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1209 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1210 if (insn_info)
1211 df_insn_info_delete (uid);
1214 bitmap_clear (&tmp);
1215 bitmap_clear (&df->insns_to_delete);
1216 bitmap_clear (&df->insns_to_rescan);
1217 bitmap_clear (&df->insns_to_notes_rescan);
1219 FOR_EACH_BB_FN (bb, cfun)
1221 rtx_insn *insn;
1222 FOR_BB_INSNS (bb, insn)
1224 df_insn_rescan (insn);
1228 if (no_insn_rescan)
1229 df_set_flags (DF_NO_INSN_RESCAN);
1230 if (defer_insn_rescan)
1231 df_set_flags (DF_DEFER_INSN_RESCAN);
1235 /* Process all of the deferred rescans or deletions. */
1237 void
1238 df_process_deferred_rescans (void)
1240 bool no_insn_rescan = false;
1241 bool defer_insn_rescan = false;
1242 bitmap_iterator bi;
1243 unsigned int uid;
1244 bitmap_head tmp;
1246 bitmap_initialize (&tmp, &df_bitmap_obstack);
1248 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1250 df_clear_flags (DF_NO_INSN_RESCAN);
1251 no_insn_rescan = true;
1254 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1256 df_clear_flags (DF_DEFER_INSN_RESCAN);
1257 defer_insn_rescan = true;
1260 if (dump_file)
1261 fprintf (dump_file, "starting the processing of deferred insns\n");
1263 bitmap_copy (&tmp, &df->insns_to_delete);
1264 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1266 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1267 if (insn_info)
1268 df_insn_info_delete (uid);
1271 bitmap_copy (&tmp, &df->insns_to_rescan);
1272 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1274 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1275 if (insn_info)
1276 df_insn_rescan (insn_info->insn);
1279 bitmap_copy (&tmp, &df->insns_to_notes_rescan);
1280 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1282 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1283 if (insn_info)
1284 df_notes_rescan (insn_info->insn);
1287 if (dump_file)
1288 fprintf (dump_file, "ending the processing of deferred insns\n");
1290 bitmap_clear (&tmp);
1291 bitmap_clear (&df->insns_to_delete);
1292 bitmap_clear (&df->insns_to_rescan);
1293 bitmap_clear (&df->insns_to_notes_rescan);
1295 if (no_insn_rescan)
1296 df_set_flags (DF_NO_INSN_RESCAN);
1297 if (defer_insn_rescan)
1298 df_set_flags (DF_DEFER_INSN_RESCAN);
1300 /* If someone changed regs_ever_live during this pass, fix up the
1301 entry and exit blocks. */
1302 if (df->redo_entry_and_exit)
1304 df_update_entry_exit_and_calls ();
1305 df->redo_entry_and_exit = false;
1310 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1311 the uses if INCLUDE_USES. Include the eq_uses if
1312 INCLUDE_EQ_USES. */
1314 static unsigned int
1315 df_count_refs (bool include_defs, bool include_uses,
1316 bool include_eq_uses)
1318 unsigned int regno;
1319 int size = 0;
1320 unsigned int m = df->regs_inited;
1322 for (regno = 0; regno < m; regno++)
1324 if (include_defs)
1325 size += DF_REG_DEF_COUNT (regno);
1326 if (include_uses)
1327 size += DF_REG_USE_COUNT (regno);
1328 if (include_eq_uses)
1329 size += DF_REG_EQ_USE_COUNT (regno);
1331 return size;
1335 /* Take build ref table for either the uses or defs from the reg-use
1336 or reg-def chains. This version processes the refs in reg order
1337 which is likely to be best if processing the whole function. */
1339 static void
1340 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1341 bool include_defs,
1342 bool include_uses,
1343 bool include_eq_uses)
1345 unsigned int m = df->regs_inited;
1346 unsigned int regno;
1347 unsigned int offset = 0;
1348 unsigned int start;
1350 if (df->changeable_flags & DF_NO_HARD_REGS)
1352 start = FIRST_PSEUDO_REGISTER;
1353 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1354 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1356 else
1357 start = 0;
1359 ref_info->total_size
1360 = df_count_refs (include_defs, include_uses, include_eq_uses);
1362 df_check_and_grow_ref_info (ref_info, 1);
1364 for (regno = start; regno < m; regno++)
1366 int count = 0;
1367 ref_info->begin[regno] = offset;
1368 if (include_defs)
1370 df_ref ref = DF_REG_DEF_CHAIN (regno);
1371 while (ref)
1373 ref_info->refs[offset] = ref;
1374 DF_REF_ID (ref) = offset++;
1375 count++;
1376 ref = DF_REF_NEXT_REG (ref);
1377 gcc_checking_assert (offset < ref_info->refs_size);
1380 if (include_uses)
1382 df_ref ref = DF_REG_USE_CHAIN (regno);
1383 while (ref)
1385 ref_info->refs[offset] = ref;
1386 DF_REF_ID (ref) = offset++;
1387 count++;
1388 ref = DF_REF_NEXT_REG (ref);
1389 gcc_checking_assert (offset < ref_info->refs_size);
1392 if (include_eq_uses)
1394 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1395 while (ref)
1397 ref_info->refs[offset] = ref;
1398 DF_REF_ID (ref) = offset++;
1399 count++;
1400 ref = DF_REF_NEXT_REG (ref);
1401 gcc_checking_assert (offset < ref_info->refs_size);
1404 ref_info->count[regno] = count;
1407 /* The bitmap size is not decremented when refs are deleted. So
1408 reset it now that we have squished out all of the empty
1409 slots. */
1410 ref_info->table_size = offset;
1414 /* Take build ref table for either the uses or defs from the reg-use
1415 or reg-def chains. This version processes the refs in insn order
1416 which is likely to be best if processing some segment of the
1417 function. */
1419 static void
1420 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1421 bool include_defs,
1422 bool include_uses,
1423 bool include_eq_uses)
1425 bitmap_iterator bi;
1426 unsigned int bb_index;
1427 unsigned int m = df->regs_inited;
1428 unsigned int offset = 0;
1429 unsigned int r;
1430 unsigned int start
1431 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1433 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1434 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1436 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1437 df_check_and_grow_ref_info (ref_info, 1);
1439 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1441 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1442 rtx_insn *insn;
1443 df_ref def, use;
1445 if (include_defs)
1446 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1448 unsigned int regno = DF_REF_REGNO (def);
1449 ref_info->count[regno]++;
1451 if (include_uses)
1452 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1454 unsigned int regno = DF_REF_REGNO (use);
1455 ref_info->count[regno]++;
1458 FOR_BB_INSNS (bb, insn)
1460 if (INSN_P (insn))
1462 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1464 if (include_defs)
1465 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1467 unsigned int regno = DF_REF_REGNO (def);
1468 ref_info->count[regno]++;
1470 if (include_uses)
1471 FOR_EACH_INSN_INFO_USE (use, insn_info)
1473 unsigned int regno = DF_REF_REGNO (use);
1474 ref_info->count[regno]++;
1476 if (include_eq_uses)
1477 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1479 unsigned int regno = DF_REF_REGNO (use);
1480 ref_info->count[regno]++;
1486 for (r = start; r < m; r++)
1488 ref_info->begin[r] = offset;
1489 offset += ref_info->count[r];
1490 ref_info->count[r] = 0;
1493 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1495 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1496 rtx_insn *insn;
1497 df_ref def, use;
1499 if (include_defs)
1500 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1502 unsigned int regno = DF_REF_REGNO (def);
1503 if (regno >= start)
1505 unsigned int id
1506 = ref_info->begin[regno] + ref_info->count[regno]++;
1507 DF_REF_ID (def) = id;
1508 ref_info->refs[id] = def;
1511 if (include_uses)
1512 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1514 unsigned int regno = DF_REF_REGNO (def);
1515 if (regno >= start)
1517 unsigned int id
1518 = ref_info->begin[regno] + ref_info->count[regno]++;
1519 DF_REF_ID (use) = id;
1520 ref_info->refs[id] = use;
1524 FOR_BB_INSNS (bb, insn)
1526 if (INSN_P (insn))
1528 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1530 if (include_defs)
1531 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1533 unsigned int regno = DF_REF_REGNO (def);
1534 if (regno >= start)
1536 unsigned int id
1537 = ref_info->begin[regno] + ref_info->count[regno]++;
1538 DF_REF_ID (def) = id;
1539 ref_info->refs[id] = def;
1542 if (include_uses)
1543 FOR_EACH_INSN_INFO_USE (use, insn_info)
1545 unsigned int regno = DF_REF_REGNO (use);
1546 if (regno >= start)
1548 unsigned int id
1549 = ref_info->begin[regno] + ref_info->count[regno]++;
1550 DF_REF_ID (use) = id;
1551 ref_info->refs[id] = use;
1554 if (include_eq_uses)
1555 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1557 unsigned int regno = DF_REF_REGNO (use);
1558 if (regno >= start)
1560 unsigned int id
1561 = ref_info->begin[regno] + ref_info->count[regno]++;
1562 DF_REF_ID (use) = id;
1563 ref_info->refs[id] = use;
1570 /* The bitmap size is not decremented when refs are deleted. So
1571 reset it now that we have squished out all of the empty
1572 slots. */
1574 ref_info->table_size = offset;
1577 /* Take build ref table for either the uses or defs from the reg-use
1578 or reg-def chains. */
1580 static void
1581 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1582 bool include_defs,
1583 bool include_uses,
1584 bool include_eq_uses)
1586 if (df->analyze_subset)
1587 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1588 include_uses, include_eq_uses);
1589 else
1590 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1591 include_uses, include_eq_uses);
1595 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1596 static unsigned int
1597 df_add_refs_to_table (unsigned int offset,
1598 struct df_ref_info *ref_info,
1599 df_ref ref)
1601 for (; ref; ref = DF_REF_NEXT_LOC (ref))
1602 if (!(df->changeable_flags & DF_NO_HARD_REGS)
1603 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1605 ref_info->refs[offset] = ref;
1606 DF_REF_ID (ref) = offset++;
1608 return offset;
1612 /* Count the number of refs in all of the insns of BB. Include the
1613 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1614 eq_uses if INCLUDE_EQ_USES. */
1616 static unsigned int
1617 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1618 struct df_ref_info *ref_info,
1619 bool include_defs, bool include_uses,
1620 bool include_eq_uses)
1622 rtx_insn *insn;
1624 if (include_defs)
1625 offset = df_add_refs_to_table (offset, ref_info,
1626 df_get_artificial_defs (bb->index));
1627 if (include_uses)
1628 offset = df_add_refs_to_table (offset, ref_info,
1629 df_get_artificial_uses (bb->index));
1631 FOR_BB_INSNS (bb, insn)
1632 if (INSN_P (insn))
1634 unsigned int uid = INSN_UID (insn);
1635 if (include_defs)
1636 offset = df_add_refs_to_table (offset, ref_info,
1637 DF_INSN_UID_DEFS (uid));
1638 if (include_uses)
1639 offset = df_add_refs_to_table (offset, ref_info,
1640 DF_INSN_UID_USES (uid));
1641 if (include_eq_uses)
1642 offset = df_add_refs_to_table (offset, ref_info,
1643 DF_INSN_UID_EQ_USES (uid));
1645 return offset;
1649 /* Organize the refs by insn into the table in REF_INFO. If
1650 blocks_to_analyze is defined, use that set, otherwise the entire
1651 program. Include the defs if INCLUDE_DEFS. Include the uses if
1652 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1654 static void
1655 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1656 bool include_defs, bool include_uses,
1657 bool include_eq_uses)
1659 basic_block bb;
1660 unsigned int offset = 0;
1662 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1663 df_check_and_grow_ref_info (ref_info, 1);
1664 if (df->blocks_to_analyze)
1666 bitmap_iterator bi;
1667 unsigned int index;
1669 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1671 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1672 index),
1673 offset, ref_info,
1674 include_defs, include_uses,
1675 include_eq_uses);
1678 ref_info->table_size = offset;
1680 else
1682 FOR_ALL_BB_FN (bb, cfun)
1683 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1684 include_defs, include_uses,
1685 include_eq_uses);
1686 ref_info->table_size = offset;
1691 /* If the use refs in DF are not organized, reorganize them. */
1693 void
1694 df_maybe_reorganize_use_refs (enum df_ref_order order)
1696 if (order == df->use_info.ref_order)
1697 return;
1699 switch (order)
1701 case DF_REF_ORDER_BY_REG:
1702 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1703 break;
1705 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1706 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1707 break;
1709 case DF_REF_ORDER_BY_INSN:
1710 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1711 break;
1713 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1714 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1715 break;
1717 case DF_REF_ORDER_NO_TABLE:
1718 free (df->use_info.refs);
1719 df->use_info.refs = NULL;
1720 df->use_info.refs_size = 0;
1721 break;
1723 case DF_REF_ORDER_UNORDERED:
1724 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1725 gcc_unreachable ();
1726 break;
1729 df->use_info.ref_order = order;
1733 /* If the def refs in DF are not organized, reorganize them. */
1735 void
1736 df_maybe_reorganize_def_refs (enum df_ref_order order)
1738 if (order == df->def_info.ref_order)
1739 return;
1741 switch (order)
1743 case DF_REF_ORDER_BY_REG:
1744 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1745 break;
1747 case DF_REF_ORDER_BY_INSN:
1748 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1749 break;
1751 case DF_REF_ORDER_NO_TABLE:
1752 free (df->def_info.refs);
1753 df->def_info.refs = NULL;
1754 df->def_info.refs_size = 0;
1755 break;
1757 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1758 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1759 case DF_REF_ORDER_UNORDERED:
1760 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1761 gcc_unreachable ();
1762 break;
1765 df->def_info.ref_order = order;
1769 /* Change all of the basic block references in INSN to use the insn's
1770 current basic block. This function is called from routines that move
1771 instructions from one block to another. */
1773 void
1774 df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1776 basic_block old_bb = BLOCK_FOR_INSN (insn);
1777 struct df_insn_info *insn_info;
1778 unsigned int uid = INSN_UID (insn);
1780 if (old_bb == new_bb)
1781 return;
1783 set_block_for_insn (insn, new_bb);
1785 if (!df)
1786 return;
1788 if (dump_file)
1789 fprintf (dump_file, "changing bb of uid %d\n", uid);
1791 insn_info = DF_INSN_UID_SAFE_GET (uid);
1792 if (insn_info == NULL)
1794 if (dump_file)
1795 fprintf (dump_file, " unscanned insn\n");
1796 df_insn_rescan (insn);
1797 return;
1800 if (!INSN_P (insn))
1801 return;
1803 df_set_bb_dirty (new_bb);
1804 if (old_bb)
1806 if (dump_file)
1807 fprintf (dump_file, " from %d to %d\n",
1808 old_bb->index, new_bb->index);
1809 df_set_bb_dirty (old_bb);
1811 else
1812 if (dump_file)
1813 fprintf (dump_file, " to %d\n", new_bb->index);
1817 /* Helper function for df_ref_change_reg_with_loc. */
1819 static void
1820 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1821 struct df_reg_info *new_df,
1822 unsigned int new_regno, rtx loc)
1824 df_ref the_ref = old_df->reg_chain;
1826 while (the_ref)
1828 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1829 && DF_REF_LOC (the_ref)
1830 && (*DF_REF_LOC (the_ref) == loc))
1832 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1833 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1834 df_ref *ref_ptr;
1835 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1837 DF_REF_REGNO (the_ref) = new_regno;
1838 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1840 /* Pull the_ref out of the old regno chain. */
1841 if (prev_ref)
1842 DF_REF_NEXT_REG (prev_ref) = next_ref;
1843 else
1844 old_df->reg_chain = next_ref;
1845 if (next_ref)
1846 DF_REF_PREV_REG (next_ref) = prev_ref;
1847 old_df->n_refs--;
1849 /* Put the ref into the new regno chain. */
1850 DF_REF_PREV_REG (the_ref) = NULL;
1851 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1852 if (new_df->reg_chain)
1853 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1854 new_df->reg_chain = the_ref;
1855 new_df->n_refs++;
1856 if (DF_REF_BB (the_ref))
1857 df_set_bb_dirty (DF_REF_BB (the_ref));
1859 /* Need to sort the record again that the ref was in because
1860 the regno is a sorting key. First, find the right
1861 record. */
1862 if (DF_REF_REG_DEF_P (the_ref))
1863 ref_ptr = &insn_info->defs;
1864 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1865 ref_ptr = &insn_info->eq_uses;
1866 else
1867 ref_ptr = &insn_info->uses;
1868 if (dump_file)
1869 fprintf (dump_file, "changing reg in insn %d\n",
1870 DF_REF_INSN_UID (the_ref));
1872 /* Stop if we find the current reference or where the reference
1873 needs to be. */
1874 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1875 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1876 if (*ref_ptr != the_ref)
1878 /* The reference needs to be promoted up the list. */
1879 df_ref next = DF_REF_NEXT_LOC (the_ref);
1880 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1881 *ref_ptr = the_ref;
1883 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1884 while (*ref_ptr != the_ref);
1885 *ref_ptr = next;
1887 else if (DF_REF_NEXT_LOC (the_ref)
1888 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1890 /* The reference needs to be demoted down the list. */
1891 *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1893 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1894 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1895 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1896 *ref_ptr = the_ref;
1899 the_ref = next_ref;
1901 else
1902 the_ref = DF_REF_NEXT_REG (the_ref);
1907 /* Change the regno of register LOC to NEW_REGNO and update the df
1908 information accordingly. Refs that do not match LOC are not changed
1909 which means that artificial refs are not changed since they have no loc.
1910 This call is to support the SET_REGNO macro. */
1912 void
1913 df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1915 unsigned int old_regno = REGNO (loc);
1916 if (old_regno == new_regno)
1917 return;
1919 if (df)
1921 df_grow_reg_info ();
1923 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1924 DF_REG_DEF_GET (new_regno),
1925 new_regno, loc);
1926 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1927 DF_REG_USE_GET (new_regno),
1928 new_regno, loc);
1929 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1930 DF_REG_EQ_USE_GET (new_regno),
1931 new_regno, loc);
1933 set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1937 /* Delete the mw_hardregs that point into the eq_notes. */
1939 static void
1940 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1942 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1943 struct df_scan_problem_data *problem_data
1944 = (struct df_scan_problem_data *) df_scan->problem_data;
1946 while (*mw_ptr)
1948 df_mw_hardreg *mw = *mw_ptr;
1949 if (mw->flags & DF_REF_IN_NOTE)
1951 *mw_ptr = DF_MWS_NEXT (mw);
1952 pool_free (problem_data->mw_reg_pool, mw);
1954 else
1955 mw_ptr = &DF_MWS_NEXT (mw);
1960 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1962 void
1963 df_notes_rescan (rtx_insn *insn)
1965 struct df_insn_info *insn_info;
1966 unsigned int uid = INSN_UID (insn);
1968 if (!df)
1969 return;
1971 /* The client has disabled rescanning and plans to do it itself. */
1972 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1973 return;
1975 /* Do nothing if the insn hasn't been emitted yet. */
1976 if (!BLOCK_FOR_INSN (insn))
1977 return;
1979 df_grow_bb_info (df_scan);
1980 df_grow_reg_info ();
1982 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1984 /* The client has deferred rescanning. */
1985 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1987 if (!insn_info)
1989 insn_info = df_insn_create_insn_record (insn);
1990 insn_info->defs = 0;
1991 insn_info->uses = 0;
1992 insn_info->eq_uses = 0;
1993 insn_info->mw_hardregs = 0;
1996 bitmap_clear_bit (&df->insns_to_delete, uid);
1997 /* If the insn is set to be rescanned, it does not need to also
1998 be notes rescanned. */
1999 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
2000 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
2001 return;
2004 bitmap_clear_bit (&df->insns_to_delete, uid);
2005 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
2007 if (insn_info)
2009 basic_block bb = BLOCK_FOR_INSN (insn);
2010 rtx note;
2011 struct df_collection_rec collection_rec;
2012 unsigned int i;
2014 df_mw_hardreg_chain_delete_eq_uses (insn_info);
2015 df_ref_chain_delete (insn_info->eq_uses);
2016 insn_info->eq_uses = NULL;
2018 /* Process REG_EQUIV/REG_EQUAL notes */
2019 for (note = REG_NOTES (insn); note;
2020 note = XEXP (note, 1))
2022 switch (REG_NOTE_KIND (note))
2024 case REG_EQUIV:
2025 case REG_EQUAL:
2026 df_uses_record (&collection_rec,
2027 &XEXP (note, 0), DF_REF_REG_USE,
2028 bb, insn_info, DF_REF_IN_NOTE);
2029 default:
2030 break;
2034 /* Find some place to put any new mw_hardregs. */
2035 df_canonize_collection_rec (&collection_rec);
2036 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2037 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2039 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2040 mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2041 DF_MWS_NEXT (mw) = *mw_ptr;
2042 *mw_ptr = mw;
2043 mw_ptr = &DF_MWS_NEXT (mw);
2045 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2047 else
2048 df_insn_rescan (insn);
2053 /*----------------------------------------------------------------------------
2054 Hard core instruction scanning code. No external interfaces here,
2055 just a lot of routines that look inside insns.
2056 ----------------------------------------------------------------------------*/
2059 /* Return true if the contents of two df_ref's are identical.
2060 It ignores DF_REF_MARKER. */
2062 static bool
2063 df_ref_equal_p (df_ref ref1, df_ref ref2)
2065 if (!ref2)
2066 return false;
2068 if (ref1 == ref2)
2069 return true;
2071 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2072 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2073 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2074 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2075 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2076 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2077 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2078 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2079 return false;
2081 switch (DF_REF_CLASS (ref1))
2083 case DF_REF_ARTIFICIAL:
2084 case DF_REF_BASE:
2085 return true;
2087 case DF_REF_REGULAR:
2088 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2090 default:
2091 gcc_unreachable ();
2093 return false;
2097 /* Compare REF1 and REF2 for sorting. This is only called from places
2098 where all of the refs are of the same type, in the same insn, and
2099 have the same bb. So these fields are not checked. */
2101 static int
2102 df_ref_compare (df_ref ref1, df_ref ref2)
2104 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2105 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2107 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2108 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2110 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2111 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2113 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2114 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2116 /* Cannot look at the LOC field on artificial refs. */
2117 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2118 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2119 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2121 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2123 /* If two refs are identical except that one of them has is from
2124 a mw and one is not, we need to have the one with the mw
2125 first. */
2126 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2127 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2128 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2129 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2130 return -1;
2131 else
2132 return 1;
2135 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2138 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2140 static int
2141 df_ref_ptr_compare (const void *r1, const void *r2)
2143 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2146 static void
2147 df_swap_refs (vec<df_ref, va_heap> *ref_vec, int i, int j)
2149 df_ref tmp = (*ref_vec)[i];
2150 (*ref_vec)[i] = (*ref_vec)[j];
2151 (*ref_vec)[j] = tmp;
2154 /* Sort and compress a set of refs. */
2156 static void
2157 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2159 unsigned int count;
2160 unsigned int i;
2161 unsigned int dist = 0;
2163 count = ref_vec->length ();
2165 /* If there are 1 or 0 elements, there is nothing to do. */
2166 if (count < 2)
2167 return;
2168 else if (count == 2)
2170 df_ref r0 = (*ref_vec)[0];
2171 df_ref r1 = (*ref_vec)[1];
2172 if (df_ref_compare (r0, r1) > 0)
2173 df_swap_refs (ref_vec, 0, 1);
2175 else
2177 for (i = 0; i < count - 1; i++)
2179 df_ref r0 = (*ref_vec)[i];
2180 df_ref r1 = (*ref_vec)[i + 1];
2181 if (df_ref_compare (r0, r1) >= 0)
2182 break;
2184 /* If the array is already strictly ordered,
2185 which is the most common case for large COUNT case
2186 (which happens for CALL INSNs),
2187 no need to sort and filter out duplicate.
2188 Simply return the count.
2189 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2190 of DF_REF_COMPARE. */
2191 if (i == count - 1)
2192 return;
2193 ref_vec->qsort (df_ref_ptr_compare);
2196 for (i=0; i<count-dist; i++)
2198 /* Find the next ref that is not equal to the current ref. */
2199 while (i + dist + 1 < count
2200 && df_ref_equal_p ((*ref_vec)[i],
2201 (*ref_vec)[i + dist + 1]))
2203 df_free_ref ((*ref_vec)[i + dist + 1]);
2204 dist++;
2206 /* Copy it down to the next position. */
2207 if (dist && i + dist + 1 < count)
2208 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2211 count -= dist;
2212 ref_vec->truncate (count);
2216 /* Return true if the contents of two df_ref's are identical.
2217 It ignores DF_REF_MARKER. */
2219 static bool
2220 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2222 if (!mw2)
2223 return false;
2224 return (mw1 == mw2) ||
2225 (mw1->mw_reg == mw2->mw_reg
2226 && mw1->type == mw2->type
2227 && mw1->flags == mw2->flags
2228 && mw1->start_regno == mw2->start_regno
2229 && mw1->end_regno == mw2->end_regno);
2233 /* Compare MW1 and MW2 for sorting. */
2235 static int
2236 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2238 if (mw1->type != mw2->type)
2239 return mw1->type - mw2->type;
2241 if (mw1->flags != mw2->flags)
2242 return mw1->flags - mw2->flags;
2244 if (mw1->start_regno != mw2->start_regno)
2245 return mw1->start_regno - mw2->start_regno;
2247 if (mw1->end_regno != mw2->end_regno)
2248 return mw1->end_regno - mw2->end_regno;
2250 if (mw1->mw_reg != mw2->mw_reg)
2251 return mw1->mw_order - mw2->mw_order;
2253 return 0;
2256 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2258 static int
2259 df_mw_ptr_compare (const void *m1, const void *m2)
2261 return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2262 *(const df_mw_hardreg *const *) m2);
2265 /* Sort and compress a set of refs. */
2267 static void
2268 df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec)
2270 unsigned int count;
2271 struct df_scan_problem_data *problem_data
2272 = (struct df_scan_problem_data *) df_scan->problem_data;
2273 unsigned int i;
2274 unsigned int dist = 0;
2276 count = mw_vec->length ();
2277 if (count < 2)
2278 return;
2279 else if (count == 2)
2281 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2282 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2283 if (df_mw_compare (m0, m1) > 0)
2285 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2286 (*mw_vec)[0] = (*mw_vec)[1];
2287 (*mw_vec)[1] = tmp;
2290 else
2291 mw_vec->qsort (df_mw_ptr_compare);
2293 for (i=0; i<count-dist; i++)
2295 /* Find the next ref that is not equal to the current ref. */
2296 while (i + dist + 1 < count
2297 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2299 pool_free (problem_data->mw_reg_pool,
2300 (*mw_vec)[i + dist + 1]);
2301 dist++;
2303 /* Copy it down to the next position. */
2304 if (dist && i + dist + 1 < count)
2305 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2308 count -= dist;
2309 mw_vec->truncate (count);
2313 /* Sort and remove duplicates from the COLLECTION_REC. */
2315 static void
2316 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2318 df_sort_and_compress_refs (&collection_rec->def_vec);
2319 df_sort_and_compress_refs (&collection_rec->use_vec);
2320 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2321 df_sort_and_compress_mws (&collection_rec->mw_vec);
2325 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2327 static void
2328 df_install_ref (df_ref this_ref,
2329 struct df_reg_info *reg_info,
2330 struct df_ref_info *ref_info,
2331 bool add_to_table)
2333 unsigned int regno = DF_REF_REGNO (this_ref);
2334 /* Add the ref to the reg_{def,use,eq_use} chain. */
2335 df_ref head = reg_info->reg_chain;
2337 reg_info->reg_chain = this_ref;
2338 reg_info->n_refs++;
2340 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2342 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2343 df->hard_regs_live_count[regno]++;
2346 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2347 && DF_REF_PREV_REG (this_ref) == NULL);
2349 DF_REF_NEXT_REG (this_ref) = head;
2351 /* We cannot actually link to the head of the chain. */
2352 DF_REF_PREV_REG (this_ref) = NULL;
2354 if (head)
2355 DF_REF_PREV_REG (head) = this_ref;
2357 if (add_to_table)
2359 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2360 df_check_and_grow_ref_info (ref_info, 1);
2361 DF_REF_ID (this_ref) = ref_info->table_size;
2362 /* Add the ref to the big array of defs. */
2363 ref_info->refs[ref_info->table_size] = this_ref;
2364 ref_info->table_size++;
2366 else
2367 DF_REF_ID (this_ref) = -1;
2369 ref_info->total_size++;
2373 /* This function takes one of the groups of refs (defs, uses or
2374 eq_uses) and installs the entire group into the insn. It also adds
2375 each of these refs into the appropriate chains. */
2377 static df_ref
2378 df_install_refs (basic_block bb,
2379 const vec<df_ref, va_heap> *old_vec,
2380 struct df_reg_info **reg_info,
2381 struct df_ref_info *ref_info,
2382 bool is_notes)
2384 unsigned int count = old_vec->length ();
2385 if (count)
2387 bool add_to_table;
2388 df_ref this_ref;
2389 unsigned int ix;
2391 switch (ref_info->ref_order)
2393 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2394 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2395 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2396 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2397 add_to_table = true;
2398 break;
2399 case DF_REF_ORDER_UNORDERED:
2400 case DF_REF_ORDER_BY_REG:
2401 case DF_REF_ORDER_BY_INSN:
2402 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2403 add_to_table = !is_notes;
2404 break;
2405 default:
2406 add_to_table = false;
2407 break;
2410 /* Do not add if ref is not in the right blocks. */
2411 if (add_to_table && df->analyze_subset)
2412 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2414 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2416 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2417 ? (*old_vec)[ix + 1]
2418 : NULL);
2419 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2420 ref_info, add_to_table);
2422 return (*old_vec)[0];
2424 else
2425 return 0;
2429 /* This function takes the mws installs the entire group into the
2430 insn. */
2432 static struct df_mw_hardreg *
2433 df_install_mws (const vec<df_mw_hardreg_ptr, va_heap> *old_vec)
2435 unsigned int count = old_vec->length ();
2436 if (count)
2438 for (unsigned int i = 0; i < count - 1; i++)
2439 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2440 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2441 return (*old_vec)[0];
2443 else
2444 return 0;
2448 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2449 chains and update other necessary information. */
2451 static void
2452 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2453 basic_block bb, rtx_insn *insn, unsigned int flags)
2455 if (insn)
2457 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2458 /* If there is a vector in the collection rec, add it to the
2459 insn. A null rec is a signal that the caller will handle the
2460 chain specially. */
2461 if (flags & copy_defs)
2463 gcc_checking_assert (!insn_rec->defs);
2464 insn_rec->defs
2465 = df_install_refs (bb, &collection_rec->def_vec,
2466 df->def_regs,
2467 &df->def_info, false);
2469 if (flags & copy_uses)
2471 gcc_checking_assert (!insn_rec->uses);
2472 insn_rec->uses
2473 = df_install_refs (bb, &collection_rec->use_vec,
2474 df->use_regs,
2475 &df->use_info, false);
2477 if (flags & copy_eq_uses)
2479 gcc_checking_assert (!insn_rec->eq_uses);
2480 insn_rec->eq_uses
2481 = df_install_refs (bb, &collection_rec->eq_use_vec,
2482 df->eq_use_regs,
2483 &df->use_info, true);
2485 if (flags & copy_mw)
2487 gcc_checking_assert (!insn_rec->mw_hardregs);
2488 insn_rec->mw_hardregs
2489 = df_install_mws (&collection_rec->mw_vec);
2492 else
2494 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2496 gcc_checking_assert (!bb_info->artificial_defs);
2497 bb_info->artificial_defs
2498 = df_install_refs (bb, &collection_rec->def_vec,
2499 df->def_regs,
2500 &df->def_info, false);
2501 gcc_checking_assert (!bb_info->artificial_uses);
2502 bb_info->artificial_uses
2503 = df_install_refs (bb, &collection_rec->use_vec,
2504 df->use_regs,
2505 &df->use_info, false);
2510 /* Allocate a ref and initialize its fields. */
2512 static df_ref
2513 df_ref_create_structure (enum df_ref_class cl,
2514 struct df_collection_rec *collection_rec,
2515 rtx reg, rtx *loc,
2516 basic_block bb, struct df_insn_info *info,
2517 enum df_ref_type ref_type,
2518 int ref_flags)
2520 df_ref this_ref = NULL;
2521 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2522 struct df_scan_problem_data *problem_data
2523 = (struct df_scan_problem_data *) df_scan->problem_data;
2525 switch (cl)
2527 case DF_REF_BASE:
2528 this_ref = (df_ref) pool_alloc (problem_data->ref_base_pool);
2529 gcc_checking_assert (loc == NULL);
2530 break;
2532 case DF_REF_ARTIFICIAL:
2533 this_ref = (df_ref) pool_alloc (problem_data->ref_artificial_pool);
2534 this_ref->artificial_ref.bb = bb;
2535 gcc_checking_assert (loc == NULL);
2536 break;
2538 case DF_REF_REGULAR:
2539 this_ref = (df_ref) pool_alloc (problem_data->ref_regular_pool);
2540 this_ref->regular_ref.loc = loc;
2541 gcc_checking_assert (loc);
2542 break;
2545 DF_REF_CLASS (this_ref) = cl;
2546 DF_REF_ID (this_ref) = -1;
2547 DF_REF_REG (this_ref) = reg;
2548 DF_REF_REGNO (this_ref) = regno;
2549 DF_REF_TYPE (this_ref) = ref_type;
2550 DF_REF_INSN_INFO (this_ref) = info;
2551 DF_REF_CHAIN (this_ref) = NULL;
2552 DF_REF_FLAGS (this_ref) = ref_flags;
2553 DF_REF_NEXT_REG (this_ref) = NULL;
2554 DF_REF_PREV_REG (this_ref) = NULL;
2555 DF_REF_ORDER (this_ref) = df->ref_order++;
2557 /* We need to clear this bit because fwprop, and in the future
2558 possibly other optimizations sometimes create new refs using ond
2559 refs as the model. */
2560 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2562 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2563 if (regno < FIRST_PSEUDO_REGISTER
2564 && !DF_REF_IS_ARTIFICIAL (this_ref)
2565 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2567 if (DF_REF_REG_DEF_P (this_ref))
2569 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2570 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2572 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2573 && (regno == FRAME_POINTER_REGNUM
2574 || regno == ARG_POINTER_REGNUM)))
2575 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2578 if (collection_rec)
2580 if (DF_REF_REG_DEF_P (this_ref))
2581 collection_rec->def_vec.safe_push (this_ref);
2582 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2583 collection_rec->eq_use_vec.safe_push (this_ref);
2584 else
2585 collection_rec->use_vec.safe_push (this_ref);
2587 else
2588 df_install_ref_incremental (this_ref);
2590 return this_ref;
2594 /* Create new references of type DF_REF_TYPE for each part of register REG
2595 at address LOC within INSN of BB. */
2598 static void
2599 df_ref_record (enum df_ref_class cl,
2600 struct df_collection_rec *collection_rec,
2601 rtx reg, rtx *loc,
2602 basic_block bb, struct df_insn_info *insn_info,
2603 enum df_ref_type ref_type,
2604 int ref_flags)
2606 unsigned int regno;
2608 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2610 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2611 if (regno < FIRST_PSEUDO_REGISTER)
2613 struct df_mw_hardreg *hardreg = NULL;
2614 struct df_scan_problem_data *problem_data
2615 = (struct df_scan_problem_data *) df_scan->problem_data;
2616 unsigned int i;
2617 unsigned int endregno;
2618 df_ref ref;
2620 if (GET_CODE (reg) == SUBREG)
2622 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2623 SUBREG_BYTE (reg), GET_MODE (reg));
2624 endregno = regno + subreg_nregs (reg);
2626 else
2627 endregno = END_REGNO (reg);
2629 /* If this is a multiword hardreg, we create some extra
2630 datastructures that will enable us to easily build REG_DEAD
2631 and REG_UNUSED notes. */
2632 if (collection_rec
2633 && (endregno != regno + 1) && insn_info)
2635 /* Sets to a subreg of a multiword register are partial.
2636 Sets to a non-subreg of a multiword register are not. */
2637 if (GET_CODE (reg) == SUBREG)
2638 ref_flags |= DF_REF_PARTIAL;
2639 ref_flags |= DF_REF_MW_HARDREG;
2641 hardreg = (struct df_mw_hardreg *) pool_alloc (problem_data->mw_reg_pool);
2642 hardreg->type = ref_type;
2643 hardreg->flags = ref_flags;
2644 hardreg->mw_reg = reg;
2645 hardreg->start_regno = regno;
2646 hardreg->end_regno = endregno - 1;
2647 hardreg->mw_order = df->ref_order++;
2648 collection_rec->mw_vec.safe_push (hardreg);
2651 for (i = regno; i < endregno; i++)
2653 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2654 bb, insn_info, ref_type, ref_flags);
2656 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2659 else
2661 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2662 ref_type, ref_flags);
2667 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2668 covered by the outer mode is smaller than that covered by the inner mode,
2669 is a read-modify-write operation.
2670 This function returns true iff the SUBREG X is such a SUBREG. */
2672 bool
2673 df_read_modify_subreg_p (rtx x)
2675 unsigned int isize, osize;
2676 if (GET_CODE (x) != SUBREG)
2677 return false;
2678 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2679 osize = GET_MODE_SIZE (GET_MODE (x));
2680 return isize > osize
2681 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2685 /* Process all the registers defined in the rtx pointed by LOC.
2686 Autoincrement/decrement definitions will be picked up by df_uses_record.
2687 Any change here has to be matched in df_find_hard_reg_defs_1. */
2689 static void
2690 df_def_record_1 (struct df_collection_rec *collection_rec,
2691 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2692 int flags)
2694 rtx dst = *loc;
2696 /* It is legal to have a set destination be a parallel. */
2697 if (GET_CODE (dst) == PARALLEL)
2699 int i;
2700 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2702 rtx temp = XVECEXP (dst, 0, i);
2703 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2704 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2705 bb, insn_info, flags);
2707 return;
2710 if (GET_CODE (dst) == STRICT_LOW_PART)
2712 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2714 loc = &XEXP (dst, 0);
2715 dst = *loc;
2718 if (GET_CODE (dst) == ZERO_EXTRACT)
2720 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2722 loc = &XEXP (dst, 0);
2723 dst = *loc;
2726 /* At this point if we do not have a reg or a subreg, just return. */
2727 if (REG_P (dst))
2729 df_ref_record (DF_REF_REGULAR, collection_rec,
2730 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2732 /* We want to keep sp alive everywhere - by making all
2733 writes to sp also use of sp. */
2734 if (REGNO (dst) == STACK_POINTER_REGNUM)
2735 df_ref_record (DF_REF_BASE, collection_rec,
2736 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2738 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2740 if (df_read_modify_subreg_p (dst))
2741 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2743 flags |= DF_REF_SUBREG;
2745 df_ref_record (DF_REF_REGULAR, collection_rec,
2746 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2751 /* Process all the registers defined in the pattern rtx, X. Any change
2752 here has to be matched in df_find_hard_reg_defs. */
2754 static void
2755 df_defs_record (struct df_collection_rec *collection_rec,
2756 rtx x, basic_block bb, struct df_insn_info *insn_info,
2757 int flags)
2759 RTX_CODE code = GET_CODE (x);
2760 int i;
2762 switch (code)
2764 case SET:
2765 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2766 break;
2768 case CLOBBER:
2769 flags |= DF_REF_MUST_CLOBBER;
2770 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2771 break;
2773 case COND_EXEC:
2774 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2775 bb, insn_info, DF_REF_CONDITIONAL);
2776 break;
2778 case PARALLEL:
2779 for (i = 0; i < XVECLEN (x, 0); i++)
2780 df_defs_record (collection_rec, XVECEXP (x, 0, i),
2781 bb, insn_info, flags);
2782 break;
2783 default:
2784 /* No DEFs to record in other cases */
2785 break;
2789 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2790 destination of a set or clobber. This has to match the logic in
2791 df_defs_record_1. */
2793 static void
2794 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2796 /* It is legal to have a set destination be a parallel. */
2797 if (GET_CODE (dst) == PARALLEL)
2799 int i;
2800 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2802 rtx temp = XVECEXP (dst, 0, i);
2803 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2804 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2806 return;
2809 if (GET_CODE (dst) == STRICT_LOW_PART)
2810 dst = XEXP (dst, 0);
2812 if (GET_CODE (dst) == ZERO_EXTRACT)
2813 dst = XEXP (dst, 0);
2815 /* At this point if we do not have a reg or a subreg, just return. */
2816 if (REG_P (dst) && HARD_REGISTER_P (dst))
2817 SET_HARD_REG_BIT (*defs, REGNO (dst));
2818 else if (GET_CODE (dst) == SUBREG
2819 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2820 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2823 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2824 has to match the logic in df_defs_record. */
2826 static void
2827 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2829 RTX_CODE code = GET_CODE (x);
2830 int i;
2832 switch (code)
2834 case SET:
2835 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2836 break;
2838 case CLOBBER:
2839 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2840 break;
2842 case COND_EXEC:
2843 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2844 break;
2846 case PARALLEL:
2847 for (i = 0; i < XVECLEN (x, 0); i++)
2848 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2849 break;
2850 default:
2851 /* No DEFs to record in other cases */
2852 break;
2857 /* Process all the registers used in the rtx at address LOC. */
2859 static void
2860 df_uses_record (struct df_collection_rec *collection_rec,
2861 rtx *loc, enum df_ref_type ref_type,
2862 basic_block bb, struct df_insn_info *insn_info,
2863 int flags)
2865 RTX_CODE code;
2866 rtx x;
2868 retry:
2869 x = *loc;
2870 if (!x)
2871 return;
2872 code = GET_CODE (x);
2873 switch (code)
2875 case LABEL_REF:
2876 case SYMBOL_REF:
2877 case CONST:
2878 CASE_CONST_ANY:
2879 case PC:
2880 case CC0:
2881 case ADDR_VEC:
2882 case ADDR_DIFF_VEC:
2883 return;
2885 case CLOBBER:
2886 /* If we are clobbering a MEM, mark any registers inside the address
2887 as being used. */
2888 if (MEM_P (XEXP (x, 0)))
2889 df_uses_record (collection_rec,
2890 &XEXP (XEXP (x, 0), 0),
2891 DF_REF_REG_MEM_STORE,
2892 bb, insn_info,
2893 flags);
2895 /* If we're clobbering a REG then we have a def so ignore. */
2896 return;
2898 case MEM:
2899 df_uses_record (collection_rec,
2900 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2901 bb, insn_info, flags & DF_REF_IN_NOTE);
2902 return;
2904 case SUBREG:
2905 /* While we're here, optimize this case. */
2906 flags |= DF_REF_PARTIAL;
2907 /* In case the SUBREG is not of a REG, do not optimize. */
2908 if (!REG_P (SUBREG_REG (x)))
2910 loc = &SUBREG_REG (x);
2911 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2912 return;
2914 /* ... Fall through ... */
2916 case REG:
2917 df_ref_record (DF_REF_REGULAR, collection_rec,
2918 x, loc, bb, insn_info,
2919 ref_type, flags);
2920 return;
2922 case SIGN_EXTRACT:
2923 case ZERO_EXTRACT:
2925 df_uses_record (collection_rec,
2926 &XEXP (x, 1), ref_type, bb, insn_info, flags);
2927 df_uses_record (collection_rec,
2928 &XEXP (x, 2), ref_type, bb, insn_info, flags);
2930 /* If the parameters to the zero or sign extract are
2931 constants, strip them off and recurse, otherwise there is
2932 no information that we can gain from this operation. */
2933 if (code == ZERO_EXTRACT)
2934 flags |= DF_REF_ZERO_EXTRACT;
2935 else
2936 flags |= DF_REF_SIGN_EXTRACT;
2938 df_uses_record (collection_rec,
2939 &XEXP (x, 0), ref_type, bb, insn_info, flags);
2940 return;
2942 break;
2944 case SET:
2946 rtx dst = SET_DEST (x);
2947 gcc_assert (!(flags & DF_REF_IN_NOTE));
2948 df_uses_record (collection_rec,
2949 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2951 switch (GET_CODE (dst))
2953 case SUBREG:
2954 if (df_read_modify_subreg_p (dst))
2956 df_uses_record (collection_rec, &SUBREG_REG (dst),
2957 DF_REF_REG_USE, bb, insn_info,
2958 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2959 break;
2961 /* Fall through. */
2962 case REG:
2963 case PARALLEL:
2964 case SCRATCH:
2965 case PC:
2966 case CC0:
2967 break;
2968 case MEM:
2969 df_uses_record (collection_rec, &XEXP (dst, 0),
2970 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2971 break;
2972 case STRICT_LOW_PART:
2974 rtx *temp = &XEXP (dst, 0);
2975 /* A strict_low_part uses the whole REG and not just the
2976 SUBREG. */
2977 dst = XEXP (dst, 0);
2978 df_uses_record (collection_rec,
2979 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2980 DF_REF_REG_USE, bb, insn_info,
2981 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2983 break;
2984 case ZERO_EXTRACT:
2986 df_uses_record (collection_rec, &XEXP (dst, 1),
2987 DF_REF_REG_USE, bb, insn_info, flags);
2988 df_uses_record (collection_rec, &XEXP (dst, 2),
2989 DF_REF_REG_USE, bb, insn_info, flags);
2990 if (GET_CODE (XEXP (dst,0)) == MEM)
2991 df_uses_record (collection_rec, &XEXP (dst, 0),
2992 DF_REF_REG_USE, bb, insn_info,
2993 flags);
2994 else
2995 df_uses_record (collection_rec, &XEXP (dst, 0),
2996 DF_REF_REG_USE, bb, insn_info,
2997 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2999 break;
3001 default:
3002 gcc_unreachable ();
3004 return;
3007 case RETURN:
3008 case SIMPLE_RETURN:
3009 break;
3011 case ASM_OPERANDS:
3012 case UNSPEC_VOLATILE:
3013 case TRAP_IF:
3014 case ASM_INPUT:
3016 /* Traditional and volatile asm instructions must be
3017 considered to use and clobber all hard registers, all
3018 pseudo-registers and all of memory. So must TRAP_IF and
3019 UNSPEC_VOLATILE operations.
3021 Consider for instance a volatile asm that changes the fpu
3022 rounding mode. An insn should not be moved across this
3023 even if it only uses pseudo-regs because it might give an
3024 incorrectly rounded result.
3026 However, flow.c's liveness computation did *not* do this,
3027 giving the reasoning as " ?!? Unfortunately, marking all
3028 hard registers as live causes massive problems for the
3029 register allocator and marking all pseudos as live creates
3030 mountains of uninitialized variable warnings."
3032 In order to maintain the status quo with regard to liveness
3033 and uses, we do what flow.c did and just mark any regs we
3034 can find in ASM_OPERANDS as used. In global asm insns are
3035 scanned and regs_asm_clobbered is filled out.
3037 For all ASM_OPERANDS, we must traverse the vector of input
3038 operands. We can not just fall through here since then we
3039 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3040 which do not indicate traditional asms unlike their normal
3041 usage. */
3042 if (code == ASM_OPERANDS)
3044 int j;
3046 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3047 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
3048 DF_REF_REG_USE, bb, insn_info, flags);
3049 return;
3051 break;
3054 case VAR_LOCATION:
3055 df_uses_record (collection_rec,
3056 &PAT_VAR_LOCATION_LOC (x),
3057 DF_REF_REG_USE, bb, insn_info, flags);
3058 return;
3060 case PRE_DEC:
3061 case POST_DEC:
3062 case PRE_INC:
3063 case POST_INC:
3064 case PRE_MODIFY:
3065 case POST_MODIFY:
3066 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3067 /* Catch the def of the register being modified. */
3068 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3069 bb, insn_info,
3070 DF_REF_REG_DEF,
3071 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3073 /* ... Fall through to handle uses ... */
3075 default:
3076 break;
3079 /* Recursively scan the operands of this expression. */
3081 const char *fmt = GET_RTX_FORMAT (code);
3082 int i;
3084 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3086 if (fmt[i] == 'e')
3088 /* Tail recursive case: save a function call level. */
3089 if (i == 0)
3091 loc = &XEXP (x, 0);
3092 goto retry;
3094 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3095 bb, insn_info, flags);
3097 else if (fmt[i] == 'E')
3099 int j;
3100 for (j = 0; j < XVECLEN (x, i); j++)
3101 df_uses_record (collection_rec,
3102 &XVECEXP (x, i, j), ref_type,
3103 bb, insn_info, flags);
3108 return;
3112 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3114 static void
3115 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3117 unsigned int ix;
3118 df_ref ref;
3120 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3122 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3124 df_ref use;
3126 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3127 DF_REF_LOC (ref), DF_REF_BB (ref),
3128 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3129 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3130 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3136 /* Get call's extra defs and uses (track caller-saved registers). */
3138 static void
3139 df_get_call_refs (struct df_collection_rec *collection_rec,
3140 basic_block bb,
3141 struct df_insn_info *insn_info,
3142 int flags)
3144 rtx note;
3145 bool is_sibling_call;
3146 unsigned int i;
3147 HARD_REG_SET defs_generated;
3148 HARD_REG_SET fn_reg_set_usage;
3150 CLEAR_HARD_REG_SET (defs_generated);
3151 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3152 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3153 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3154 regs_invalidated_by_call);
3156 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3158 if (i == STACK_POINTER_REGNUM)
3159 /* The stack ptr is used (honorarily) by a CALL insn. */
3160 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3161 NULL, bb, insn_info, DF_REF_REG_USE,
3162 DF_REF_CALL_STACK_USAGE | flags);
3163 else if (global_regs[i])
3165 /* Calls to const functions cannot access any global registers and
3166 calls to pure functions cannot set them. All other calls may
3167 reference any of the global registers, so they are recorded as
3168 used. */
3169 if (!RTL_CONST_CALL_P (insn_info->insn))
3171 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3172 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3173 if (!RTL_PURE_CALL_P (insn_info->insn))
3174 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3175 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3178 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3179 /* no clobbers for regs that are the result of the call */
3180 && !TEST_HARD_REG_BIT (defs_generated, i)
3181 && (!is_sibling_call
3182 || !bitmap_bit_p (df->exit_block_uses, i)
3183 || refers_to_regno_p (i, crtl->return_rtx)))
3184 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3185 NULL, bb, insn_info, DF_REF_REG_DEF,
3186 DF_REF_MAY_CLOBBER | flags);
3189 /* Record the registers used to pass arguments, and explicitly
3190 noted as clobbered. */
3191 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3192 note = XEXP (note, 1))
3194 if (GET_CODE (XEXP (note, 0)) == USE)
3195 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3196 DF_REF_REG_USE, bb, insn_info, flags);
3197 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3199 if (REG_P (XEXP (XEXP (note, 0), 0)))
3201 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3202 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3203 df_defs_record (collection_rec, XEXP (note, 0), bb,
3204 insn_info, flags);
3206 else
3207 df_uses_record (collection_rec, &XEXP (note, 0),
3208 DF_REF_REG_USE, bb, insn_info, flags);
3212 return;
3215 /* Collect all refs in the INSN. This function is free of any
3216 side-effect - it will create and return a lists of df_ref's in the
3217 COLLECTION_REC without putting those refs into existing ref chains
3218 and reg chains. */
3220 static void
3221 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3222 basic_block bb, struct df_insn_info *insn_info)
3224 rtx note;
3225 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3227 /* Clear out the collection record. */
3228 collection_rec->def_vec.truncate (0);
3229 collection_rec->use_vec.truncate (0);
3230 collection_rec->eq_use_vec.truncate (0);
3231 collection_rec->mw_vec.truncate (0);
3233 /* Process REG_EQUIV/REG_EQUAL notes. */
3234 for (note = REG_NOTES (insn_info->insn); note;
3235 note = XEXP (note, 1))
3237 switch (REG_NOTE_KIND (note))
3239 case REG_EQUIV:
3240 case REG_EQUAL:
3241 df_uses_record (collection_rec,
3242 &XEXP (note, 0), DF_REF_REG_USE,
3243 bb, insn_info, DF_REF_IN_NOTE);
3244 break;
3245 case REG_NON_LOCAL_GOTO:
3246 /* The frame ptr is used by a non-local goto. */
3247 df_ref_record (DF_REF_BASE, collection_rec,
3248 regno_reg_rtx[FRAME_POINTER_REGNUM],
3249 NULL, bb, insn_info,
3250 DF_REF_REG_USE, 0);
3251 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3252 df_ref_record (DF_REF_BASE, collection_rec,
3253 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3254 NULL, bb, insn_info,
3255 DF_REF_REG_USE, 0);
3256 break;
3257 default:
3258 break;
3262 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3263 uses from CALL_INSN_FUNCTION_USAGE. */
3264 if (CALL_P (insn_info->insn))
3265 df_get_call_refs (collection_rec, bb, insn_info,
3266 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3268 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3269 that a qsort on the defs is unnecessary in most cases. */
3270 df_defs_record (collection_rec,
3271 PATTERN (insn_info->insn), bb, insn_info, 0);
3273 /* Record the register uses. */
3274 df_uses_record (collection_rec,
3275 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3277 /* DF_REF_CONDITIONAL needs corresponding USES. */
3278 if (is_cond_exec)
3279 df_get_conditional_uses (collection_rec);
3281 df_canonize_collection_rec (collection_rec);
3284 /* Recompute the luids for the insns in BB. */
3286 void
3287 df_recompute_luids (basic_block bb)
3289 rtx_insn *insn;
3290 int luid = 0;
3292 df_grow_insn_info ();
3294 /* Scan the block an insn at a time from beginning to end. */
3295 FOR_BB_INSNS (bb, insn)
3297 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3298 /* Inserting labels does not always trigger the incremental
3299 rescanning. */
3300 if (!insn_info)
3302 gcc_assert (!INSN_P (insn));
3303 insn_info = df_insn_create_insn_record (insn);
3306 DF_INSN_INFO_LUID (insn_info) = luid;
3307 if (INSN_P (insn))
3308 luid++;
3313 /* Collect all artificial refs at the block level for BB and add them
3314 to COLLECTION_REC. */
3316 static void
3317 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3319 collection_rec->def_vec.truncate (0);
3320 collection_rec->use_vec.truncate (0);
3321 collection_rec->eq_use_vec.truncate (0);
3322 collection_rec->mw_vec.truncate (0);
3324 if (bb->index == ENTRY_BLOCK)
3326 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3327 return;
3329 else if (bb->index == EXIT_BLOCK)
3331 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3332 return;
3335 if (bb_has_eh_pred (bb))
3337 unsigned int i;
3338 /* Mark the registers that will contain data for the handler. */
3339 for (i = 0; ; ++i)
3341 unsigned regno = EH_RETURN_DATA_REGNO (i);
3342 if (regno == INVALID_REGNUM)
3343 break;
3344 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3345 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3349 /* Add the hard_frame_pointer if this block is the target of a
3350 non-local goto. */
3351 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3352 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3353 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3355 /* Add the artificial uses. */
3356 if (bb->index >= NUM_FIXED_BLOCKS)
3358 bitmap_iterator bi;
3359 unsigned int regno;
3360 bitmap au = bb_has_eh_pred (bb)
3361 ? &df->eh_block_artificial_uses
3362 : &df->regular_block_artificial_uses;
3364 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3366 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3367 bb, NULL, DF_REF_REG_USE, 0);
3371 df_canonize_collection_rec (collection_rec);
3375 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3377 void
3378 df_bb_refs_record (int bb_index, bool scan_insns)
3380 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3381 rtx_insn *insn;
3382 int luid = 0;
3384 if (!df)
3385 return;
3387 df_collection_rec collection_rec;
3388 df_grow_bb_info (df_scan);
3389 if (scan_insns)
3390 /* Scan the block an insn at a time from beginning to end. */
3391 FOR_BB_INSNS (bb, insn)
3393 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3394 gcc_assert (!insn_info);
3396 insn_info = df_insn_create_insn_record (insn);
3397 if (INSN_P (insn))
3399 /* Record refs within INSN. */
3400 DF_INSN_INFO_LUID (insn_info) = luid++;
3401 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3402 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3404 DF_INSN_INFO_LUID (insn_info) = luid;
3407 /* Other block level artificial refs */
3408 df_bb_refs_collect (&collection_rec, bb);
3409 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3411 /* Now that the block has been processed, set the block as dirty so
3412 LR and LIVE will get it processed. */
3413 df_set_bb_dirty (bb);
3417 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3418 block. */
3420 static void
3421 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3423 #ifdef EH_USES
3424 unsigned int i;
3425 #endif
3427 bitmap_clear (regular_block_artificial_uses);
3429 if (reload_completed)
3431 if (frame_pointer_needed)
3432 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3434 else
3435 /* Before reload, there are a few registers that must be forced
3436 live everywhere -- which might not already be the case for
3437 blocks within infinite loops. */
3439 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3441 /* Any reference to any pseudo before reload is a potential
3442 reference of the frame pointer. */
3443 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3445 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3446 bitmap_set_bit (regular_block_artificial_uses,
3447 HARD_FRAME_POINTER_REGNUM);
3449 /* Pseudos with argument area equivalences may require
3450 reloading via the argument pointer. */
3451 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3452 && fixed_regs[ARG_POINTER_REGNUM])
3453 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3455 /* Any constant, or pseudo with constant equivalences, may
3456 require reloading from memory using the pic register. */
3457 if (picreg != INVALID_REGNUM
3458 && fixed_regs[picreg])
3459 bitmap_set_bit (regular_block_artificial_uses, picreg);
3461 /* The all-important stack pointer must always be live. */
3462 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3464 #ifdef EH_USES
3465 /* EH_USES registers are used:
3466 1) at all insns that might throw (calls or with -fnon-call-exceptions
3467 trapping insns)
3468 2) in all EH edges
3469 3) to support backtraces and/or debugging, anywhere between their
3470 initialization and where they the saved registers are restored
3471 from them, including the cases where we don't reach the epilogue
3472 (noreturn call or infinite loop). */
3473 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3474 if (EH_USES (i))
3475 bitmap_set_bit (regular_block_artificial_uses, i);
3476 #endif
3480 /* Get the artificial use set for an eh block. */
3482 static void
3483 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3485 bitmap_clear (eh_block_artificial_uses);
3487 /* The following code (down through the arg_pointer setting APPEARS
3488 to be necessary because there is nothing that actually
3489 describes what the exception handling code may actually need
3490 to keep alive. */
3491 if (reload_completed)
3493 if (frame_pointer_needed)
3495 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3496 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3497 bitmap_set_bit (eh_block_artificial_uses,
3498 HARD_FRAME_POINTER_REGNUM);
3500 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3501 && fixed_regs[ARG_POINTER_REGNUM])
3502 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3508 /*----------------------------------------------------------------------------
3509 Specialized hard register scanning functions.
3510 ----------------------------------------------------------------------------*/
3513 /* Mark a register in SET. Hard registers in large modes get all
3514 of their component registers set as well. */
3516 static void
3517 df_mark_reg (rtx reg, void *vset)
3519 bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3523 /* Set the bit for regs that are considered being defined at the entry. */
3525 static void
3526 df_get_entry_block_def_set (bitmap entry_block_defs)
3528 rtx r;
3529 int i;
3531 bitmap_clear (entry_block_defs);
3533 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3535 if (global_regs[i])
3536 bitmap_set_bit (entry_block_defs, i);
3537 if (FUNCTION_ARG_REGNO_P (i))
3538 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3541 /* The always important stack pointer. */
3542 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3544 /* Once the prologue has been generated, all of these registers
3545 should just show up in the first regular block. */
3546 if (HAVE_prologue && epilogue_completed)
3548 /* Defs for the callee saved registers are inserted so that the
3549 pushes have some defining location. */
3550 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3551 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3552 bitmap_set_bit (entry_block_defs, i);
3555 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3556 if (r && REG_P (r))
3557 bitmap_set_bit (entry_block_defs, REGNO (r));
3559 /* If the function has an incoming STATIC_CHAIN, it has to show up
3560 in the entry def set. */
3561 r = targetm.calls.static_chain (current_function_decl, true);
3562 if (r && REG_P (r))
3563 bitmap_set_bit (entry_block_defs, REGNO (r));
3565 if ((!reload_completed) || frame_pointer_needed)
3567 /* Any reference to any pseudo before reload is a potential
3568 reference of the frame pointer. */
3569 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3571 /* If they are different, also mark the hard frame pointer as live. */
3572 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3573 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3574 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3577 /* These registers are live everywhere. */
3578 if (!reload_completed)
3580 /* Pseudos with argument area equivalences may require
3581 reloading via the argument pointer. */
3582 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3583 && fixed_regs[ARG_POINTER_REGNUM])
3584 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3586 /* Any constant, or pseudo with constant equivalences, may
3587 require reloading from memory using the pic register. */
3588 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3589 if (picreg != INVALID_REGNUM
3590 && fixed_regs[picreg])
3591 bitmap_set_bit (entry_block_defs, picreg);
3594 #ifdef INCOMING_RETURN_ADDR_RTX
3595 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3596 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3597 #endif
3599 targetm.extra_live_on_entry (entry_block_defs);
3603 /* Return the (conservative) set of hard registers that are defined on
3604 entry to the function.
3605 It uses df->entry_block_defs to determine which register
3606 reference to include. */
3608 static void
3609 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3610 bitmap entry_block_defs)
3612 unsigned int i;
3613 bitmap_iterator bi;
3615 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3617 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3618 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3621 df_canonize_collection_rec (collection_rec);
3625 /* Record the (conservative) set of hard registers that are defined on
3626 entry to the function. */
3628 static void
3629 df_record_entry_block_defs (bitmap entry_block_defs)
3631 struct df_collection_rec collection_rec;
3632 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3634 /* Process bb_refs chain */
3635 df_refs_add_to_chains (&collection_rec,
3636 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3637 NULL,
3638 copy_defs);
3642 /* Update the defs in the entry block. */
3644 void
3645 df_update_entry_block_defs (void)
3647 bitmap_head refs;
3648 bool changed = false;
3650 bitmap_initialize (&refs, &df_bitmap_obstack);
3651 df_get_entry_block_def_set (&refs);
3652 if (df->entry_block_defs)
3654 if (!bitmap_equal_p (df->entry_block_defs, &refs))
3656 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3657 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3658 df_ref_chain_delete (bb_info->artificial_defs);
3659 bb_info->artificial_defs = NULL;
3660 changed = true;
3663 else
3665 struct df_scan_problem_data *problem_data
3666 = (struct df_scan_problem_data *) df_scan->problem_data;
3667 gcc_unreachable ();
3668 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3669 changed = true;
3672 if (changed)
3674 df_record_entry_block_defs (&refs);
3675 bitmap_copy (df->entry_block_defs, &refs);
3676 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3678 bitmap_clear (&refs);
3682 /* Set the bit for regs that are considered being used at the exit. */
3684 static void
3685 df_get_exit_block_use_set (bitmap exit_block_uses)
3687 unsigned int i;
3688 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3690 bitmap_clear (exit_block_uses);
3692 /* Stack pointer is always live at the exit. */
3693 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3695 /* Mark the frame pointer if needed at the end of the function.
3696 If we end up eliminating it, it will be removed from the live
3697 list of each basic block by reload. */
3699 if ((!reload_completed) || frame_pointer_needed)
3701 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3703 /* If they are different, also mark the hard frame pointer as live. */
3704 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3705 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3706 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3709 /* Many architectures have a GP register even without flag_pic.
3710 Assume the pic register is not in use, or will be handled by
3711 other means, if it is not fixed. */
3712 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3713 && picreg != INVALID_REGNUM
3714 && fixed_regs[picreg])
3715 bitmap_set_bit (exit_block_uses, picreg);
3717 /* Mark all global registers, and all registers used by the
3718 epilogue as being live at the end of the function since they
3719 may be referenced by our caller. */
3720 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3721 if (global_regs[i] || EPILOGUE_USES (i))
3722 bitmap_set_bit (exit_block_uses, i);
3724 if (HAVE_epilogue && epilogue_completed)
3726 /* Mark all call-saved registers that we actually used. */
3727 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3728 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3729 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3730 bitmap_set_bit (exit_block_uses, i);
3733 /* Mark the registers that will contain data for the handler. */
3734 if (reload_completed && crtl->calls_eh_return)
3735 for (i = 0; ; ++i)
3737 unsigned regno = EH_RETURN_DATA_REGNO (i);
3738 if (regno == INVALID_REGNUM)
3739 break;
3740 bitmap_set_bit (exit_block_uses, regno);
3743 #ifdef EH_RETURN_STACKADJ_RTX
3744 if ((!HAVE_epilogue || ! epilogue_completed)
3745 && crtl->calls_eh_return)
3747 rtx tmp = EH_RETURN_STACKADJ_RTX;
3748 if (tmp && REG_P (tmp))
3749 df_mark_reg (tmp, exit_block_uses);
3751 #endif
3753 #ifdef EH_RETURN_HANDLER_RTX
3754 if ((!HAVE_epilogue || ! epilogue_completed)
3755 && crtl->calls_eh_return)
3757 rtx tmp = EH_RETURN_HANDLER_RTX;
3758 if (tmp && REG_P (tmp))
3759 df_mark_reg (tmp, exit_block_uses);
3761 #endif
3763 /* Mark function return value. */
3764 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3768 /* Return the refs of hard registers that are used in the exit block.
3769 It uses df->exit_block_uses to determine register to include. */
3771 static void
3772 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3774 unsigned int i;
3775 bitmap_iterator bi;
3777 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3778 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3779 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3781 /* It is deliberate that this is not put in the exit block uses but
3782 I do not know why. */
3783 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3784 && reload_completed
3785 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3786 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3787 && fixed_regs[ARG_POINTER_REGNUM])
3788 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3789 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3791 df_canonize_collection_rec (collection_rec);
3795 /* Record the set of hard registers that are used in the exit block.
3796 It uses df->exit_block_uses to determine which bit to include. */
3798 static void
3799 df_record_exit_block_uses (bitmap exit_block_uses)
3801 struct df_collection_rec collection_rec;
3802 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3804 /* Process bb_refs chain */
3805 df_refs_add_to_chains (&collection_rec,
3806 BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3807 NULL,
3808 copy_uses);
3812 /* Update the uses in the exit block. */
3814 void
3815 df_update_exit_block_uses (void)
3817 bitmap_head refs;
3818 bool changed = false;
3820 bitmap_initialize (&refs, &df_bitmap_obstack);
3821 df_get_exit_block_use_set (&refs);
3822 if (df->exit_block_uses)
3824 if (!bitmap_equal_p (df->exit_block_uses, &refs))
3826 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3827 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3828 df_ref_chain_delete (bb_info->artificial_uses);
3829 bb_info->artificial_uses = NULL;
3830 changed = true;
3833 else
3835 struct df_scan_problem_data *problem_data
3836 = (struct df_scan_problem_data *) df_scan->problem_data;
3837 gcc_unreachable ();
3838 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3839 changed = true;
3842 if (changed)
3844 df_record_exit_block_uses (&refs);
3845 bitmap_copy (df->exit_block_uses,& refs);
3846 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3848 bitmap_clear (&refs);
3851 static bool initialized = false;
3854 /* Initialize some platform specific structures. */
3856 void
3857 df_hard_reg_init (void)
3859 #ifdef ELIMINABLE_REGS
3860 int i;
3861 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3862 #endif
3863 if (initialized)
3864 return;
3866 /* Record which registers will be eliminated. We use this in
3867 mark_used_regs. */
3868 CLEAR_HARD_REG_SET (elim_reg_set);
3870 #ifdef ELIMINABLE_REGS
3871 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3872 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3873 #else
3874 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3875 #endif
3877 initialized = true;
3881 /* Recompute the parts of scanning that are based on regs_ever_live
3882 because something changed in that array. */
3884 void
3885 df_update_entry_exit_and_calls (void)
3887 basic_block bb;
3889 df_update_entry_block_defs ();
3890 df_update_exit_block_uses ();
3892 /* The call insns need to be rescanned because there may be changes
3893 in the set of registers clobbered across the call. */
3894 FOR_EACH_BB_FN (bb, cfun)
3896 rtx_insn *insn;
3897 FOR_BB_INSNS (bb, insn)
3899 if (INSN_P (insn) && CALL_P (insn))
3900 df_insn_rescan (insn);
3906 /* Return true if hard REG is actually used in the some instruction.
3907 There are a fair number of conditions that affect the setting of
3908 this array. See the comment in df.h for df->hard_regs_live_count
3909 for the conditions that this array is set. */
3911 bool
3912 df_hard_reg_used_p (unsigned int reg)
3914 return df->hard_regs_live_count[reg] != 0;
3918 /* A count of the number of times REG is actually used in the some
3919 instruction. There are a fair number of conditions that affect the
3920 setting of this array. See the comment in df.h for
3921 df->hard_regs_live_count for the conditions that this array is
3922 set. */
3925 unsigned int
3926 df_hard_reg_used_count (unsigned int reg)
3928 return df->hard_regs_live_count[reg];
3932 /* Get the value of regs_ever_live[REGNO]. */
3934 bool
3935 df_regs_ever_live_p (unsigned int regno)
3937 return regs_ever_live[regno];
3941 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3942 to change, schedule that change for the next update. */
3944 void
3945 df_set_regs_ever_live (unsigned int regno, bool value)
3947 if (regs_ever_live[regno] == value)
3948 return;
3950 regs_ever_live[regno] = value;
3951 if (df)
3952 df->redo_entry_and_exit = true;
3956 /* Compute "regs_ever_live" information from the underlying df
3957 information. Set the vector to all false if RESET. */
3959 void
3960 df_compute_regs_ever_live (bool reset)
3962 unsigned int i;
3963 bool changed = df->redo_entry_and_exit;
3965 if (reset)
3966 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3968 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3969 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3971 regs_ever_live[i] = true;
3972 changed = true;
3974 if (changed)
3975 df_update_entry_exit_and_calls ();
3976 df->redo_entry_and_exit = false;
3980 /*----------------------------------------------------------------------------
3981 Dataflow ref information verification functions.
3983 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3984 df_reg_chain_verify_unmarked (refs)
3985 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3986 df_mws_verify (mw*, mw*, bool)
3987 df_insn_refs_verify (collection_rec, bb, insn, bool)
3988 df_bb_refs_verify (bb, refs, bool)
3989 df_bb_verify (bb)
3990 df_exit_block_bitmap_verify (bool)
3991 df_entry_block_bitmap_verify (bool)
3992 df_scan_verify ()
3993 ----------------------------------------------------------------------------*/
3996 /* Mark all refs in the reg chain. Verify that all of the registers
3997 are in the correct chain. */
3999 static unsigned int
4000 df_reg_chain_mark (df_ref refs, unsigned int regno,
4001 bool is_def, bool is_eq_use)
4003 unsigned int count = 0;
4004 df_ref ref;
4005 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4007 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4009 /* If there are no def-use or use-def chains, make sure that all
4010 of the chains are clear. */
4011 if (!df_chain)
4012 gcc_assert (!DF_REF_CHAIN (ref));
4014 /* Check to make sure the ref is in the correct chain. */
4015 gcc_assert (DF_REF_REGNO (ref) == regno);
4016 if (is_def)
4017 gcc_assert (DF_REF_REG_DEF_P (ref));
4018 else
4019 gcc_assert (!DF_REF_REG_DEF_P (ref));
4021 if (is_eq_use)
4022 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4023 else
4024 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4026 if (DF_REF_NEXT_REG (ref))
4027 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
4028 count++;
4029 DF_REF_REG_MARK (ref);
4031 return count;
4035 /* Verify that all of the registers in the chain are unmarked. */
4037 static void
4038 df_reg_chain_verify_unmarked (df_ref refs)
4040 df_ref ref;
4041 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4042 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4046 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4048 static bool
4049 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4050 bool abort_if_fail)
4052 unsigned int ix;
4053 df_ref new_ref;
4055 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4057 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4059 if (abort_if_fail)
4060 gcc_assert (0);
4061 else
4062 return false;
4065 /* Abort if fail is called from the function level verifier. If
4066 that is the context, mark this reg as being seem. */
4067 if (abort_if_fail)
4069 gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4070 DF_REF_REG_UNMARK (old_rec);
4073 old_rec = DF_REF_NEXT_LOC (old_rec);
4076 if (abort_if_fail)
4077 gcc_assert (old_rec == NULL);
4078 else
4079 return old_rec == NULL;
4080 return false;
4084 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4086 static bool
4087 df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec,
4088 struct df_mw_hardreg *old_rec,
4089 bool abort_if_fail)
4091 unsigned int ix;
4092 struct df_mw_hardreg *new_reg;
4094 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4096 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4098 if (abort_if_fail)
4099 gcc_assert (0);
4100 else
4101 return false;
4103 old_rec = DF_MWS_NEXT (old_rec);
4106 if (abort_if_fail)
4107 gcc_assert (old_rec == NULL);
4108 else
4109 return old_rec == NULL;
4110 return false;
4114 /* Return true if the existing insn refs information is complete and
4115 correct. Otherwise (i.e. if there's any missing or extra refs),
4116 return the correct df_ref chain in REFS_RETURN.
4118 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4119 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4120 verification mode instead of the whole function, so unmark
4121 everything.
4123 If ABORT_IF_FAIL is set, this function never returns false. */
4125 static bool
4126 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4127 basic_block bb,
4128 rtx_insn *insn,
4129 bool abort_if_fail)
4131 bool ret1, ret2, ret3, ret4;
4132 unsigned int uid = INSN_UID (insn);
4133 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4135 df_insn_refs_collect (collection_rec, bb, insn_info);
4137 /* Unfortunately we cannot opt out early if one of these is not
4138 right because the marks will not get cleared. */
4139 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4140 abort_if_fail);
4141 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4142 abort_if_fail);
4143 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4144 abort_if_fail);
4145 ret4 = df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4146 abort_if_fail);
4147 return (ret1 && ret2 && ret3 && ret4);
4151 /* Return true if all refs in the basic block are correct and complete.
4152 Due to df_ref_chain_verify, it will cause all refs
4153 that are verified to have DF_REF_MARK bit set. */
4155 static bool
4156 df_bb_verify (basic_block bb)
4158 rtx_insn *insn;
4159 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4160 struct df_collection_rec collection_rec;
4162 gcc_assert (bb_info);
4164 /* Scan the block, one insn at a time, from beginning to end. */
4165 FOR_BB_INSNS_REVERSE (bb, insn)
4167 if (!INSN_P (insn))
4168 continue;
4169 df_insn_refs_verify (&collection_rec, bb, insn, true);
4170 df_free_collection_rec (&collection_rec);
4173 /* Do the artificial defs and uses. */
4174 df_bb_refs_collect (&collection_rec, bb);
4175 df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4176 df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4177 df_free_collection_rec (&collection_rec);
4179 return true;
4183 /* Returns true if the entry block has correct and complete df_ref set.
4184 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4186 static bool
4187 df_entry_block_bitmap_verify (bool abort_if_fail)
4189 bitmap_head entry_block_defs;
4190 bool is_eq;
4192 bitmap_initialize (&entry_block_defs, &df_bitmap_obstack);
4193 df_get_entry_block_def_set (&entry_block_defs);
4195 is_eq = bitmap_equal_p (&entry_block_defs, df->entry_block_defs);
4197 if (!is_eq && abort_if_fail)
4199 fprintf (stderr, "entry_block_defs = ");
4200 df_print_regset (stderr, &entry_block_defs);
4201 fprintf (stderr, "df->entry_block_defs = ");
4202 df_print_regset (stderr, df->entry_block_defs);
4203 gcc_assert (0);
4206 bitmap_clear (&entry_block_defs);
4208 return is_eq;
4212 /* Returns true if the exit block has correct and complete df_ref set.
4213 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4215 static bool
4216 df_exit_block_bitmap_verify (bool abort_if_fail)
4218 bitmap_head exit_block_uses;
4219 bool is_eq;
4221 bitmap_initialize (&exit_block_uses, &df_bitmap_obstack);
4222 df_get_exit_block_use_set (&exit_block_uses);
4224 is_eq = bitmap_equal_p (&exit_block_uses, df->exit_block_uses);
4226 if (!is_eq && abort_if_fail)
4228 fprintf (stderr, "exit_block_uses = ");
4229 df_print_regset (stderr, &exit_block_uses);
4230 fprintf (stderr, "df->exit_block_uses = ");
4231 df_print_regset (stderr, df->exit_block_uses);
4232 gcc_assert (0);
4235 bitmap_clear (&exit_block_uses);
4237 return is_eq;
4241 /* Return true if df_ref information for all insns in all blocks are
4242 correct and complete. */
4244 void
4245 df_scan_verify (void)
4247 unsigned int i;
4248 basic_block bb;
4249 bitmap_head regular_block_artificial_uses;
4250 bitmap_head eh_block_artificial_uses;
4252 if (!df)
4253 return;
4255 /* Verification is a 4 step process. */
4257 /* (1) All of the refs are marked by going through the reg chains. */
4258 for (i = 0; i < DF_REG_SIZE (df); i++)
4260 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4261 == DF_REG_DEF_COUNT (i));
4262 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4263 == DF_REG_USE_COUNT (i));
4264 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4265 == DF_REG_EQ_USE_COUNT (i));
4268 /* (2) There are various bitmaps whose value may change over the
4269 course of the compilation. This step recomputes them to make
4270 sure that they have not slipped out of date. */
4271 bitmap_initialize (&regular_block_artificial_uses, &df_bitmap_obstack);
4272 bitmap_initialize (&eh_block_artificial_uses, &df_bitmap_obstack);
4274 df_get_regular_block_artificial_uses (&regular_block_artificial_uses);
4275 df_get_eh_block_artificial_uses (&eh_block_artificial_uses);
4277 bitmap_ior_into (&eh_block_artificial_uses,
4278 &regular_block_artificial_uses);
4280 /* Check artificial_uses bitmaps didn't change. */
4281 gcc_assert (bitmap_equal_p (&regular_block_artificial_uses,
4282 &df->regular_block_artificial_uses));
4283 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses,
4284 &df->eh_block_artificial_uses));
4286 bitmap_clear (&regular_block_artificial_uses);
4287 bitmap_clear (&eh_block_artificial_uses);
4289 /* Verify entry block and exit block. These only verify the bitmaps,
4290 the refs are verified in df_bb_verify. */
4291 df_entry_block_bitmap_verify (true);
4292 df_exit_block_bitmap_verify (true);
4294 /* (3) All of the insns in all of the blocks are traversed and the
4295 marks are cleared both in the artificial refs attached to the
4296 blocks and the real refs inside the insns. It is a failure to
4297 clear a mark that has not been set as this means that the ref in
4298 the block or insn was not in the reg chain. */
4300 FOR_ALL_BB_FN (bb, cfun)
4301 df_bb_verify (bb);
4303 /* (4) See if all reg chains are traversed a second time. This time
4304 a check is made that the marks are clear. A set mark would be a
4305 from a reg that is not in any insn or basic block. */
4307 for (i = 0; i < DF_REG_SIZE (df); i++)
4309 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4310 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4311 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));