projects / gcc.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
df.h (df_mw_hardreg, [...]): Add a link pointer.
[gcc.git] / gcc / df-scan.c
1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999-2014 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).
7
8 This file is part of GCC.
9
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.
14
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.
19
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/>. */
23
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 "function.h"
33 #include "regs.h"
34 #include "alloc-pool.h"
35 #include "flags.h"
36 #include "hard-reg-set.h"
37 #include "basic-block.h"
38 #include "sbitmap.h"
39 #include "bitmap.h"
40 #include "dumpfile.h"
41 #include "tree.h"
42 #include "target.h"
43 #include "target-def.h"
44 #include "df.h"
45 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
46
47
48 typedef struct df_mw_hardreg *df_mw_hardreg_ptr;
49
50
51 #ifndef HAVE_epilogue
52 #define HAVE_epilogue 0
53 #endif
54 #ifndef HAVE_prologue
55 #define HAVE_prologue 0
56 #endif
57 #ifndef HAVE_sibcall_epilogue
58 #define HAVE_sibcall_epilogue 0
59 #endif
60
61 #ifndef EPILOGUE_USES
62 #define EPILOGUE_USES(REGNO) 0
63 #endif
64
65 /* The set of hard registers in eliminables[i].from. */
66
67 static HARD_REG_SET elim_reg_set;
68
69 /* Initialize ur_in and ur_out as if all hard registers were partially
70 available. */
71
72 struct df_collection_rec
73 {
74 auto_vec<df_ref, 128> def_vec;
75 auto_vec<df_ref, 32> use_vec;
76 auto_vec<df_ref, 32> eq_use_vec;
77 auto_vec<df_mw_hardreg_ptr, 32> mw_vec;
78 };
79
80 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
81 rtx, rtx *,
82 basic_block, struct df_insn_info *,
83 enum df_ref_type, int ref_flags);
84 static void df_def_record_1 (struct df_collection_rec *, rtx *,
85 basic_block, struct df_insn_info *,
86 int ref_flags);
87 static void df_defs_record (struct df_collection_rec *, rtx,
88 basic_block, struct df_insn_info *,
89 int ref_flags);
90 static void df_uses_record (struct df_collection_rec *,
91 rtx *, enum df_ref_type,
92 basic_block, struct df_insn_info *,
93 int ref_flags);
94
95 static void df_install_ref_incremental (df_ref);
96 static void df_insn_refs_collect (struct df_collection_rec*,
97 basic_block, struct df_insn_info *);
98 static void df_canonize_collection_rec (struct df_collection_rec *);
99
100 static void df_get_regular_block_artificial_uses (bitmap);
101 static void df_get_eh_block_artificial_uses (bitmap);
102
103 static void df_record_entry_block_defs (bitmap);
104 static void df_record_exit_block_uses (bitmap);
105 static void df_get_exit_block_use_set (bitmap);
106 static void df_get_entry_block_def_set (bitmap);
107 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
108 static void df_ref_chain_delete_du_chain (df_ref);
109 static void df_ref_chain_delete (df_ref);
110
111 static void df_refs_add_to_chains (struct df_collection_rec *,
112 basic_block, rtx, unsigned int);
113
114 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block, rtx, bool);
115 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
116 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
117 static void df_install_ref (df_ref, struct df_reg_info *,
118 struct df_ref_info *, bool);
119
120 static int df_ref_compare (df_ref, df_ref);
121 static int df_ref_ptr_compare (const void *, const void *);
122 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
123 static int df_mw_ptr_compare (const void *, const void *);
124
125 static void df_insn_info_delete (unsigned int);
126
127 /* Indexed by hardware reg number, is true if that register is ever
128 used in the current function.
129
130 In df-scan.c, this is set up to record the hard regs used
131 explicitly. Reload adds in the hard regs used for holding pseudo
132 regs. Final uses it to generate the code in the function prologue
133 and epilogue to save and restore registers as needed. */
134
135 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
136
137 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
138 static const unsigned int copy_defs = 0x1;
139 static const unsigned int copy_uses = 0x2;
140 static const unsigned int copy_eq_uses = 0x4;
141 static const unsigned int copy_mw = 0x8;
142 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
143 | copy_mw;
144 \f
145 /*----------------------------------------------------------------------------
146 SCANNING DATAFLOW PROBLEM
147
148 There are several ways in which scanning looks just like the other
149 dataflow problems. It shares the all the mechanisms for local info
150 as well as basic block info. Where it differs is when and how often
151 it gets run. It also has no need for the iterative solver.
152 ----------------------------------------------------------------------------*/
153
154 /* Problem data for the scanning dataflow function. */
155 struct df_scan_problem_data
156 {
157 alloc_pool ref_base_pool;
158 alloc_pool ref_artificial_pool;
159 alloc_pool ref_regular_pool;
160 alloc_pool insn_pool;
161 alloc_pool reg_pool;
162 alloc_pool mw_reg_pool;
163 bitmap_obstack reg_bitmaps;
164 bitmap_obstack insn_bitmaps;
165 };
166
167 typedef struct df_scan_bb_info *df_scan_bb_info_t;
168
169
170 /* Internal function to shut down the scanning problem. */
171 static void
172 df_scan_free_internal (void)
173 {
174 struct df_scan_problem_data *problem_data
175 = (struct df_scan_problem_data *) df_scan->problem_data;
176
177 free (df->def_info.refs);
178 free (df->def_info.begin);
179 free (df->def_info.count);
180 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
181
182 free (df->use_info.refs);
183 free (df->use_info.begin);
184 free (df->use_info.count);
185 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
186
187 free (df->def_regs);
188 df->def_regs = NULL;
189 free (df->use_regs);
190 df->use_regs = NULL;
191 free (df->eq_use_regs);
192 df->eq_use_regs = NULL;
193 df->regs_size = 0;
194 DF_REG_SIZE (df) = 0;
195
196 free (df->insns);
197 df->insns = NULL;
198 DF_INSN_SIZE () = 0;
199
200 free (df_scan->block_info);
201 df_scan->block_info = NULL;
202 df_scan->block_info_size = 0;
203
204 bitmap_clear (&df->hardware_regs_used);
205 bitmap_clear (&df->regular_block_artificial_uses);
206 bitmap_clear (&df->eh_block_artificial_uses);
207 BITMAP_FREE (df->entry_block_defs);
208 BITMAP_FREE (df->exit_block_uses);
209 bitmap_clear (&df->insns_to_delete);
210 bitmap_clear (&df->insns_to_rescan);
211 bitmap_clear (&df->insns_to_notes_rescan);
212
213 free_alloc_pool (problem_data->ref_base_pool);
214 free_alloc_pool (problem_data->ref_artificial_pool);
215 free_alloc_pool (problem_data->ref_regular_pool);
216 free_alloc_pool (problem_data->insn_pool);
217 free_alloc_pool (problem_data->reg_pool);
218 free_alloc_pool (problem_data->mw_reg_pool);
219 bitmap_obstack_release (&problem_data->reg_bitmaps);
220 bitmap_obstack_release (&problem_data->insn_bitmaps);
221 free (df_scan->problem_data);
222 }
223
224
225 /* Free basic block info. */
226
227 static void
228 df_scan_free_bb_info (basic_block bb, void *vbb_info)
229 {
230 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
231 unsigned int bb_index = bb->index;
232 rtx insn;
233
234 FOR_BB_INSNS (bb, insn)
235 if (INSN_P (insn))
236 df_insn_info_delete (INSN_UID (insn));
237
238 if (bb_index < df_scan->block_info_size)
239 bb_info = df_scan_get_bb_info (bb_index);
240
241 /* Get rid of any artificial uses or defs. */
242 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
243 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
244 df_ref_chain_delete (bb_info->artificial_defs);
245 df_ref_chain_delete (bb_info->artificial_uses);
246 bb_info->artificial_defs = NULL;
247 bb_info->artificial_uses = NULL;
248 }
249
250
251 /* Allocate the problem data for the scanning problem. This should be
252 called when the problem is created or when the entire function is to
253 be rescanned. */
254 void
255 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
256 {
257 struct df_scan_problem_data *problem_data;
258 unsigned int insn_num = get_max_uid () + 1;
259 unsigned int block_size = 512;
260 basic_block bb;
261
262 /* Given the number of pools, this is really faster than tearing
263 everything apart. */
264 if (df_scan->problem_data)
265 df_scan_free_internal ();
266
267 problem_data = XNEW (struct df_scan_problem_data);
268 df_scan->problem_data = problem_data;
269 df_scan->computed = true;
270
271 problem_data->ref_base_pool
272 = create_alloc_pool ("df_scan ref base",
273 sizeof (struct df_base_ref), block_size);
274 problem_data->ref_artificial_pool
275 = create_alloc_pool ("df_scan ref artificial",
276 sizeof (struct df_artificial_ref), block_size);
277 problem_data->ref_regular_pool
278 = create_alloc_pool ("df_scan ref regular",
279 sizeof (struct df_regular_ref), block_size);
280 problem_data->insn_pool
281 = create_alloc_pool ("df_scan insn",
282 sizeof (struct df_insn_info), block_size);
283 problem_data->reg_pool
284 = create_alloc_pool ("df_scan reg",
285 sizeof (struct df_reg_info), block_size);
286 problem_data->mw_reg_pool
287 = create_alloc_pool ("df_scan mw_reg",
288 sizeof (struct df_mw_hardreg), block_size / 16);
289
290 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
291 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
292
293 insn_num += insn_num / 4;
294 df_grow_reg_info ();
295
296 df_grow_insn_info ();
297 df_grow_bb_info (df_scan);
298
299 FOR_ALL_BB_FN (bb, cfun)
300 {
301 unsigned int bb_index = bb->index;
302 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
303 bb_info->artificial_defs = NULL;
304 bb_info->artificial_uses = NULL;
305 }
306
307 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
308 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
309 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
310 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
311 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
312 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
313 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
314 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
315 df_scan->optional_p = false;
316 }
317
318
319 /* Free all of the data associated with the scan problem. */
320
321 static void
322 df_scan_free (void)
323 {
324 if (df_scan->problem_data)
325 df_scan_free_internal ();
326
327 if (df->blocks_to_analyze)
328 {
329 BITMAP_FREE (df->blocks_to_analyze);
330 df->blocks_to_analyze = NULL;
331 }
332
333 free (df_scan);
334 }
335
336 /* Dump the preamble for DF_SCAN dump. */
337 static void
338 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
339 {
340 int i;
341 int dcount = 0;
342 int ucount = 0;
343 int ecount = 0;
344 int icount = 0;
345 int ccount = 0;
346 basic_block bb;
347 rtx insn;
348
349 fprintf (file, ";; invalidated by call \t");
350 df_print_regset (file, regs_invalidated_by_call_regset);
351 fprintf (file, ";; hardware regs used \t");
352 df_print_regset (file, &df->hardware_regs_used);
353 fprintf (file, ";; regular block artificial uses \t");
354 df_print_regset (file, &df->regular_block_artificial_uses);
355 fprintf (file, ";; eh block artificial uses \t");
356 df_print_regset (file, &df->eh_block_artificial_uses);
357 fprintf (file, ";; entry block defs \t");
358 df_print_regset (file, df->entry_block_defs);
359 fprintf (file, ";; exit block uses \t");
360 df_print_regset (file, df->exit_block_uses);
361 fprintf (file, ";; regs ever live \t");
362 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
363 if (df_regs_ever_live_p (i))
364 fprintf (file, " %d[%s]", i, reg_names[i]);
365 fprintf (file, "\n;; ref usage \t");
366
367 for (i = 0; i < (int)df->regs_inited; i++)
368 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
369 {
370 const char * sep = "";
371
372 fprintf (file, "r%d={", i);
373 if (DF_REG_DEF_COUNT (i))
374 {
375 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
376 sep = ",";
377 dcount += DF_REG_DEF_COUNT (i);
378 }
379 if (DF_REG_USE_COUNT (i))
380 {
381 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
382 sep = ",";
383 ucount += DF_REG_USE_COUNT (i);
384 }
385 if (DF_REG_EQ_USE_COUNT (i))
386 {
387 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
388 ecount += DF_REG_EQ_USE_COUNT (i);
389 }
390 fprintf (file, "} ");
391 }
392
393 FOR_EACH_BB_FN (bb, cfun)
394 FOR_BB_INSNS (bb, insn)
395 if (INSN_P (insn))
396 {
397 if (CALL_P (insn))
398 ccount++;
399 else
400 icount++;
401 }
402
403 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
404 " in %d{%d regular + %d call} insns.\n",
405 dcount + ucount + ecount, dcount, ucount, ecount,
406 icount + ccount, icount, ccount);
407 }
408
409 /* Dump the bb_info for a given basic block. */
410 static void
411 df_scan_start_block (basic_block bb, FILE *file)
412 {
413 struct df_scan_bb_info *bb_info
414 = df_scan_get_bb_info (bb->index);
415
416 if (bb_info)
417 {
418 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
419 df_refs_chain_dump (bb_info->artificial_defs, true, file);
420 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
421 df_refs_chain_dump (bb_info->artificial_uses, true, file);
422 fprintf (file, "\n");
423 }
424 #if 0
425 {
426 rtx insn;
427 FOR_BB_INSNS (bb, insn)
428 if (INSN_P (insn))
429 df_insn_debug (insn, false, file);
430 }
431 #endif
432 }
433
434 static struct df_problem problem_SCAN =
435 {
436 DF_SCAN, /* Problem id. */
437 DF_NONE, /* Direction. */
438 df_scan_alloc, /* Allocate the problem specific data. */
439 NULL, /* Reset global information. */
440 df_scan_free_bb_info, /* Free basic block info. */
441 NULL, /* Local compute function. */
442 NULL, /* Init the solution specific data. */
443 NULL, /* Iterative solver. */
444 NULL, /* Confluence operator 0. */
445 NULL, /* Confluence operator n. */
446 NULL, /* Transfer function. */
447 NULL, /* Finalize function. */
448 df_scan_free, /* Free all of the problem information. */
449 NULL, /* Remove this problem from the stack of dataflow problems. */
450 df_scan_start_dump, /* Debugging. */
451 df_scan_start_block, /* Debugging start block. */
452 NULL, /* Debugging end block. */
453 NULL, /* Debugging start insn. */
454 NULL, /* Debugging end insn. */
455 NULL, /* Incremental solution verify start. */
456 NULL, /* Incremental solution verify end. */
457 NULL, /* Dependent problem. */
458 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
459 TV_DF_SCAN, /* Timing variable. */
460 false /* Reset blocks on dropping out of blocks_to_analyze. */
461 };
462
463
464 /* Create a new DATAFLOW instance and add it to an existing instance
465 of DF. The returned structure is what is used to get at the
466 solution. */
467
468 void
469 df_scan_add_problem (void)
470 {
471 df_add_problem (&problem_SCAN);
472 }
473
474 \f
475 /*----------------------------------------------------------------------------
476 Storage Allocation Utilities
477 ----------------------------------------------------------------------------*/
478
479
480 /* First, grow the reg_info information. If the current size is less than
481 the number of pseudos, grow to 25% more than the number of
482 pseudos.
483
484 Second, assure that all of the slots up to max_reg_num have been
485 filled with reg_info structures. */
486
487 void
488 df_grow_reg_info (void)
489 {
490 unsigned int max_reg = max_reg_num ();
491 unsigned int new_size = max_reg;
492 struct df_scan_problem_data *problem_data
493 = (struct df_scan_problem_data *) df_scan->problem_data;
494 unsigned int i;
495
496 if (df->regs_size < new_size)
497 {
498 new_size += new_size / 4;
499 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
500 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
501 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
502 new_size);
503 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
504 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
505 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
506 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
507 df->regs_size = new_size;
508 }
509
510 for (i = df->regs_inited; i < max_reg; i++)
511 {
512 struct df_reg_info *reg_info;
513
514 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
515 memset (reg_info, 0, sizeof (struct df_reg_info));
516 df->def_regs[i] = reg_info;
517 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
518 memset (reg_info, 0, sizeof (struct df_reg_info));
519 df->use_regs[i] = reg_info;
520 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool);
521 memset (reg_info, 0, sizeof (struct df_reg_info));
522 df->eq_use_regs[i] = reg_info;
523 df->def_info.begin[i] = 0;
524 df->def_info.count[i] = 0;
525 df->use_info.begin[i] = 0;
526 df->use_info.count[i] = 0;
527 }
528
529 df->regs_inited = max_reg;
530 }
531
532
533 /* Grow the ref information. */
534
535 static void
536 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
537 {
538 if (ref_info->refs_size < new_size)
539 {
540 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
541 memset (ref_info->refs + ref_info->refs_size, 0,
542 (new_size - ref_info->refs_size) *sizeof (df_ref));
543 ref_info->refs_size = new_size;
544 }
545 }
546
547
548 /* Check and grow the ref information if necessary. This routine
549 guarantees total_size + BITMAP_ADDEND amount of entries in refs
550 array. It updates ref_info->refs_size only and does not change
551 ref_info->total_size. */
552
553 static void
554 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
555 unsigned bitmap_addend)
556 {
557 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
558 {
559 int new_size = ref_info->total_size + bitmap_addend;
560 new_size += ref_info->total_size / 4;
561 df_grow_ref_info (ref_info, new_size);
562 }
563 }
564
565
566 /* Grow the ref information. If the current size is less than the
567 number of instructions, grow to 25% more than the number of
568 instructions. */
569
570 void
571 df_grow_insn_info (void)
572 {
573 unsigned int new_size = get_max_uid () + 1;
574 if (DF_INSN_SIZE () < new_size)
575 {
576 new_size += new_size / 4;
577 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
578 memset (df->insns + df->insns_size, 0,
579 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
580 DF_INSN_SIZE () = new_size;
581 }
582 }
583
584
585
586 \f
587 /*----------------------------------------------------------------------------
588 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
589 ----------------------------------------------------------------------------*/
590
591 /* Rescan all of the block_to_analyze or all of the blocks in the
592 function if df_set_blocks if blocks_to_analyze is NULL; */
593
594 void
595 df_scan_blocks (void)
596 {
597 basic_block bb;
598
599 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
600 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
601
602 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
603 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
604
605 bitmap_ior_into (&df->eh_block_artificial_uses,
606 &df->regular_block_artificial_uses);
607
608 /* ENTRY and EXIT blocks have special defs/uses. */
609 df_get_entry_block_def_set (df->entry_block_defs);
610 df_record_entry_block_defs (df->entry_block_defs);
611 df_get_exit_block_use_set (df->exit_block_uses);
612 df_record_exit_block_uses (df->exit_block_uses);
613 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
614 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
615
616 /* Regular blocks */
617 FOR_EACH_BB_FN (bb, cfun)
618 {
619 unsigned int bb_index = bb->index;
620 df_bb_refs_record (bb_index, true);
621 }
622 }
623
624 /* Create new refs under address LOC within INSN. This function is
625 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
626 depending on whether LOC is inside PATTERN (INSN) or a note. */
627
628 void
629 df_uses_create (rtx *loc, rtx insn, int ref_flags)
630 {
631 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
632 df_uses_record (NULL, loc, DF_REF_REG_USE,
633 BLOCK_FOR_INSN (insn),
634 DF_INSN_INFO_GET (insn),
635 ref_flags);
636 }
637
638 static void
639 df_install_ref_incremental (df_ref ref)
640 {
641 struct df_reg_info **reg_info;
642 struct df_ref_info *ref_info;
643 df_ref *ref_ptr;
644 bool add_to_table;
645
646 rtx insn = DF_REF_INSN (ref);
647 basic_block bb = BLOCK_FOR_INSN (insn);
648
649 if (DF_REF_REG_DEF_P (ref))
650 {
651 reg_info = df->def_regs;
652 ref_info = &df->def_info;
653 ref_ptr = &DF_INSN_DEFS (insn);
654 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
655 }
656 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
657 {
658 reg_info = df->eq_use_regs;
659 ref_info = &df->use_info;
660 ref_ptr = &DF_INSN_EQ_USES (insn);
661 switch (ref_info->ref_order)
662 {
663 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
664 case DF_REF_ORDER_BY_REG_WITH_NOTES:
665 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
666 add_to_table = true;
667 break;
668 default:
669 add_to_table = false;
670 break;
671 }
672 }
673 else
674 {
675 reg_info = df->use_regs;
676 ref_info = &df->use_info;
677 ref_ptr = &DF_INSN_USES (insn);
678 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
679 }
680
681 /* Do not add if ref is not in the right blocks. */
682 if (add_to_table && df->analyze_subset)
683 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
684
685 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
686
687 if (add_to_table)
688 switch (ref_info->ref_order)
689 {
690 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
691 case DF_REF_ORDER_BY_REG_WITH_NOTES:
692 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
693 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
694 break;
695 default:
696 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
697 break;
698 }
699
700 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
701 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
702
703 DF_REF_NEXT_LOC (ref) = *ref_ptr;
704 *ref_ptr = ref;
705
706 #if 0
707 if (dump_file)
708 {
709 fprintf (dump_file, "adding ref ");
710 df_ref_debug (ref, dump_file);
711 }
712 #endif
713 /* By adding the ref directly, df_insn_rescan my not find any
714 differences even though the block will have changed. So we need
715 to mark the block dirty ourselves. */
716 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
717 df_set_bb_dirty (bb);
718 }
719
720
721 \f
722 /*----------------------------------------------------------------------------
723 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
724 ----------------------------------------------------------------------------*/
725
726 static void
727 df_free_ref (df_ref ref)
728 {
729 struct df_scan_problem_data *problem_data
730 = (struct df_scan_problem_data *) df_scan->problem_data;
731
732 switch (DF_REF_CLASS (ref))
733 {
734 case DF_REF_BASE:
735 pool_free (problem_data->ref_base_pool, ref);
736 break;
737
738 case DF_REF_ARTIFICIAL:
739 pool_free (problem_data->ref_artificial_pool, ref);
740 break;
741
742 case DF_REF_REGULAR:
743 pool_free (problem_data->ref_regular_pool, ref);
744 break;
745 }
746 }
747
748
749 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
750 Also delete the def-use or use-def chain if it exists. */
751
752 static void
753 df_reg_chain_unlink (df_ref ref)
754 {
755 df_ref next = DF_REF_NEXT_REG (ref);
756 df_ref prev = DF_REF_PREV_REG (ref);
757 int id = DF_REF_ID (ref);
758 struct df_reg_info *reg_info;
759 df_ref *refs = NULL;
760
761 if (DF_REF_REG_DEF_P (ref))
762 {
763 int regno = DF_REF_REGNO (ref);
764 reg_info = DF_REG_DEF_GET (regno);
765 refs = df->def_info.refs;
766 }
767 else
768 {
769 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
770 {
771 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
772 switch (df->use_info.ref_order)
773 {
774 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
775 case DF_REF_ORDER_BY_REG_WITH_NOTES:
776 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
777 refs = df->use_info.refs;
778 break;
779 default:
780 break;
781 }
782 }
783 else
784 {
785 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
786 refs = df->use_info.refs;
787 }
788 }
789
790 if (refs)
791 {
792 if (df->analyze_subset)
793 {
794 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
795 refs[id] = NULL;
796 }
797 else
798 refs[id] = NULL;
799 }
800
801 /* Delete any def-use or use-def chains that start here. It is
802 possible that there is trash in this field. This happens for
803 insns that have been deleted when rescanning has been deferred
804 and the chain problem has also been deleted. The chain tear down
805 code skips deleted insns. */
806 if (df_chain && DF_REF_CHAIN (ref))
807 df_chain_unlink (ref);
808
809 reg_info->n_refs--;
810 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
811 {
812 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
813 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
814 }
815
816 /* Unlink from the reg chain. If there is no prev, this is the
817 first of the list. If not, just join the next and prev. */
818 if (prev)
819 DF_REF_NEXT_REG (prev) = next;
820 else
821 {
822 gcc_assert (reg_info->reg_chain == ref);
823 reg_info->reg_chain = next;
824 }
825 if (next)
826 DF_REF_PREV_REG (next) = prev;
827
828 df_free_ref (ref);
829 }
830
831
832 /* Create the insn record for INSN. If there was one there, zero it
833 out. */
834
835 struct df_insn_info *
836 df_insn_create_insn_record (rtx insn)
837 {
838 struct df_scan_problem_data *problem_data
839 = (struct df_scan_problem_data *) df_scan->problem_data;
840 struct df_insn_info *insn_rec;
841
842 df_grow_insn_info ();
843 insn_rec = DF_INSN_INFO_GET (insn);
844 if (!insn_rec)
845 {
846 insn_rec = (struct df_insn_info *) pool_alloc (problem_data->insn_pool);
847 DF_INSN_INFO_SET (insn, insn_rec);
848 }
849 memset (insn_rec, 0, sizeof (struct df_insn_info));
850 insn_rec->insn = insn;
851 return insn_rec;
852 }
853
854
855 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
856
857 static void
858 df_ref_chain_delete_du_chain (df_ref ref)
859 {
860 for (; ref; ref = DF_REF_NEXT_LOC (ref))
861 /* CHAIN is allocated by DF_CHAIN. So make sure to
862 pass df_scan instance for the problem. */
863 if (DF_REF_CHAIN (ref))
864 df_chain_unlink (ref);
865 }
866
867
868 /* Delete all refs in the ref chain. */
869
870 static void
871 df_ref_chain_delete (df_ref ref)
872 {
873 df_ref next;
874 for (; ref; ref = next)
875 {
876 next = DF_REF_NEXT_LOC (ref);
877 df_reg_chain_unlink (ref);
878 }
879 }
880
881
882 /* Delete the hardreg chain. */
883
884 static void
885 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
886 {
887 struct df_scan_problem_data *problem_data
888 = (struct df_scan_problem_data *) df_scan->problem_data;
889 df_mw_hardreg *next;
890
891 for (; hardregs; hardregs = next)
892 {
893 next = DF_MWS_NEXT (hardregs);
894 pool_free (problem_data->mw_reg_pool, hardregs);
895 }
896 }
897
898
899 /* Delete all of the refs information from the insn with UID.
900 Internal helper for df_insn_delete, df_insn_rescan, and other
901 df-scan routines that don't have to work in deferred mode
902 and do not have to mark basic blocks for re-processing. */
903
904 static void
905 df_insn_info_delete (unsigned int uid)
906 {
907 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
908
909 bitmap_clear_bit (&df->insns_to_delete, uid);
910 bitmap_clear_bit (&df->insns_to_rescan, uid);
911 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
912 if (insn_info)
913 {
914 struct df_scan_problem_data *problem_data
915 = (struct df_scan_problem_data *) df_scan->problem_data;
916
917 /* In general, notes do not have the insn_info fields
918 initialized. However, combine deletes insns by changing them
919 to notes. How clever. So we cannot just check if it is a
920 valid insn before short circuiting this code, we need to see
921 if we actually initialized it. */
922 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
923
924 if (df_chain)
925 {
926 df_ref_chain_delete_du_chain (insn_info->defs);
927 df_ref_chain_delete_du_chain (insn_info->uses);
928 df_ref_chain_delete_du_chain (insn_info->eq_uses);
929 }
930
931 df_ref_chain_delete (insn_info->defs);
932 df_ref_chain_delete (insn_info->uses);
933 df_ref_chain_delete (insn_info->eq_uses);
934
935 pool_free (problem_data->insn_pool, insn_info);
936 DF_INSN_UID_SET (uid, NULL);
937 }
938 }
939
940 /* Delete all of the refs information from INSN, either right now
941 or marked for later in deferred mode. */
942
943 void
944 df_insn_delete (rtx insn)
945 {
946 unsigned int uid;
947 basic_block bb;
948
949 gcc_checking_assert (INSN_P (insn));
950
951 if (!df)
952 return;
953
954 uid = INSN_UID (insn);
955 bb = BLOCK_FOR_INSN (insn);
956
957 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
958 not exist anymore (as mentioned in df-core.c: "The only requirement
959 [for DF] is that there be a correct control flow graph." Clearly
960 that isn't the case after pass_free_cfg. But DF is freed much later
961 because some back-ends want to use DF info even though the CFG is
962 already gone. It's not clear to me whether that is safe, actually.
963 In any case, we expect BB to be non-NULL at least up to register
964 allocation, so disallow a non-NULL BB up to there. Not perfect
965 but better than nothing... */
966 gcc_checking_assert (bb != NULL || reload_completed);
967
968 df_grow_bb_info (df_scan);
969 df_grow_reg_info ();
970
971 /* The block must be marked as dirty now, rather than later as in
972 df_insn_rescan and df_notes_rescan because it may not be there at
973 rescanning time and the mark would blow up.
974 DEBUG_INSNs do not make a block's data flow solution dirty (at
975 worst the LUIDs are no longer contiguous). */
976 if (bb != NULL && NONDEBUG_INSN_P (insn))
977 df_set_bb_dirty (bb);
978
979 /* The client has deferred rescanning. */
980 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
981 {
982 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
983 if (insn_info)
984 {
985 bitmap_clear_bit (&df->insns_to_rescan, uid);
986 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
987 bitmap_set_bit (&df->insns_to_delete, uid);
988 }
989 if (dump_file)
990 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
991 return;
992 }
993
994 if (dump_file)
995 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
996
997 df_insn_info_delete (uid);
998 }
999
1000
1001 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
1002
1003 static void
1004 df_free_collection_rec (struct df_collection_rec *collection_rec)
1005 {
1006 unsigned int ix;
1007 struct df_scan_problem_data *problem_data
1008 = (struct df_scan_problem_data *) df_scan->problem_data;
1009 df_ref ref;
1010 struct df_mw_hardreg *mw;
1011
1012 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
1013 df_free_ref (ref);
1014 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
1015 df_free_ref (ref);
1016 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1017 df_free_ref (ref);
1018 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1019 pool_free (problem_data->mw_reg_pool, mw);
1020
1021 collection_rec->def_vec.release ();
1022 collection_rec->use_vec.release ();
1023 collection_rec->eq_use_vec.release ();
1024 collection_rec->mw_vec.release ();
1025 }
1026
1027 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1028
1029 bool
1030 df_insn_rescan (rtx insn)
1031 {
1032 unsigned int uid = INSN_UID (insn);
1033 struct df_insn_info *insn_info = NULL;
1034 basic_block bb = BLOCK_FOR_INSN (insn);
1035 struct df_collection_rec collection_rec;
1036
1037 if ((!df) || (!INSN_P (insn)))
1038 return false;
1039
1040 if (!bb)
1041 {
1042 if (dump_file)
1043 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1044 return false;
1045 }
1046
1047 /* The client has disabled rescanning and plans to do it itself. */
1048 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1049 return false;
1050
1051 df_grow_bb_info (df_scan);
1052 df_grow_reg_info ();
1053
1054 insn_info = DF_INSN_UID_SAFE_GET (uid);
1055
1056 /* The client has deferred rescanning. */
1057 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1058 {
1059 if (!insn_info)
1060 {
1061 insn_info = df_insn_create_insn_record (insn);
1062 insn_info->defs = 0;
1063 insn_info->uses = 0;
1064 insn_info->eq_uses = 0;
1065 insn_info->mw_hardregs = 0;
1066 }
1067 if (dump_file)
1068 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1069
1070 bitmap_clear_bit (&df->insns_to_delete, uid);
1071 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1072 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1073 return false;
1074 }
1075
1076 bitmap_clear_bit (&df->insns_to_delete, uid);
1077 bitmap_clear_bit (&df->insns_to_rescan, uid);
1078 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1079 if (insn_info)
1080 {
1081 int luid;
1082 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1083 /* If there's no change, return false. */
1084 if (the_same)
1085 {
1086 df_free_collection_rec (&collection_rec);
1087 if (dump_file)
1088 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1089 return false;
1090 }
1091 if (dump_file)
1092 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1093
1094 /* There's change - we need to delete the existing info.
1095 Since the insn isn't moved, we can salvage its LUID. */
1096 luid = DF_INSN_LUID (insn);
1097 df_insn_info_delete (uid);
1098 df_insn_create_insn_record (insn);
1099 DF_INSN_LUID (insn) = luid;
1100 }
1101 else
1102 {
1103 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1104 df_insn_refs_collect (&collection_rec, bb, insn_info);
1105 if (dump_file)
1106 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1107 }
1108
1109 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1110 if (!DEBUG_INSN_P (insn))
1111 df_set_bb_dirty (bb);
1112
1113 return true;
1114 }
1115
1116 /* Same as df_insn_rescan, but don't mark the basic block as
1117 dirty. */
1118
1119 bool
1120 df_insn_rescan_debug_internal (rtx insn)
1121 {
1122 unsigned int uid = INSN_UID (insn);
1123 struct df_insn_info *insn_info;
1124
1125 gcc_assert (DEBUG_INSN_P (insn)
1126 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1127
1128 if (!df)
1129 return false;
1130
1131 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1132 if (!insn_info)
1133 return false;
1134
1135 if (dump_file)
1136 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1137
1138 bitmap_clear_bit (&df->insns_to_delete, uid);
1139 bitmap_clear_bit (&df->insns_to_rescan, uid);
1140 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1141
1142 if (insn_info->defs == 0
1143 && insn_info->uses == 0
1144 && insn_info->eq_uses == 0
1145 && insn_info->mw_hardregs == 0)
1146 return false;
1147
1148 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1149
1150 if (df_chain)
1151 {
1152 df_ref_chain_delete_du_chain (insn_info->defs);
1153 df_ref_chain_delete_du_chain (insn_info->uses);
1154 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1155 }
1156
1157 df_ref_chain_delete (insn_info->defs);
1158 df_ref_chain_delete (insn_info->uses);
1159 df_ref_chain_delete (insn_info->eq_uses);
1160
1161 insn_info->defs = 0;
1162 insn_info->uses = 0;
1163 insn_info->eq_uses = 0;
1164 insn_info->mw_hardregs = 0;
1165
1166 return true;
1167 }
1168
1169
1170 /* Rescan all of the insns in the function. Note that the artificial
1171 uses and defs are not touched. This function will destroy def-use
1172 or use-def chains. */
1173
1174 void
1175 df_insn_rescan_all (void)
1176 {
1177 bool no_insn_rescan = false;
1178 bool defer_insn_rescan = false;
1179 basic_block bb;
1180 bitmap_iterator bi;
1181 unsigned int uid;
1182 bitmap_head tmp;
1183
1184 bitmap_initialize (&tmp, &df_bitmap_obstack);
1185
1186 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1187 {
1188 df_clear_flags (DF_NO_INSN_RESCAN);
1189 no_insn_rescan = true;
1190 }
1191
1192 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1193 {
1194 df_clear_flags (DF_DEFER_INSN_RESCAN);
1195 defer_insn_rescan = true;
1196 }
1197
1198 bitmap_copy (&tmp, &df->insns_to_delete);
1199 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1200 {
1201 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1202 if (insn_info)
1203 df_insn_info_delete (uid);
1204 }
1205
1206 bitmap_clear (&tmp);
1207 bitmap_clear (&df->insns_to_delete);
1208 bitmap_clear (&df->insns_to_rescan);
1209 bitmap_clear (&df->insns_to_notes_rescan);
1210
1211 FOR_EACH_BB_FN (bb, cfun)
1212 {
1213 rtx insn;
1214 FOR_BB_INSNS (bb, insn)
1215 {
1216 df_insn_rescan (insn);
1217 }
1218 }
1219
1220 if (no_insn_rescan)
1221 df_set_flags (DF_NO_INSN_RESCAN);
1222 if (defer_insn_rescan)
1223 df_set_flags (DF_DEFER_INSN_RESCAN);
1224 }
1225
1226
1227 /* Process all of the deferred rescans or deletions. */
1228
1229 void
1230 df_process_deferred_rescans (void)
1231 {
1232 bool no_insn_rescan = false;
1233 bool defer_insn_rescan = false;
1234 bitmap_iterator bi;
1235 unsigned int uid;
1236 bitmap_head tmp;
1237
1238 bitmap_initialize (&tmp, &df_bitmap_obstack);
1239
1240 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1241 {
1242 df_clear_flags (DF_NO_INSN_RESCAN);
1243 no_insn_rescan = true;
1244 }
1245
1246 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1247 {
1248 df_clear_flags (DF_DEFER_INSN_RESCAN);
1249 defer_insn_rescan = true;
1250 }
1251
1252 if (dump_file)
1253 fprintf (dump_file, "starting the processing of deferred insns\n");
1254
1255 bitmap_copy (&tmp, &df->insns_to_delete);
1256 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1257 {
1258 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1259 if (insn_info)
1260 df_insn_info_delete (uid);
1261 }
1262
1263 bitmap_copy (&tmp, &df->insns_to_rescan);
1264 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1265 {
1266 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1267 if (insn_info)
1268 df_insn_rescan (insn_info->insn);
1269 }
1270
1271 bitmap_copy (&tmp, &df->insns_to_notes_rescan);
1272 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi)
1273 {
1274 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1275 if (insn_info)
1276 df_notes_rescan (insn_info->insn);
1277 }
1278
1279 if (dump_file)
1280 fprintf (dump_file, "ending the processing of deferred insns\n");
1281
1282 bitmap_clear (&tmp);
1283 bitmap_clear (&df->insns_to_delete);
1284 bitmap_clear (&df->insns_to_rescan);
1285 bitmap_clear (&df->insns_to_notes_rescan);
1286
1287 if (no_insn_rescan)
1288 df_set_flags (DF_NO_INSN_RESCAN);
1289 if (defer_insn_rescan)
1290 df_set_flags (DF_DEFER_INSN_RESCAN);
1291
1292 /* If someone changed regs_ever_live during this pass, fix up the
1293 entry and exit blocks. */
1294 if (df->redo_entry_and_exit)
1295 {
1296 df_update_entry_exit_and_calls ();
1297 df->redo_entry_and_exit = false;
1298 }
1299 }
1300
1301
1302 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1303 the uses if INCLUDE_USES. Include the eq_uses if
1304 INCLUDE_EQ_USES. */
1305
1306 static unsigned int
1307 df_count_refs (bool include_defs, bool include_uses,
1308 bool include_eq_uses)
1309 {
1310 unsigned int regno;
1311 int size = 0;
1312 unsigned int m = df->regs_inited;
1313
1314 for (regno = 0; regno < m; regno++)
1315 {
1316 if (include_defs)
1317 size += DF_REG_DEF_COUNT (regno);
1318 if (include_uses)
1319 size += DF_REG_USE_COUNT (regno);
1320 if (include_eq_uses)
1321 size += DF_REG_EQ_USE_COUNT (regno);
1322 }
1323 return size;
1324 }
1325
1326
1327 /* Take build ref table for either the uses or defs from the reg-use
1328 or reg-def chains. This version processes the refs in reg order
1329 which is likely to be best if processing the whole function. */
1330
1331 static void
1332 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1333 bool include_defs,
1334 bool include_uses,
1335 bool include_eq_uses)
1336 {
1337 unsigned int m = df->regs_inited;
1338 unsigned int regno;
1339 unsigned int offset = 0;
1340 unsigned int start;
1341
1342 if (df->changeable_flags & DF_NO_HARD_REGS)
1343 {
1344 start = FIRST_PSEUDO_REGISTER;
1345 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1346 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1347 }
1348 else
1349 start = 0;
1350
1351 ref_info->total_size
1352 = df_count_refs (include_defs, include_uses, include_eq_uses);
1353
1354 df_check_and_grow_ref_info (ref_info, 1);
1355
1356 for (regno = start; regno < m; regno++)
1357 {
1358 int count = 0;
1359 ref_info->begin[regno] = offset;
1360 if (include_defs)
1361 {
1362 df_ref ref = DF_REG_DEF_CHAIN (regno);
1363 while (ref)
1364 {
1365 ref_info->refs[offset] = ref;
1366 DF_REF_ID (ref) = offset++;
1367 count++;
1368 ref = DF_REF_NEXT_REG (ref);
1369 gcc_checking_assert (offset < ref_info->refs_size);
1370 }
1371 }
1372 if (include_uses)
1373 {
1374 df_ref ref = DF_REG_USE_CHAIN (regno);
1375 while (ref)
1376 {
1377 ref_info->refs[offset] = ref;
1378 DF_REF_ID (ref) = offset++;
1379 count++;
1380 ref = DF_REF_NEXT_REG (ref);
1381 gcc_checking_assert (offset < ref_info->refs_size);
1382 }
1383 }
1384 if (include_eq_uses)
1385 {
1386 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1387 while (ref)
1388 {
1389 ref_info->refs[offset] = ref;
1390 DF_REF_ID (ref) = offset++;
1391 count++;
1392 ref = DF_REF_NEXT_REG (ref);
1393 gcc_checking_assert (offset < ref_info->refs_size);
1394 }
1395 }
1396 ref_info->count[regno] = count;
1397 }
1398
1399 /* The bitmap size is not decremented when refs are deleted. So
1400 reset it now that we have squished out all of the empty
1401 slots. */
1402 ref_info->table_size = offset;
1403 }
1404
1405
1406 /* Take build ref table for either the uses or defs from the reg-use
1407 or reg-def chains. This version processes the refs in insn order
1408 which is likely to be best if processing some segment of the
1409 function. */
1410
1411 static void
1412 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1413 bool include_defs,
1414 bool include_uses,
1415 bool include_eq_uses)
1416 {
1417 bitmap_iterator bi;
1418 unsigned int bb_index;
1419 unsigned int m = df->regs_inited;
1420 unsigned int offset = 0;
1421 unsigned int r;
1422 unsigned int start
1423 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1424
1425 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1426 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1427
1428 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1429 df_check_and_grow_ref_info (ref_info, 1);
1430
1431 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1432 {
1433 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1434 rtx insn;
1435 df_ref def, use;
1436
1437 if (include_defs)
1438 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1439 {
1440 unsigned int regno = DF_REF_REGNO (def);
1441 ref_info->count[regno]++;
1442 }
1443 if (include_uses)
1444 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1445 {
1446 unsigned int regno = DF_REF_REGNO (use);
1447 ref_info->count[regno]++;
1448 }
1449
1450 FOR_BB_INSNS (bb, insn)
1451 {
1452 if (INSN_P (insn))
1453 {
1454 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1455
1456 if (include_defs)
1457 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1458 {
1459 unsigned int regno = DF_REF_REGNO (def);
1460 ref_info->count[regno]++;
1461 }
1462 if (include_uses)
1463 FOR_EACH_INSN_INFO_USE (use, insn_info)
1464 {
1465 unsigned int regno = DF_REF_REGNO (use);
1466 ref_info->count[regno]++;
1467 }
1468 if (include_eq_uses)
1469 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1470 {
1471 unsigned int regno = DF_REF_REGNO (use);
1472 ref_info->count[regno]++;
1473 }
1474 }
1475 }
1476 }
1477
1478 for (r = start; r < m; r++)
1479 {
1480 ref_info->begin[r] = offset;
1481 offset += ref_info->count[r];
1482 ref_info->count[r] = 0;
1483 }
1484
1485 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1486 {
1487 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1488 rtx insn;
1489 df_ref def, use;
1490
1491 if (include_defs)
1492 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1493 {
1494 unsigned int regno = DF_REF_REGNO (def);
1495 if (regno >= start)
1496 {
1497 unsigned int id
1498 = ref_info->begin[regno] + ref_info->count[regno]++;
1499 DF_REF_ID (def) = id;
1500 ref_info->refs[id] = def;
1501 }
1502 }
1503 if (include_uses)
1504 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1505 {
1506 unsigned int regno = DF_REF_REGNO (def);
1507 if (regno >= start)
1508 {
1509 unsigned int id
1510 = ref_info->begin[regno] + ref_info->count[regno]++;
1511 DF_REF_ID (use) = id;
1512 ref_info->refs[id] = use;
1513 }
1514 }
1515
1516 FOR_BB_INSNS (bb, insn)
1517 {
1518 if (INSN_P (insn))
1519 {
1520 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1521
1522 if (include_defs)
1523 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1524 {
1525 unsigned int regno = DF_REF_REGNO (def);
1526 if (regno >= start)
1527 {
1528 unsigned int id
1529 = ref_info->begin[regno] + ref_info->count[regno]++;
1530 DF_REF_ID (def) = id;
1531 ref_info->refs[id] = def;
1532 }
1533 }
1534 if (include_uses)
1535 FOR_EACH_INSN_INFO_USE (use, insn_info)
1536 {
1537 unsigned int regno = DF_REF_REGNO (use);
1538 if (regno >= start)
1539 {
1540 unsigned int id
1541 = ref_info->begin[regno] + ref_info->count[regno]++;
1542 DF_REF_ID (use) = id;
1543 ref_info->refs[id] = use;
1544 }
1545 }
1546 if (include_eq_uses)
1547 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1548 {
1549 unsigned int regno = DF_REF_REGNO (use);
1550 if (regno >= start)
1551 {
1552 unsigned int id
1553 = ref_info->begin[regno] + ref_info->count[regno]++;
1554 DF_REF_ID (use) = id;
1555 ref_info->refs[id] = use;
1556 }
1557 }
1558 }
1559 }
1560 }
1561
1562 /* The bitmap size is not decremented when refs are deleted. So
1563 reset it now that we have squished out all of the empty
1564 slots. */
1565
1566 ref_info->table_size = offset;
1567 }
1568
1569 /* Take build ref table for either the uses or defs from the reg-use
1570 or reg-def chains. */
1571
1572 static void
1573 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1574 bool include_defs,
1575 bool include_uses,
1576 bool include_eq_uses)
1577 {
1578 if (df->analyze_subset)
1579 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1580 include_uses, include_eq_uses);
1581 else
1582 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1583 include_uses, include_eq_uses);
1584 }
1585
1586
1587 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1588 static unsigned int
1589 df_add_refs_to_table (unsigned int offset,
1590 struct df_ref_info *ref_info,
1591 df_ref ref)
1592 {
1593 for (; ref; ref = DF_REF_NEXT_LOC (ref))
1594 if (!(df->changeable_flags & DF_NO_HARD_REGS)
1595 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1596 {
1597 ref_info->refs[offset] = ref;
1598 DF_REF_ID (ref) = offset++;
1599 }
1600 return offset;
1601 }
1602
1603
1604 /* Count the number of refs in all of the insns of BB. Include the
1605 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1606 eq_uses if INCLUDE_EQ_USES. */
1607
1608 static unsigned int
1609 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1610 struct df_ref_info *ref_info,
1611 bool include_defs, bool include_uses,
1612 bool include_eq_uses)
1613 {
1614 rtx insn;
1615
1616 if (include_defs)
1617 offset = df_add_refs_to_table (offset, ref_info,
1618 df_get_artificial_defs (bb->index));
1619 if (include_uses)
1620 offset = df_add_refs_to_table (offset, ref_info,
1621 df_get_artificial_uses (bb->index));
1622
1623 FOR_BB_INSNS (bb, insn)
1624 if (INSN_P (insn))
1625 {
1626 unsigned int uid = INSN_UID (insn);
1627 if (include_defs)
1628 offset = df_add_refs_to_table (offset, ref_info,
1629 DF_INSN_UID_DEFS (uid));
1630 if (include_uses)
1631 offset = df_add_refs_to_table (offset, ref_info,
1632 DF_INSN_UID_USES (uid));
1633 if (include_eq_uses)
1634 offset = df_add_refs_to_table (offset, ref_info,
1635 DF_INSN_UID_EQ_USES (uid));
1636 }
1637 return offset;
1638 }
1639
1640
1641 /* Organize the refs by insn into the table in REF_INFO. If
1642 blocks_to_analyze is defined, use that set, otherwise the entire
1643 program. Include the defs if INCLUDE_DEFS. Include the uses if
1644 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1645
1646 static void
1647 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1648 bool include_defs, bool include_uses,
1649 bool include_eq_uses)
1650 {
1651 basic_block bb;
1652 unsigned int offset = 0;
1653
1654 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1655 df_check_and_grow_ref_info (ref_info, 1);
1656 if (df->blocks_to_analyze)
1657 {
1658 bitmap_iterator bi;
1659 unsigned int index;
1660
1661 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1662 {
1663 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1664 index),
1665 offset, ref_info,
1666 include_defs, include_uses,
1667 include_eq_uses);
1668 }
1669
1670 ref_info->table_size = offset;
1671 }
1672 else
1673 {
1674 FOR_ALL_BB_FN (bb, cfun)
1675 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1676 include_defs, include_uses,
1677 include_eq_uses);
1678 ref_info->table_size = offset;
1679 }
1680 }
1681
1682
1683 /* If the use refs in DF are not organized, reorganize them. */
1684
1685 void
1686 df_maybe_reorganize_use_refs (enum df_ref_order order)
1687 {
1688 if (order == df->use_info.ref_order)
1689 return;
1690
1691 switch (order)
1692 {
1693 case DF_REF_ORDER_BY_REG:
1694 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1695 break;
1696
1697 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1698 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1699 break;
1700
1701 case DF_REF_ORDER_BY_INSN:
1702 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1703 break;
1704
1705 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1706 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1707 break;
1708
1709 case DF_REF_ORDER_NO_TABLE:
1710 free (df->use_info.refs);
1711 df->use_info.refs = NULL;
1712 df->use_info.refs_size = 0;
1713 break;
1714
1715 case DF_REF_ORDER_UNORDERED:
1716 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1717 gcc_unreachable ();
1718 break;
1719 }
1720
1721 df->use_info.ref_order = order;
1722 }
1723
1724
1725 /* If the def refs in DF are not organized, reorganize them. */
1726
1727 void
1728 df_maybe_reorganize_def_refs (enum df_ref_order order)
1729 {
1730 if (order == df->def_info.ref_order)
1731 return;
1732
1733 switch (order)
1734 {
1735 case DF_REF_ORDER_BY_REG:
1736 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1737 break;
1738
1739 case DF_REF_ORDER_BY_INSN:
1740 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1741 break;
1742
1743 case DF_REF_ORDER_NO_TABLE:
1744 free (df->def_info.refs);
1745 df->def_info.refs = NULL;
1746 df->def_info.refs_size = 0;
1747 break;
1748
1749 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1750 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1751 case DF_REF_ORDER_UNORDERED:
1752 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1753 gcc_unreachable ();
1754 break;
1755 }
1756
1757 df->def_info.ref_order = order;
1758 }
1759
1760
1761 /* Change all of the basic block references in INSN to use the insn's
1762 current basic block. This function is called from routines that move
1763 instructions from one block to another. */
1764
1765 void
1766 df_insn_change_bb (rtx insn, basic_block new_bb)
1767 {
1768 basic_block old_bb = BLOCK_FOR_INSN (insn);
1769 struct df_insn_info *insn_info;
1770 unsigned int uid = INSN_UID (insn);
1771
1772 if (old_bb == new_bb)
1773 return;
1774
1775 set_block_for_insn (insn, new_bb);
1776
1777 if (!df)
1778 return;
1779
1780 if (dump_file)
1781 fprintf (dump_file, "changing bb of uid %d\n", uid);
1782
1783 insn_info = DF_INSN_UID_SAFE_GET (uid);
1784 if (insn_info == NULL)
1785 {
1786 if (dump_file)
1787 fprintf (dump_file, " unscanned insn\n");
1788 df_insn_rescan (insn);
1789 return;
1790 }
1791
1792 if (!INSN_P (insn))
1793 return;
1794
1795 df_set_bb_dirty (new_bb);
1796 if (old_bb)
1797 {
1798 if (dump_file)
1799 fprintf (dump_file, " from %d to %d\n",
1800 old_bb->index, new_bb->index);
1801 df_set_bb_dirty (old_bb);
1802 }
1803 else
1804 if (dump_file)
1805 fprintf (dump_file, " to %d\n", new_bb->index);
1806 }
1807
1808
1809 /* Helper function for df_ref_change_reg_with_loc. */
1810
1811 static void
1812 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1813 struct df_reg_info *new_df,
1814 int new_regno, rtx loc)
1815 {
1816 df_ref the_ref = old_df->reg_chain;
1817
1818 while (the_ref)
1819 {
1820 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1821 && DF_REF_LOC (the_ref)
1822 && (*DF_REF_LOC (the_ref) == loc))
1823 {
1824 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1825 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1826 df_ref *ref_ptr;
1827 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1828
1829 DF_REF_REGNO (the_ref) = new_regno;
1830 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1831
1832 /* Pull the_ref out of the old regno chain. */
1833 if (prev_ref)
1834 DF_REF_NEXT_REG (prev_ref) = next_ref;
1835 else
1836 old_df->reg_chain = next_ref;
1837 if (next_ref)
1838 DF_REF_PREV_REG (next_ref) = prev_ref;
1839 old_df->n_refs--;
1840
1841 /* Put the ref into the new regno chain. */
1842 DF_REF_PREV_REG (the_ref) = NULL;
1843 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1844 if (new_df->reg_chain)
1845 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1846 new_df->reg_chain = the_ref;
1847 new_df->n_refs++;
1848 if (DF_REF_BB (the_ref))
1849 df_set_bb_dirty (DF_REF_BB (the_ref));
1850
1851 /* Need to sort the record again that the ref was in because
1852 the regno is a sorting key. First, find the right
1853 record. */
1854 if (DF_REF_REG_DEF_P (the_ref))
1855 ref_ptr = &insn_info->defs;
1856 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1857 ref_ptr = &insn_info->eq_uses;
1858 else
1859 ref_ptr = &insn_info->uses;
1860 if (dump_file)
1861 fprintf (dump_file, "changing reg in insn %d\n",
1862 DF_REF_INSN_UID (the_ref));
1863
1864 /* Stop if we find the current reference or where the reference
1865 needs to be. */
1866 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1867 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1868 if (*ref_ptr != the_ref)
1869 {
1870 /* The reference needs to be promoted up the list. */
1871 df_ref next = DF_REF_NEXT_LOC (the_ref);
1872 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1873 *ref_ptr = the_ref;
1874 do
1875 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1876 while (*ref_ptr != the_ref);
1877 *ref_ptr = next;
1878 }
1879 else if (DF_REF_NEXT_LOC (the_ref)
1880 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1881 {
1882 /* The reference needs to be demoted down the list. */
1883 *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1884 do
1885 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1886 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1887 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1888 *ref_ptr = the_ref;
1889 }
1890
1891 the_ref = next_ref;
1892 }
1893 else
1894 the_ref = DF_REF_NEXT_REG (the_ref);
1895 }
1896 }
1897
1898
1899 /* Change the regno of all refs that contained LOC from OLD_REGNO to
1900 NEW_REGNO. Refs that do not match LOC are not changed which means
1901 that artificial refs are not changed since they have no loc. This
1902 call is to support the SET_REGNO macro. */
1903
1904 void
1905 df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
1906 {
1907 if ((!df) || (old_regno == -1) || (old_regno == new_regno))
1908 return;
1909
1910 df_grow_reg_info ();
1911
1912 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1913 DF_REG_DEF_GET (new_regno), new_regno, loc);
1914 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1915 DF_REG_USE_GET (new_regno), new_regno, loc);
1916 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1917 DF_REG_EQ_USE_GET (new_regno), new_regno, loc);
1918 }
1919
1920
1921 /* Delete the mw_hardregs that point into the eq_notes. */
1922
1923 static void
1924 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1925 {
1926 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1927 struct df_scan_problem_data *problem_data
1928 = (struct df_scan_problem_data *) df_scan->problem_data;
1929
1930 while (*mw_ptr)
1931 {
1932 df_mw_hardreg *mw = *mw_ptr;
1933 if (mw->flags & DF_REF_IN_NOTE)
1934 {
1935 *mw_ptr = DF_MWS_NEXT (mw);
1936 pool_free (problem_data->mw_reg_pool, mw);
1937 }
1938 else
1939 mw_ptr = &DF_MWS_NEXT (mw);
1940 }
1941 }
1942
1943
1944 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1945
1946 void
1947 df_notes_rescan (rtx insn)
1948 {
1949 struct df_insn_info *insn_info;
1950 unsigned int uid = INSN_UID (insn);
1951
1952 if (!df)
1953 return;
1954
1955 /* The client has disabled rescanning and plans to do it itself. */
1956 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1957 return;
1958
1959 /* Do nothing if the insn hasn't been emitted yet. */
1960 if (!BLOCK_FOR_INSN (insn))
1961 return;
1962
1963 df_grow_bb_info (df_scan);
1964 df_grow_reg_info ();
1965
1966 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1967
1968 /* The client has deferred rescanning. */
1969 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1970 {
1971 if (!insn_info)
1972 {
1973 insn_info = df_insn_create_insn_record (insn);
1974 insn_info->defs = 0;
1975 insn_info->uses = 0;
1976 insn_info->eq_uses = 0;
1977 insn_info->mw_hardregs = 0;
1978 }
1979
1980 bitmap_clear_bit (&df->insns_to_delete, uid);
1981 /* If the insn is set to be rescanned, it does not need to also
1982 be notes rescanned. */
1983 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1984 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1985 return;
1986 }
1987
1988 bitmap_clear_bit (&df->insns_to_delete, uid);
1989 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1990
1991 if (insn_info)
1992 {
1993 basic_block bb = BLOCK_FOR_INSN (insn);
1994 rtx note;
1995 struct df_collection_rec collection_rec;
1996 unsigned int i;
1997
1998 df_mw_hardreg_chain_delete_eq_uses (insn_info);
1999 df_ref_chain_delete (insn_info->eq_uses);
2000 insn_info->eq_uses = NULL;
2001
2002 /* Process REG_EQUIV/REG_EQUAL notes */
2003 for (note = REG_NOTES (insn); note;
2004 note = XEXP (note, 1))
2005 {
2006 switch (REG_NOTE_KIND (note))
2007 {
2008 case REG_EQUIV:
2009 case REG_EQUAL:
2010 df_uses_record (&collection_rec,
2011 &XEXP (note, 0), DF_REF_REG_USE,
2012 bb, insn_info, DF_REF_IN_NOTE);
2013 default:
2014 break;
2015 }
2016 }
2017
2018 /* Find some place to put any new mw_hardregs. */
2019 df_canonize_collection_rec (&collection_rec);
2020 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2021 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2022 {
2023 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2024 mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2025 DF_MWS_NEXT (mw) = *mw_ptr;
2026 *mw_ptr = mw;
2027 mw_ptr = &DF_MWS_NEXT (mw);
2028 }
2029 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2030 }
2031 else
2032 df_insn_rescan (insn);
2033
2034 }
2035
2036 \f
2037 /*----------------------------------------------------------------------------
2038 Hard core instruction scanning code. No external interfaces here,
2039 just a lot of routines that look inside insns.
2040 ----------------------------------------------------------------------------*/
2041
2042
2043 /* Return true if the contents of two df_ref's are identical.
2044 It ignores DF_REF_MARKER. */
2045
2046 static bool
2047 df_ref_equal_p (df_ref ref1, df_ref ref2)
2048 {
2049 if (!ref2)
2050 return false;
2051
2052 if (ref1 == ref2)
2053 return true;
2054
2055 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2056 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2057 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2058 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2059 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2060 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2061 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2062 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2063 return false;
2064
2065 switch (DF_REF_CLASS (ref1))
2066 {
2067 case DF_REF_ARTIFICIAL:
2068 case DF_REF_BASE:
2069 return true;
2070
2071 case DF_REF_REGULAR:
2072 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2073
2074 default:
2075 gcc_unreachable ();
2076 }
2077 return false;
2078 }
2079
2080
2081 /* Compare REF1 and REF2 for sorting. This is only called from places
2082 where all of the refs are of the same type, in the same insn, and
2083 have the same bb. So these fields are not checked. */
2084
2085 static int
2086 df_ref_compare (df_ref ref1, df_ref ref2)
2087 {
2088 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2089 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2090
2091 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2092 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2093
2094 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2095 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2096
2097 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2098 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2099
2100 /* Cannot look at the LOC field on artificial refs. */
2101 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2102 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2103 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2104
2105 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2106 {
2107 /* If two refs are identical except that one of them has is from
2108 a mw and one is not, we need to have the one with the mw
2109 first. */
2110 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2111 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2112 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2113 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2114 return -1;
2115 else
2116 return 1;
2117 }
2118
2119 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2120 }
2121
2122 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2123
2124 static int
2125 df_ref_ptr_compare (const void *r1, const void *r2)
2126 {
2127 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2128 }
2129
2130 static void
2131 df_swap_refs (vec<df_ref, va_heap> *ref_vec, int i, int j)
2132 {
2133 df_ref tmp = (*ref_vec)[i];
2134 (*ref_vec)[i] = (*ref_vec)[j];
2135 (*ref_vec)[j] = tmp;
2136 }
2137
2138 /* Sort and compress a set of refs. */
2139
2140 static void
2141 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2142 {
2143 unsigned int count;
2144 unsigned int i;
2145 unsigned int dist = 0;
2146
2147 count = ref_vec->length ();
2148
2149 /* If there are 1 or 0 elements, there is nothing to do. */
2150 if (count < 2)
2151 return;
2152 else if (count == 2)
2153 {
2154 df_ref r0 = (*ref_vec)[0];
2155 df_ref r1 = (*ref_vec)[1];
2156 if (df_ref_compare (r0, r1) > 0)
2157 df_swap_refs (ref_vec, 0, 1);
2158 }
2159 else
2160 {
2161 for (i = 0; i < count - 1; i++)
2162 {
2163 df_ref r0 = (*ref_vec)[i];
2164 df_ref r1 = (*ref_vec)[i + 1];
2165 if (df_ref_compare (r0, r1) >= 0)
2166 break;
2167 }
2168 /* If the array is already strictly ordered,
2169 which is the most common case for large COUNT case
2170 (which happens for CALL INSNs),
2171 no need to sort and filter out duplicate.
2172 Simply return the count.
2173 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2174 of DF_REF_COMPARE. */
2175 if (i == count - 1)
2176 return;
2177 ref_vec->qsort (df_ref_ptr_compare);
2178 }
2179
2180 for (i=0; i<count-dist; i++)
2181 {
2182 /* Find the next ref that is not equal to the current ref. */
2183 while (i + dist + 1 < count
2184 && df_ref_equal_p ((*ref_vec)[i],
2185 (*ref_vec)[i + dist + 1]))
2186 {
2187 df_free_ref ((*ref_vec)[i + dist + 1]);
2188 dist++;
2189 }
2190 /* Copy it down to the next position. */
2191 if (dist && i + dist + 1 < count)
2192 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2193 }
2194
2195 count -= dist;
2196 ref_vec->truncate (count);
2197 }
2198
2199
2200 /* Return true if the contents of two df_ref's are identical.
2201 It ignores DF_REF_MARKER. */
2202
2203 static bool
2204 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2205 {
2206 if (!mw2)
2207 return false;
2208 return (mw1 == mw2) ||
2209 (mw1->mw_reg == mw2->mw_reg
2210 && mw1->type == mw2->type
2211 && mw1->flags == mw2->flags
2212 && mw1->start_regno == mw2->start_regno
2213 && mw1->end_regno == mw2->end_regno);
2214 }
2215
2216
2217 /* Compare MW1 and MW2 for sorting. */
2218
2219 static int
2220 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2221 {
2222 if (mw1->type != mw2->type)
2223 return mw1->type - mw2->type;
2224
2225 if (mw1->flags != mw2->flags)
2226 return mw1->flags - mw2->flags;
2227
2228 if (mw1->start_regno != mw2->start_regno)
2229 return mw1->start_regno - mw2->start_regno;
2230
2231 if (mw1->end_regno != mw2->end_regno)
2232 return mw1->end_regno - mw2->end_regno;
2233
2234 if (mw1->mw_reg != mw2->mw_reg)
2235 return mw1->mw_order - mw2->mw_order;
2236
2237 return 0;
2238 }
2239
2240 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2241
2242 static int
2243 df_mw_ptr_compare (const void *m1, const void *m2)
2244 {
2245 return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2246 *(const df_mw_hardreg *const *) m2);
2247 }
2248
2249 /* Sort and compress a set of refs. */
2250
2251 static void
2252 df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec)
2253 {
2254 unsigned int count;
2255 struct df_scan_problem_data *problem_data
2256 = (struct df_scan_problem_data *) df_scan->problem_data;
2257 unsigned int i;
2258 unsigned int dist = 0;
2259
2260 count = mw_vec->length ();
2261 if (count < 2)
2262 return;
2263 else if (count == 2)
2264 {
2265 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2266 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2267 if (df_mw_compare (m0, m1) > 0)
2268 {
2269 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2270 (*mw_vec)[0] = (*mw_vec)[1];
2271 (*mw_vec)[1] = tmp;
2272 }
2273 }
2274 else
2275 mw_vec->qsort (df_mw_ptr_compare);
2276
2277 for (i=0; i<count-dist; i++)
2278 {
2279 /* Find the next ref that is not equal to the current ref. */
2280 while (i + dist + 1 < count
2281 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2282 {
2283 pool_free (problem_data->mw_reg_pool,
2284 (*mw_vec)[i + dist + 1]);
2285 dist++;
2286 }
2287 /* Copy it down to the next position. */
2288 if (dist && i + dist + 1 < count)
2289 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2290 }
2291
2292 count -= dist;
2293 mw_vec->truncate (count);
2294 }
2295
2296
2297 /* Sort and remove duplicates from the COLLECTION_REC. */
2298
2299 static void
2300 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2301 {
2302 df_sort_and_compress_refs (&collection_rec->def_vec);
2303 df_sort_and_compress_refs (&collection_rec->use_vec);
2304 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2305 df_sort_and_compress_mws (&collection_rec->mw_vec);
2306 }
2307
2308
2309 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2310
2311 static void
2312 df_install_ref (df_ref this_ref,
2313 struct df_reg_info *reg_info,
2314 struct df_ref_info *ref_info,
2315 bool add_to_table)
2316 {
2317 unsigned int regno = DF_REF_REGNO (this_ref);
2318 /* Add the ref to the reg_{def,use,eq_use} chain. */
2319 df_ref head = reg_info->reg_chain;
2320
2321 reg_info->reg_chain = this_ref;
2322 reg_info->n_refs++;
2323
2324 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2325 {
2326 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2327 df->hard_regs_live_count[regno]++;
2328 }
2329
2330 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2331 && DF_REF_PREV_REG (this_ref) == NULL);
2332
2333 DF_REF_NEXT_REG (this_ref) = head;
2334
2335 /* We cannot actually link to the head of the chain. */
2336 DF_REF_PREV_REG (this_ref) = NULL;
2337
2338 if (head)
2339 DF_REF_PREV_REG (head) = this_ref;
2340
2341 if (add_to_table)
2342 {
2343 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2344 df_check_and_grow_ref_info (ref_info, 1);
2345 DF_REF_ID (this_ref) = ref_info->table_size;
2346 /* Add the ref to the big array of defs. */
2347 ref_info->refs[ref_info->table_size] = this_ref;
2348 ref_info->table_size++;
2349 }
2350 else
2351 DF_REF_ID (this_ref) = -1;
2352
2353 ref_info->total_size++;
2354 }
2355
2356
2357 /* This function takes one of the groups of refs (defs, uses or
2358 eq_uses) and installs the entire group into the insn. It also adds
2359 each of these refs into the appropriate chains. */
2360
2361 static df_ref
2362 df_install_refs (basic_block bb,
2363 const vec<df_ref, va_heap> *old_vec,
2364 struct df_reg_info **reg_info,
2365 struct df_ref_info *ref_info,
2366 bool is_notes)
2367 {
2368 unsigned int count = old_vec->length ();
2369 if (count)
2370 {
2371 bool add_to_table;
2372 df_ref this_ref;
2373 unsigned int ix;
2374
2375 switch (ref_info->ref_order)
2376 {
2377 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2378 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2379 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2380 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2381 add_to_table = true;
2382 break;
2383 case DF_REF_ORDER_UNORDERED:
2384 case DF_REF_ORDER_BY_REG:
2385 case DF_REF_ORDER_BY_INSN:
2386 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2387 add_to_table = !is_notes;
2388 break;
2389 default:
2390 add_to_table = false;
2391 break;
2392 }
2393
2394 /* Do not add if ref is not in the right blocks. */
2395 if (add_to_table && df->analyze_subset)
2396 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2397
2398 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2399 {
2400 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2401 ? (*old_vec)[ix + 1]
2402 : NULL);
2403 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2404 ref_info, add_to_table);
2405 }
2406 return (*old_vec)[0];
2407 }
2408 else
2409 return 0;
2410 }
2411
2412
2413 /* This function takes the mws installs the entire group into the
2414 insn. */
2415
2416 static struct df_mw_hardreg *
2417 df_install_mws (const vec<df_mw_hardreg_ptr, va_heap> *old_vec)
2418 {
2419 unsigned int count = old_vec->length ();
2420 if (count)
2421 {
2422 for (unsigned int i = 0; i < count - 1; i++)
2423 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2424 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2425 return (*old_vec)[0];
2426 }
2427 else
2428 return 0;
2429 }
2430
2431
2432 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2433 chains and update other necessary information. */
2434
2435 static void
2436 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2437 basic_block bb, rtx insn, unsigned int flags)
2438 {
2439 if (insn)
2440 {
2441 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2442 /* If there is a vector in the collection rec, add it to the
2443 insn. A null rec is a signal that the caller will handle the
2444 chain specially. */
2445 if (flags & copy_defs)
2446 {
2447 gcc_checking_assert (!insn_rec->defs);
2448 insn_rec->defs
2449 = df_install_refs (bb, &collection_rec->def_vec,
2450 df->def_regs,
2451 &df->def_info, false);
2452 }
2453 if (flags & copy_uses)
2454 {
2455 gcc_checking_assert (!insn_rec->uses);
2456 insn_rec->uses
2457 = df_install_refs (bb, &collection_rec->use_vec,
2458 df->use_regs,
2459 &df->use_info, false);
2460 }
2461 if (flags & copy_eq_uses)
2462 {
2463 gcc_checking_assert (!insn_rec->eq_uses);
2464 insn_rec->eq_uses
2465 = df_install_refs (bb, &collection_rec->eq_use_vec,
2466 df->eq_use_regs,
2467 &df->use_info, true);
2468 }
2469 if (flags & copy_mw)
2470 {
2471 gcc_checking_assert (!insn_rec->mw_hardregs);
2472 insn_rec->mw_hardregs
2473 = df_install_mws (&collection_rec->mw_vec);
2474 }
2475 }
2476 else
2477 {
2478 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2479
2480 gcc_checking_assert (!bb_info->artificial_defs);
2481 bb_info->artificial_defs
2482 = df_install_refs (bb, &collection_rec->def_vec,
2483 df->def_regs,
2484 &df->def_info, false);
2485 gcc_checking_assert (!bb_info->artificial_uses);
2486 bb_info->artificial_uses
2487 = df_install_refs (bb, &collection_rec->use_vec,
2488 df->use_regs,
2489 &df->use_info, false);
2490 }
2491 }
2492
2493
2494 /* Allocate a ref and initialize its fields. */
2495
2496 static df_ref
2497 df_ref_create_structure (enum df_ref_class cl,
2498 struct df_collection_rec *collection_rec,
2499 rtx reg, rtx *loc,
2500 basic_block bb, struct df_insn_info *info,
2501 enum df_ref_type ref_type,
2502 int ref_flags)
2503 {
2504 df_ref this_ref = NULL;
2505 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2506 struct df_scan_problem_data *problem_data
2507 = (struct df_scan_problem_data *) df_scan->problem_data;
2508
2509 switch (cl)
2510 {
2511 case DF_REF_BASE:
2512 this_ref = (df_ref) pool_alloc (problem_data->ref_base_pool);
2513 gcc_checking_assert (loc == NULL);
2514 break;
2515
2516 case DF_REF_ARTIFICIAL:
2517 this_ref = (df_ref) pool_alloc (problem_data->ref_artificial_pool);
2518 this_ref->artificial_ref.bb = bb;
2519 gcc_checking_assert (loc == NULL);
2520 break;
2521
2522 case DF_REF_REGULAR:
2523 this_ref = (df_ref) pool_alloc (problem_data->ref_regular_pool);
2524 this_ref->regular_ref.loc = loc;
2525 gcc_checking_assert (loc);
2526 break;
2527 }
2528
2529 DF_REF_CLASS (this_ref) = cl;
2530 DF_REF_ID (this_ref) = -1;
2531 DF_REF_REG (this_ref) = reg;
2532 DF_REF_REGNO (this_ref) = regno;
2533 DF_REF_TYPE (this_ref) = ref_type;
2534 DF_REF_INSN_INFO (this_ref) = info;
2535 DF_REF_CHAIN (this_ref) = NULL;
2536 DF_REF_FLAGS (this_ref) = ref_flags;
2537 DF_REF_NEXT_REG (this_ref) = NULL;
2538 DF_REF_PREV_REG (this_ref) = NULL;
2539 DF_REF_ORDER (this_ref) = df->ref_order++;
2540
2541 /* We need to clear this bit because fwprop, and in the future
2542 possibly other optimizations sometimes create new refs using ond
2543 refs as the model. */
2544 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2545
2546 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2547 if (regno < FIRST_PSEUDO_REGISTER
2548 && !DF_REF_IS_ARTIFICIAL (this_ref)
2549 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2550 {
2551 if (DF_REF_REG_DEF_P (this_ref))
2552 {
2553 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2554 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2555 }
2556 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2557 && (regno == FRAME_POINTER_REGNUM
2558 || regno == ARG_POINTER_REGNUM)))
2559 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2560 }
2561
2562 if (collection_rec)
2563 {
2564 if (DF_REF_REG_DEF_P (this_ref))
2565 collection_rec->def_vec.safe_push (this_ref);
2566 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2567 collection_rec->eq_use_vec.safe_push (this_ref);
2568 else
2569 collection_rec->use_vec.safe_push (this_ref);
2570 }
2571 else
2572 df_install_ref_incremental (this_ref);
2573
2574 return this_ref;
2575 }
2576
2577
2578 /* Create new references of type DF_REF_TYPE for each part of register REG
2579 at address LOC within INSN of BB. */
2580
2581
2582 static void
2583 df_ref_record (enum df_ref_class cl,
2584 struct df_collection_rec *collection_rec,
2585 rtx reg, rtx *loc,
2586 basic_block bb, struct df_insn_info *insn_info,
2587 enum df_ref_type ref_type,
2588 int ref_flags)
2589 {
2590 unsigned int regno;
2591
2592 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2593
2594 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2595 if (regno < FIRST_PSEUDO_REGISTER)
2596 {
2597 struct df_mw_hardreg *hardreg = NULL;
2598 struct df_scan_problem_data *problem_data
2599 = (struct df_scan_problem_data *) df_scan->problem_data;
2600 unsigned int i;
2601 unsigned int endregno;
2602 df_ref ref;
2603
2604 if (GET_CODE (reg) == SUBREG)
2605 {
2606 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2607 SUBREG_BYTE (reg), GET_MODE (reg));
2608 endregno = regno + subreg_nregs (reg);
2609 }
2610 else
2611 endregno = END_HARD_REGNO (reg);
2612
2613 /* If this is a multiword hardreg, we create some extra
2614 datastructures that will enable us to easily build REG_DEAD
2615 and REG_UNUSED notes. */
2616 if (collection_rec
2617 && (endregno != regno + 1) && insn_info)
2618 {
2619 /* Sets to a subreg of a multiword register are partial.
2620 Sets to a non-subreg of a multiword register are not. */
2621 if (GET_CODE (reg) == SUBREG)
2622 ref_flags |= DF_REF_PARTIAL;
2623 ref_flags |= DF_REF_MW_HARDREG;
2624
2625 hardreg = (struct df_mw_hardreg *) pool_alloc (problem_data->mw_reg_pool);
2626 hardreg->type = ref_type;
2627 hardreg->flags = ref_flags;
2628 hardreg->mw_reg = reg;
2629 hardreg->start_regno = regno;
2630 hardreg->end_regno = endregno - 1;
2631 hardreg->mw_order = df->ref_order++;
2632 collection_rec->mw_vec.safe_push (hardreg);
2633 }
2634
2635 for (i = regno; i < endregno; i++)
2636 {
2637 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2638 bb, insn_info, ref_type, ref_flags);
2639
2640 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2641 }
2642 }
2643 else
2644 {
2645 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2646 ref_type, ref_flags);
2647 }
2648 }
2649
2650
2651 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2652 covered by the outer mode is smaller than that covered by the inner mode,
2653 is a read-modify-write operation.
2654 This function returns true iff the SUBREG X is such a SUBREG. */
2655
2656 bool
2657 df_read_modify_subreg_p (rtx x)
2658 {
2659 unsigned int isize, osize;
2660 if (GET_CODE (x) != SUBREG)
2661 return false;
2662 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2663 osize = GET_MODE_SIZE (GET_MODE (x));
2664 return isize > osize
2665 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2666 }
2667
2668
2669 /* Process all the registers defined in the rtx pointed by LOC.
2670 Autoincrement/decrement definitions will be picked up by df_uses_record.
2671 Any change here has to be matched in df_find_hard_reg_defs_1. */
2672
2673 static void
2674 df_def_record_1 (struct df_collection_rec *collection_rec,
2675 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2676 int flags)
2677 {
2678 rtx dst = *loc;
2679
2680 /* It is legal to have a set destination be a parallel. */
2681 if (GET_CODE (dst) == PARALLEL)
2682 {
2683 int i;
2684 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2685 {
2686 rtx temp = XVECEXP (dst, 0, i);
2687 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2688 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2689 bb, insn_info, flags);
2690 }
2691 return;
2692 }
2693
2694 if (GET_CODE (dst) == STRICT_LOW_PART)
2695 {
2696 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2697
2698 loc = &XEXP (dst, 0);
2699 dst = *loc;
2700 }
2701
2702 if (GET_CODE (dst) == ZERO_EXTRACT)
2703 {
2704 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2705
2706 loc = &XEXP (dst, 0);
2707 dst = *loc;
2708 }
2709
2710 /* At this point if we do not have a reg or a subreg, just return. */
2711 if (REG_P (dst))
2712 {
2713 df_ref_record (DF_REF_REGULAR, collection_rec,
2714 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2715
2716 /* We want to keep sp alive everywhere - by making all
2717 writes to sp also use of sp. */
2718 if (REGNO (dst) == STACK_POINTER_REGNUM)
2719 df_ref_record (DF_REF_BASE, collection_rec,
2720 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2721 }
2722 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2723 {
2724 if (df_read_modify_subreg_p (dst))
2725 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2726
2727 flags |= DF_REF_SUBREG;
2728
2729 df_ref_record (DF_REF_REGULAR, collection_rec,
2730 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2731 }
2732 }
2733
2734
2735 /* Process all the registers defined in the pattern rtx, X. Any change
2736 here has to be matched in df_find_hard_reg_defs. */
2737
2738 static void
2739 df_defs_record (struct df_collection_rec *collection_rec,
2740 rtx x, basic_block bb, struct df_insn_info *insn_info,
2741 int flags)
2742 {
2743 RTX_CODE code = GET_CODE (x);
2744 int i;
2745
2746 switch (code)
2747 {
2748 case SET:
2749 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2750 break;
2751
2752 case CLOBBER:
2753 flags |= DF_REF_MUST_CLOBBER;
2754 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2755 break;
2756
2757 case COND_EXEC:
2758 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2759 bb, insn_info, DF_REF_CONDITIONAL);
2760 break;
2761
2762 case PARALLEL:
2763 for (i = 0; i < XVECLEN (x, 0); i++)
2764 df_defs_record (collection_rec, XVECEXP (x, 0, i),
2765 bb, insn_info, flags);
2766 break;
2767 default:
2768 /* No DEFs to record in other cases */
2769 break;
2770 }
2771 }
2772
2773 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2774 destination of a set or clobber. This has to match the logic in
2775 df_defs_record_1. */
2776
2777 static void
2778 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2779 {
2780 /* It is legal to have a set destination be a parallel. */
2781 if (GET_CODE (dst) == PARALLEL)
2782 {
2783 int i;
2784 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2785 {
2786 rtx temp = XVECEXP (dst, 0, i);
2787 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2788 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2789 }
2790 return;
2791 }
2792
2793 if (GET_CODE (dst) == STRICT_LOW_PART)
2794 dst = XEXP (dst, 0);
2795
2796 if (GET_CODE (dst) == ZERO_EXTRACT)
2797 dst = XEXP (dst, 0);
2798
2799 /* At this point if we do not have a reg or a subreg, just return. */
2800 if (REG_P (dst) && HARD_REGISTER_P (dst))
2801 SET_HARD_REG_BIT (*defs, REGNO (dst));
2802 else if (GET_CODE (dst) == SUBREG
2803 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2804 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2805 }
2806
2807 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2808 has to match the logic in df_defs_record. */
2809
2810 static void
2811 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2812 {
2813 RTX_CODE code = GET_CODE (x);
2814 int i;
2815
2816 switch (code)
2817 {
2818 case SET:
2819 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2820 break;
2821
2822 case CLOBBER:
2823 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2824 break;
2825
2826 case COND_EXEC:
2827 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2828 break;
2829
2830 case PARALLEL:
2831 for (i = 0; i < XVECLEN (x, 0); i++)
2832 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2833 break;
2834 default:
2835 /* No DEFs to record in other cases */
2836 break;
2837 }
2838 }
2839
2840
2841 /* Process all the registers used in the rtx at address LOC. */
2842
2843 static void
2844 df_uses_record (struct df_collection_rec *collection_rec,
2845 rtx *loc, enum df_ref_type ref_type,
2846 basic_block bb, struct df_insn_info *insn_info,
2847 int flags)
2848 {
2849 RTX_CODE code;
2850 rtx x;
2851
2852 retry:
2853 x = *loc;
2854 if (!x)
2855 return;
2856 code = GET_CODE (x);
2857 switch (code)
2858 {
2859 case LABEL_REF:
2860 case SYMBOL_REF:
2861 case CONST:
2862 CASE_CONST_ANY:
2863 case PC:
2864 case CC0:
2865 case ADDR_VEC:
2866 case ADDR_DIFF_VEC:
2867 return;
2868
2869 case CLOBBER:
2870 /* If we are clobbering a MEM, mark any registers inside the address
2871 as being used. */
2872 if (MEM_P (XEXP (x, 0)))
2873 df_uses_record (collection_rec,
2874 &XEXP (XEXP (x, 0), 0),
2875 DF_REF_REG_MEM_STORE,
2876 bb, insn_info,
2877 flags);
2878
2879 /* If we're clobbering a REG then we have a def so ignore. */
2880 return;
2881
2882 case MEM:
2883 df_uses_record (collection_rec,
2884 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2885 bb, insn_info, flags & DF_REF_IN_NOTE);
2886 return;
2887
2888 case SUBREG:
2889 /* While we're here, optimize this case. */
2890 flags |= DF_REF_PARTIAL;
2891 /* In case the SUBREG is not of a REG, do not optimize. */
2892 if (!REG_P (SUBREG_REG (x)))
2893 {
2894 loc = &SUBREG_REG (x);
2895 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2896 return;
2897 }
2898 /* ... Fall through ... */
2899
2900 case REG:
2901 df_ref_record (DF_REF_REGULAR, collection_rec,
2902 x, loc, bb, insn_info,
2903 ref_type, flags);
2904 return;
2905
2906 case SIGN_EXTRACT:
2907 case ZERO_EXTRACT:
2908 {
2909 df_uses_record (collection_rec,
2910 &XEXP (x, 1), ref_type, bb, insn_info, flags);
2911 df_uses_record (collection_rec,
2912 &XEXP (x, 2), ref_type, bb, insn_info, flags);
2913
2914 /* If the parameters to the zero or sign extract are
2915 constants, strip them off and recurse, otherwise there is
2916 no information that we can gain from this operation. */
2917 if (code == ZERO_EXTRACT)
2918 flags |= DF_REF_ZERO_EXTRACT;
2919 else
2920 flags |= DF_REF_SIGN_EXTRACT;
2921
2922 df_uses_record (collection_rec,
2923 &XEXP (x, 0), ref_type, bb, insn_info, flags);
2924 return;
2925 }
2926 break;
2927
2928 case SET:
2929 {
2930 rtx dst = SET_DEST (x);
2931 gcc_assert (!(flags & DF_REF_IN_NOTE));
2932 df_uses_record (collection_rec,
2933 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2934
2935 switch (GET_CODE (dst))
2936 {
2937 case SUBREG:
2938 if (df_read_modify_subreg_p (dst))
2939 {
2940 df_uses_record (collection_rec, &SUBREG_REG (dst),
2941 DF_REF_REG_USE, bb, insn_info,
2942 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2943 break;
2944 }
2945 /* Fall through. */
2946 case REG:
2947 case PARALLEL:
2948 case SCRATCH:
2949 case PC:
2950 case CC0:
2951 break;
2952 case MEM:
2953 df_uses_record (collection_rec, &XEXP (dst, 0),
2954 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2955 break;
2956 case STRICT_LOW_PART:
2957 {
2958 rtx *temp = &XEXP (dst, 0);
2959 /* A strict_low_part uses the whole REG and not just the
2960 SUBREG. */
2961 dst = XEXP (dst, 0);
2962 df_uses_record (collection_rec,
2963 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2964 DF_REF_REG_USE, bb, insn_info,
2965 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2966 }
2967 break;
2968 case ZERO_EXTRACT:
2969 {
2970 df_uses_record (collection_rec, &XEXP (dst, 1),
2971 DF_REF_REG_USE, bb, insn_info, flags);
2972 df_uses_record (collection_rec, &XEXP (dst, 2),
2973 DF_REF_REG_USE, bb, insn_info, flags);
2974 if (GET_CODE (XEXP (dst,0)) == MEM)
2975 df_uses_record (collection_rec, &XEXP (dst, 0),
2976 DF_REF_REG_USE, bb, insn_info,
2977 flags);
2978 else
2979 df_uses_record (collection_rec, &XEXP (dst, 0),
2980 DF_REF_REG_USE, bb, insn_info,
2981 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2982 }
2983 break;
2984
2985 default:
2986 gcc_unreachable ();
2987 }
2988 return;
2989 }
2990
2991 case RETURN:
2992 case SIMPLE_RETURN:
2993 break;
2994
2995 case ASM_OPERANDS:
2996 case UNSPEC_VOLATILE:
2997 case TRAP_IF:
2998 case ASM_INPUT:
2999 {
3000 /* Traditional and volatile asm instructions must be
3001 considered to use and clobber all hard registers, all
3002 pseudo-registers and all of memory. So must TRAP_IF and
3003 UNSPEC_VOLATILE operations.
3004
3005 Consider for instance a volatile asm that changes the fpu
3006 rounding mode. An insn should not be moved across this
3007 even if it only uses pseudo-regs because it might give an
3008 incorrectly rounded result.
3009
3010 However, flow.c's liveness computation did *not* do this,
3011 giving the reasoning as " ?!? Unfortunately, marking all
3012 hard registers as live causes massive problems for the
3013 register allocator and marking all pseudos as live creates
3014 mountains of uninitialized variable warnings."
3015
3016 In order to maintain the status quo with regard to liveness
3017 and uses, we do what flow.c did and just mark any regs we
3018 can find in ASM_OPERANDS as used. In global asm insns are
3019 scanned and regs_asm_clobbered is filled out.
3020
3021 For all ASM_OPERANDS, we must traverse the vector of input
3022 operands. We can not just fall through here since then we
3023 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3024 which do not indicate traditional asms unlike their normal
3025 usage. */
3026 if (code == ASM_OPERANDS)
3027 {
3028 int j;
3029
3030 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3031 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
3032 DF_REF_REG_USE, bb, insn_info, flags);
3033 return;
3034 }
3035 break;
3036 }
3037
3038 case VAR_LOCATION:
3039 df_uses_record (collection_rec,
3040 &PAT_VAR_LOCATION_LOC (x),
3041 DF_REF_REG_USE, bb, insn_info, flags);
3042 return;
3043
3044 case PRE_DEC:
3045 case POST_DEC:
3046 case PRE_INC:
3047 case POST_INC:
3048 case PRE_MODIFY:
3049 case POST_MODIFY:
3050 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3051 /* Catch the def of the register being modified. */
3052 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3053 bb, insn_info,
3054 DF_REF_REG_DEF,
3055 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3056
3057 /* ... Fall through to handle uses ... */
3058
3059 default:
3060 break;
3061 }
3062
3063 /* Recursively scan the operands of this expression. */
3064 {
3065 const char *fmt = GET_RTX_FORMAT (code);
3066 int i;
3067
3068 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3069 {
3070 if (fmt[i] == 'e')
3071 {
3072 /* Tail recursive case: save a function call level. */
3073 if (i == 0)
3074 {
3075 loc = &XEXP (x, 0);
3076 goto retry;
3077 }
3078 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3079 bb, insn_info, flags);
3080 }
3081 else if (fmt[i] == 'E')
3082 {
3083 int j;
3084 for (j = 0; j < XVECLEN (x, i); j++)
3085 df_uses_record (collection_rec,
3086 &XVECEXP (x, i, j), ref_type,
3087 bb, insn_info, flags);
3088 }
3089 }
3090 }
3091
3092 return;
3093 }
3094
3095
3096 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3097
3098 static void
3099 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3100 {
3101 unsigned int ix;
3102 df_ref ref;
3103
3104 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3105 {
3106 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3107 {
3108 df_ref use;
3109
3110 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3111 DF_REF_LOC (ref), DF_REF_BB (ref),
3112 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3113 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3114 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3115 }
3116 }
3117 }
3118
3119
3120 /* Get call's extra defs and uses (track caller-saved registers). */
3121
3122 static void
3123 df_get_call_refs (struct df_collection_rec *collection_rec,
3124 basic_block bb,
3125 struct df_insn_info *insn_info,
3126 int flags)
3127 {
3128 rtx note;
3129 bool is_sibling_call;
3130 unsigned int i;
3131 HARD_REG_SET defs_generated;
3132 HARD_REG_SET fn_reg_set_usage;
3133
3134 CLEAR_HARD_REG_SET (defs_generated);
3135 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3136 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3137 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3138 regs_invalidated_by_call);
3139
3140 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3141 {
3142 if (i == STACK_POINTER_REGNUM)
3143 /* The stack ptr is used (honorarily) by a CALL insn. */
3144 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3145 NULL, bb, insn_info, DF_REF_REG_USE,
3146 DF_REF_CALL_STACK_USAGE | flags);
3147 else if (global_regs[i])
3148 {
3149 /* Calls to const functions cannot access any global registers and
3150 calls to pure functions cannot set them. All other calls may
3151 reference any of the global registers, so they are recorded as
3152 used. */
3153 if (!RTL_CONST_CALL_P (insn_info->insn))
3154 {
3155 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3156 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3157 if (!RTL_PURE_CALL_P (insn_info->insn))
3158 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3159 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3160 }
3161 }
3162 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3163 /* no clobbers for regs that are the result of the call */
3164 && !TEST_HARD_REG_BIT (defs_generated, i)
3165 && (!is_sibling_call
3166 || !bitmap_bit_p (df->exit_block_uses, i)
3167 || refers_to_regno_p (i, i+1,
3168 crtl->return_rtx, NULL)))
3169 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3170 NULL, bb, insn_info, DF_REF_REG_DEF,
3171 DF_REF_MAY_CLOBBER | flags);
3172 }
3173
3174 /* Record the registers used to pass arguments, and explicitly
3175 noted as clobbered. */
3176 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3177 note = XEXP (note, 1))
3178 {
3179 if (GET_CODE (XEXP (note, 0)) == USE)
3180 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3181 DF_REF_REG_USE, bb, insn_info, flags);
3182 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3183 {
3184 if (REG_P (XEXP (XEXP (note, 0), 0)))
3185 {
3186 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3187 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3188 df_defs_record (collection_rec, XEXP (note, 0), bb,
3189 insn_info, flags);
3190 }
3191 else
3192 df_uses_record (collection_rec, &XEXP (note, 0),
3193 DF_REF_REG_USE, bb, insn_info, flags);
3194 }
3195 }
3196
3197 return;
3198 }
3199
3200 /* Collect all refs in the INSN. This function is free of any
3201 side-effect - it will create and return a lists of df_ref's in the
3202 COLLECTION_REC without putting those refs into existing ref chains
3203 and reg chains. */
3204
3205 static void
3206 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3207 basic_block bb, struct df_insn_info *insn_info)
3208 {
3209 rtx note;
3210 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3211
3212 /* Clear out the collection record. */
3213 collection_rec->def_vec.truncate (0);
3214 collection_rec->use_vec.truncate (0);
3215 collection_rec->eq_use_vec.truncate (0);
3216 collection_rec->mw_vec.truncate (0);
3217
3218 /* Process REG_EQUIV/REG_EQUAL notes. */
3219 for (note = REG_NOTES (insn_info->insn); note;
3220 note = XEXP (note, 1))
3221 {
3222 switch (REG_NOTE_KIND (note))
3223 {
3224 case REG_EQUIV:
3225 case REG_EQUAL:
3226 df_uses_record (collection_rec,
3227 &XEXP (note, 0), DF_REF_REG_USE,
3228 bb, insn_info, DF_REF_IN_NOTE);
3229 break;
3230 case REG_NON_LOCAL_GOTO:
3231 /* The frame ptr is used by a non-local goto. */
3232 df_ref_record (DF_REF_BASE, collection_rec,
3233 regno_reg_rtx[FRAME_POINTER_REGNUM],
3234 NULL, bb, insn_info,
3235 DF_REF_REG_USE, 0);
3236 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3237 df_ref_record (DF_REF_BASE, collection_rec,
3238 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3239 NULL, bb, insn_info,
3240 DF_REF_REG_USE, 0);
3241 #endif
3242 break;
3243 default:
3244 break;
3245 }
3246 }
3247
3248 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3249 uses from CALL_INSN_FUNCTION_USAGE. */
3250 if (CALL_P (insn_info->insn))
3251 df_get_call_refs (collection_rec, bb, insn_info,
3252 (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3253
3254 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3255 that a qsort on the defs is unnecessary in most cases. */
3256 df_defs_record (collection_rec,
3257 PATTERN (insn_info->insn), bb, insn_info, 0);
3258
3259 /* Record the register uses. */
3260 df_uses_record (collection_rec,
3261 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3262
3263 /* DF_REF_CONDITIONAL needs corresponding USES. */
3264 if (is_cond_exec)
3265 df_get_conditional_uses (collection_rec);
3266
3267 df_canonize_collection_rec (collection_rec);
3268 }
3269
3270 /* Recompute the luids for the insns in BB. */
3271
3272 void
3273 df_recompute_luids (basic_block bb)
3274 {
3275 rtx insn;
3276 int luid = 0;
3277
3278 df_grow_insn_info ();
3279
3280 /* Scan the block an insn at a time from beginning to end. */
3281 FOR_BB_INSNS (bb, insn)
3282 {
3283 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3284 /* Inserting labels does not always trigger the incremental
3285 rescanning. */
3286 if (!insn_info)
3287 {
3288 gcc_assert (!INSN_P (insn));
3289 insn_info = df_insn_create_insn_record (insn);
3290 }
3291
3292 DF_INSN_INFO_LUID (insn_info) = luid;
3293 if (INSN_P (insn))
3294 luid++;
3295 }
3296 }
3297
3298
3299 /* Collect all artificial refs at the block level for BB and add them
3300 to COLLECTION_REC. */
3301
3302 static void
3303 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3304 {
3305 collection_rec->def_vec.truncate (0);
3306 collection_rec->use_vec.truncate (0);
3307 collection_rec->eq_use_vec.truncate (0);
3308 collection_rec->mw_vec.truncate (0);
3309
3310 if (bb->index == ENTRY_BLOCK)
3311 {
3312 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3313 return;
3314 }
3315 else if (bb->index == EXIT_BLOCK)
3316 {
3317 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3318 return;
3319 }
3320
3321 #ifdef EH_RETURN_DATA_REGNO
3322 if (bb_has_eh_pred (bb))
3323 {
3324 unsigned int i;
3325 /* Mark the registers that will contain data for the handler. */
3326 for (i = 0; ; ++i)
3327 {
3328 unsigned regno = EH_RETURN_DATA_REGNO (i);
3329 if (regno == INVALID_REGNUM)
3330 break;
3331 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3332 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3333 }
3334 }
3335 #endif
3336
3337 /* Add the hard_frame_pointer if this block is the target of a
3338 non-local goto. */
3339 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3340 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3341 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3342
3343 /* Add the artificial uses. */
3344 if (bb->index >= NUM_FIXED_BLOCKS)
3345 {
3346 bitmap_iterator bi;
3347 unsigned int regno;
3348 bitmap au = bb_has_eh_pred (bb)
3349 ? &df->eh_block_artificial_uses
3350 : &df->regular_block_artificial_uses;
3351
3352 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3353 {
3354 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3355 bb, NULL, DF_REF_REG_USE, 0);
3356 }
3357 }
3358
3359 df_canonize_collection_rec (collection_rec);
3360 }
3361
3362
3363 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3364
3365 void
3366 df_bb_refs_record (int bb_index, bool scan_insns)
3367 {
3368 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3369 rtx insn;
3370 int luid = 0;
3371
3372 if (!df)
3373 return;
3374
3375 df_collection_rec collection_rec;
3376 df_grow_bb_info (df_scan);
3377 if (scan_insns)
3378 /* Scan the block an insn at a time from beginning to end. */
3379 FOR_BB_INSNS (bb, insn)
3380 {
3381 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3382 gcc_assert (!insn_info);
3383
3384 insn_info = df_insn_create_insn_record (insn);
3385 if (INSN_P (insn))
3386 {
3387 /* Record refs within INSN. */
3388 DF_INSN_INFO_LUID (insn_info) = luid++;
3389 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3390 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3391 }
3392 DF_INSN_INFO_LUID (insn_info) = luid;
3393 }
3394
3395 /* Other block level artificial refs */
3396 df_bb_refs_collect (&collection_rec, bb);
3397 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3398
3399 /* Now that the block has been processed, set the block as dirty so
3400 LR and LIVE will get it processed. */
3401 df_set_bb_dirty (bb);
3402 }
3403
3404
3405 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3406 block. */
3407
3408 static void
3409 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3410 {
3411 #ifdef EH_USES
3412 unsigned int i;
3413 #endif
3414
3415 bitmap_clear (regular_block_artificial_uses);
3416
3417 if (reload_completed)
3418 {
3419 if (frame_pointer_needed)
3420 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3421 }
3422 else
3423 /* Before reload, there are a few registers that must be forced
3424 live everywhere -- which might not already be the case for
3425 blocks within infinite loops. */
3426 {
3427 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3428
3429 /* Any reference to any pseudo before reload is a potential
3430 reference of the frame pointer. */
3431 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3432
3433 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3434 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3435 #endif
3436
3437 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3438 /* Pseudos with argument area equivalences may require
3439 reloading via the argument pointer. */
3440 if (fixed_regs[ARG_POINTER_REGNUM])
3441 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3442 #endif
3443
3444 /* Any constant, or pseudo with constant equivalences, may
3445 require reloading from memory using the pic register. */
3446 if (picreg != INVALID_REGNUM
3447 && fixed_regs[picreg])
3448 bitmap_set_bit (regular_block_artificial_uses, picreg);
3449 }
3450 /* The all-important stack pointer must always be live. */
3451 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3452
3453 #ifdef EH_USES
3454 /* EH_USES registers are used:
3455 1) at all insns that might throw (calls or with -fnon-call-exceptions
3456 trapping insns)
3457 2) in all EH edges
3458 3) to support backtraces and/or debugging, anywhere between their
3459 initialization and where they the saved registers are restored
3460 from them, including the cases where we don't reach the epilogue
3461 (noreturn call or infinite loop). */
3462 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3463 if (EH_USES (i))
3464 bitmap_set_bit (regular_block_artificial_uses, i);
3465 #endif
3466 }
3467
3468
3469 /* Get the artificial use set for an eh block. */
3470
3471 static void
3472 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3473 {
3474 bitmap_clear (eh_block_artificial_uses);
3475
3476 /* The following code (down through the arg_pointer setting APPEARS
3477 to be necessary because there is nothing that actually
3478 describes what the exception handling code may actually need
3479 to keep alive. */
3480 if (reload_completed)
3481 {
3482 if (frame_pointer_needed)
3483 {
3484 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3485 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3486 bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3487 #endif
3488 }
3489 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3490 if (fixed_regs[ARG_POINTER_REGNUM])
3491 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3492 #endif
3493 }
3494 }
3495
3496
3497 \f
3498 /*----------------------------------------------------------------------------
3499 Specialized hard register scanning functions.
3500 ----------------------------------------------------------------------------*/
3501
3502
3503 /* Mark a register in SET. Hard registers in large modes get all
3504 of their component registers set as well. */
3505
3506 static void
3507 df_mark_reg (rtx reg, void *vset)
3508 {
3509 bitmap set = (bitmap) vset;
3510 int regno = REGNO (reg);
3511
3512 gcc_assert (GET_MODE (reg) != BLKmode);
3513
3514 if (regno < FIRST_PSEUDO_REGISTER)
3515 {
3516 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3517 bitmap_set_range (set, regno, n);
3518 }
3519 else
3520 bitmap_set_bit (set, regno);
3521 }
3522
3523
3524 /* Set the bit for regs that are considered being defined at the entry. */
3525
3526 static void
3527 df_get_entry_block_def_set (bitmap entry_block_defs)
3528 {
3529 rtx r;
3530 int i;
3531
3532 bitmap_clear (entry_block_defs);
3533
3534 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3535 {
3536 if (global_regs[i])
3537 bitmap_set_bit (entry_block_defs, i);
3538 if (FUNCTION_ARG_REGNO_P (i))
3539 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3540 }
3541
3542 /* The always important stack pointer. */
3543 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3544
3545 /* Once the prologue has been generated, all of these registers
3546 should just show up in the first regular block. */
3547 if (HAVE_prologue && epilogue_completed)
3548 {
3549 /* Defs for the callee saved registers are inserted so that the
3550 pushes have some defining location. */
3551 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3552 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3553 bitmap_set_bit (entry_block_defs, i);
3554 }
3555
3556 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3557 if (r && REG_P (r))
3558 bitmap_set_bit (entry_block_defs, REGNO (r));
3559
3560 /* If the function has an incoming STATIC_CHAIN, it has to show up
3561 in the entry def set. */
3562 r = targetm.calls.static_chain (current_function_decl, true);
3563 if (r && REG_P (r))
3564 bitmap_set_bit (entry_block_defs, REGNO (r));
3565
3566 if ((!reload_completed) || frame_pointer_needed)
3567 {
3568 /* Any reference to any pseudo before reload is a potential
3569 reference of the frame pointer. */
3570 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3571 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3572 /* If they are different, also mark the hard frame pointer as live. */
3573 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3574 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3575 #endif
3576 }
3577
3578 /* These registers are live everywhere. */
3579 if (!reload_completed)
3580 {
3581 #ifdef PIC_OFFSET_TABLE_REGNUM
3582 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3583 #endif
3584
3585 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3586 /* Pseudos with argument area equivalences may require
3587 reloading via the argument pointer. */
3588 if (fixed_regs[ARG_POINTER_REGNUM])
3589 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3590 #endif
3591
3592 #ifdef PIC_OFFSET_TABLE_REGNUM
3593 /* Any constant, or pseudo with constant equivalences, may
3594 require reloading from memory using the pic register. */
3595 if (picreg != INVALID_REGNUM
3596 && fixed_regs[picreg])
3597 bitmap_set_bit (entry_block_defs, picreg);
3598 #endif
3599 }
3600
3601 #ifdef INCOMING_RETURN_ADDR_RTX
3602 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3603 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3604 #endif
3605
3606 targetm.extra_live_on_entry (entry_block_defs);
3607 }
3608
3609
3610 /* Return the (conservative) set of hard registers that are defined on
3611 entry to the function.
3612 It uses df->entry_block_defs to determine which register
3613 reference to include. */
3614
3615 static void
3616 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3617 bitmap entry_block_defs)
3618 {
3619 unsigned int i;
3620 bitmap_iterator bi;
3621
3622 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3623 {
3624 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3625 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3626 }
3627
3628 df_canonize_collection_rec (collection_rec);
3629 }
3630
3631
3632 /* Record the (conservative) set of hard registers that are defined on
3633 entry to the function. */
3634
3635 static void
3636 df_record_entry_block_defs (bitmap entry_block_defs)
3637 {
3638 struct df_collection_rec collection_rec;
3639 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3640
3641 /* Process bb_refs chain */
3642 df_refs_add_to_chains (&collection_rec,
3643 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3644 NULL,
3645 copy_defs);
3646 }
3647
3648
3649 /* Update the defs in the entry block. */
3650
3651 void
3652 df_update_entry_block_defs (void)
3653 {
3654 bitmap_head refs;
3655 bool changed = false;
3656
3657 bitmap_initialize (&refs, &df_bitmap_obstack);
3658 df_get_entry_block_def_set (&refs);
3659 if (df->entry_block_defs)
3660 {
3661 if (!bitmap_equal_p (df->entry_block_defs, &refs))
3662 {
3663 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3664 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3665 df_ref_chain_delete (bb_info->artificial_defs);
3666 bb_info->artificial_defs = NULL;
3667 changed = true;
3668 }
3669 }
3670 else
3671 {
3672 struct df_scan_problem_data *problem_data
3673 = (struct df_scan_problem_data *) df_scan->problem_data;
3674 gcc_unreachable ();
3675 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3676 changed = true;
3677 }
3678
3679 if (changed)
3680 {
3681 df_record_entry_block_defs (&refs);
3682 bitmap_copy (df->entry_block_defs, &refs);
3683 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3684 }
3685 bitmap_clear (&refs);
3686 }
3687
3688
3689 /* Set the bit for regs that are considered being used at the exit. */
3690
3691 static void
3692 df_get_exit_block_use_set (bitmap exit_block_uses)
3693 {
3694 unsigned int i;
3695 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3696
3697 bitmap_clear (exit_block_uses);
3698
3699 /* Stack pointer is always live at the exit. */
3700 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3701
3702 /* Mark the frame pointer if needed at the end of the function.
3703 If we end up eliminating it, it will be removed from the live
3704 list of each basic block by reload. */
3705
3706 if ((!reload_completed) || frame_pointer_needed)
3707 {
3708 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3709 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
3710 /* If they are different, also mark the hard frame pointer as live. */
3711 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3712 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3713 #endif
3714 }
3715
3716 /* Many architectures have a GP register even without flag_pic.
3717 Assume the pic register is not in use, or will be handled by
3718 other means, if it is not fixed. */
3719 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3720 && picreg != INVALID_REGNUM
3721 && fixed_regs[picreg])
3722 bitmap_set_bit (exit_block_uses, picreg);
3723
3724 /* Mark all global registers, and all registers used by the
3725 epilogue as being live at the end of the function since they
3726 may be referenced by our caller. */
3727 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3728 if (global_regs[i] || EPILOGUE_USES (i))
3729 bitmap_set_bit (exit_block_uses, i);
3730
3731 if (HAVE_epilogue && epilogue_completed)
3732 {
3733 /* Mark all call-saved registers that we actually used. */
3734 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3735 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3736 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3737 bitmap_set_bit (exit_block_uses, i);
3738 }
3739
3740 #ifdef EH_RETURN_DATA_REGNO
3741 /* Mark the registers that will contain data for the handler. */
3742 if (reload_completed && crtl->calls_eh_return)
3743 for (i = 0; ; ++i)
3744 {
3745 unsigned regno = EH_RETURN_DATA_REGNO (i);
3746 if (regno == INVALID_REGNUM)
3747 break;
3748 bitmap_set_bit (exit_block_uses, regno);
3749 }
3750 #endif
3751
3752 #ifdef EH_RETURN_STACKADJ_RTX
3753 if ((!HAVE_epilogue || ! epilogue_completed)
3754 && crtl->calls_eh_return)
3755 {
3756 rtx tmp = EH_RETURN_STACKADJ_RTX;
3757 if (tmp && REG_P (tmp))
3758 df_mark_reg (tmp, exit_block_uses);
3759 }
3760 #endif
3761
3762 #ifdef EH_RETURN_HANDLER_RTX
3763 if ((!HAVE_epilogue || ! epilogue_completed)
3764 && crtl->calls_eh_return)
3765 {
3766 rtx tmp = EH_RETURN_HANDLER_RTX;
3767 if (tmp && REG_P (tmp))
3768 df_mark_reg (tmp, exit_block_uses);
3769 }
3770 #endif
3771
3772 /* Mark function return value. */
3773 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3774 }
3775
3776
3777 /* Return the refs of hard registers that are used in the exit block.
3778 It uses df->exit_block_uses to determine register to include. */
3779
3780 static void
3781 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3782 {
3783 unsigned int i;
3784 bitmap_iterator bi;
3785
3786 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3787 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3788 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3789
3790 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3791 /* It is deliberate that this is not put in the exit block uses but
3792 I do not know why. */
3793 if (reload_completed
3794 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3795 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3796 && fixed_regs[ARG_POINTER_REGNUM])
3797 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3798 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3799 #endif
3800
3801 df_canonize_collection_rec (collection_rec);
3802 }
3803
3804
3805 /* Record the set of hard registers that are used in the exit block.
3806 It uses df->exit_block_uses to determine which bit to include. */
3807
3808 static void
3809 df_record_exit_block_uses (bitmap exit_block_uses)
3810 {
3811 struct df_collection_rec collection_rec;
3812 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3813
3814 /* Process bb_refs chain */
3815 df_refs_add_to_chains (&collection_rec,
3816 BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3817 NULL,
3818 copy_uses);
3819 }
3820
3821
3822 /* Update the uses in the exit block. */
3823
3824 void
3825 df_update_exit_block_uses (void)
3826 {
3827 bitmap_head refs;
3828 bool changed = false;
3829
3830 bitmap_initialize (&refs, &df_bitmap_obstack);
3831 df_get_exit_block_use_set (&refs);
3832 if (df->exit_block_uses)
3833 {
3834 if (!bitmap_equal_p (df->exit_block_uses, &refs))
3835 {
3836 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3837 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3838 df_ref_chain_delete (bb_info->artificial_uses);
3839 bb_info->artificial_uses = NULL;
3840 changed = true;
3841 }
3842 }
3843 else
3844 {
3845 struct df_scan_problem_data *problem_data
3846 = (struct df_scan_problem_data *) df_scan->problem_data;
3847 gcc_unreachable ();
3848 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3849 changed = true;
3850 }
3851
3852 if (changed)
3853 {
3854 df_record_exit_block_uses (&refs);
3855 bitmap_copy (df->exit_block_uses,& refs);
3856 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3857 }
3858 bitmap_clear (&refs);
3859 }
3860
3861 static bool initialized = false;
3862
3863
3864 /* Initialize some platform specific structures. */
3865
3866 void
3867 df_hard_reg_init (void)
3868 {
3869 #ifdef ELIMINABLE_REGS
3870 int i;
3871 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3872 #endif
3873 if (initialized)
3874 return;
3875
3876 /* Record which registers will be eliminated. We use this in
3877 mark_used_regs. */
3878 CLEAR_HARD_REG_SET (elim_reg_set);
3879
3880 #ifdef ELIMINABLE_REGS
3881 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3882 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3883 #else
3884 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3885 #endif
3886
3887 initialized = true;
3888 }
3889
3890
3891 /* Recompute the parts of scanning that are based on regs_ever_live
3892 because something changed in that array. */
3893
3894 void
3895 df_update_entry_exit_and_calls (void)
3896 {
3897 basic_block bb;
3898
3899 df_update_entry_block_defs ();
3900 df_update_exit_block_uses ();
3901
3902 /* The call insns need to be rescanned because there may be changes
3903 in the set of registers clobbered across the call. */
3904 FOR_EACH_BB_FN (bb, cfun)
3905 {
3906 rtx insn;
3907 FOR_BB_INSNS (bb, insn)
3908 {
3909 if (INSN_P (insn) && CALL_P (insn))
3910 df_insn_rescan (insn);
3911 }
3912 }
3913 }
3914
3915
3916 /* Return true if hard REG is actually used in the some instruction.
3917 There are a fair number of conditions that affect the setting of
3918 this array. See the comment in df.h for df->hard_regs_live_count
3919 for the conditions that this array is set. */
3920
3921 bool
3922 df_hard_reg_used_p (unsigned int reg)
3923 {
3924 return df->hard_regs_live_count[reg] != 0;
3925 }
3926
3927
3928 /* A count of the number of times REG is actually used in the some
3929 instruction. There are a fair number of conditions that affect the
3930 setting of this array. See the comment in df.h for
3931 df->hard_regs_live_count for the conditions that this array is
3932 set. */
3933
3934
3935 unsigned int
3936 df_hard_reg_used_count (unsigned int reg)
3937 {
3938 return df->hard_regs_live_count[reg];
3939 }
3940
3941
3942 /* Get the value of regs_ever_live[REGNO]. */
3943
3944 bool
3945 df_regs_ever_live_p (unsigned int regno)
3946 {
3947 return regs_ever_live[regno];
3948 }
3949
3950
3951 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3952 to change, schedule that change for the next update. */
3953
3954 void
3955 df_set_regs_ever_live (unsigned int regno, bool value)
3956 {
3957 if (regs_ever_live[regno] == value)
3958 return;
3959
3960 regs_ever_live[regno] = value;
3961 if (df)
3962 df->redo_entry_and_exit = true;
3963 }
3964
3965
3966 /* Compute "regs_ever_live" information from the underlying df
3967 information. Set the vector to all false if RESET. */
3968
3969 void
3970 df_compute_regs_ever_live (bool reset)
3971 {
3972 unsigned int i;
3973 bool changed = df->redo_entry_and_exit;
3974
3975 if (reset)
3976 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3977
3978 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3979 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3980 {
3981 regs_ever_live[i] = true;
3982 changed = true;
3983 }
3984 if (changed)
3985 df_update_entry_exit_and_calls ();
3986 df->redo_entry_and_exit = false;
3987 }
3988
3989 \f
3990 /*----------------------------------------------------------------------------
3991 Dataflow ref information verification functions.
3992
3993 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3994 df_reg_chain_verify_unmarked (refs)
3995 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3996 df_mws_verify (mw*, mw*, bool)
3997 df_insn_refs_verify (collection_rec, bb, insn, bool)
3998 df_bb_refs_verify (bb, refs, bool)
3999 df_bb_verify (bb)
4000 df_exit_block_bitmap_verify (bool)
4001 df_entry_block_bitmap_verify (bool)
4002 df_scan_verify ()
4003 ----------------------------------------------------------------------------*/
4004
4005
4006 /* Mark all refs in the reg chain. Verify that all of the registers
4007 are in the correct chain. */
4008
4009 static unsigned int
4010 df_reg_chain_mark (df_ref refs, unsigned int regno,
4011 bool is_def, bool is_eq_use)
4012 {
4013 unsigned int count = 0;
4014 df_ref ref;
4015 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4016 {
4017 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4018
4019 /* If there are no def-use or use-def chains, make sure that all
4020 of the chains are clear. */
4021 if (!df_chain)
4022 gcc_assert (!DF_REF_CHAIN (ref));
4023
4024 /* Check to make sure the ref is in the correct chain. */
4025 gcc_assert (DF_REF_REGNO (ref) == regno);
4026 if (is_def)
4027 gcc_assert (DF_REF_REG_DEF_P (ref));
4028 else
4029 gcc_assert (!DF_REF_REG_DEF_P (ref));
4030
4031 if (is_eq_use)
4032 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4033 else
4034 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4035
4036 if (DF_REF_NEXT_REG (ref))
4037 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
4038 count++;
4039 DF_REF_REG_MARK (ref);
4040 }
4041 return count;
4042 }
4043
4044
4045 /* Verify that all of the registers in the chain are unmarked. */
4046
4047 static void
4048 df_reg_chain_verify_unmarked (df_ref refs)
4049 {
4050 df_ref ref;
4051 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4052 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4053 }
4054
4055
4056 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4057
4058 static bool
4059 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4060 bool abort_if_fail)
4061 {
4062 unsigned int ix;
4063 df_ref new_ref;
4064
4065 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4066 {
4067 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4068 {
4069 if (abort_if_fail)
4070 gcc_assert (0);
4071 else
4072 return false;
4073 }
4074
4075 /* Abort if fail is called from the function level verifier. If
4076 that is the context, mark this reg as being seem. */
4077 if (abort_if_fail)
4078 {
4079 gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4080 DF_REF_REG_UNMARK (old_rec);
4081 }
4082
4083 old_rec = DF_REF_NEXT_LOC (old_rec);
4084 }
4085
4086 if (abort_if_fail)
4087 gcc_assert (old_rec == NULL);
4088 else
4089 return old_rec == NULL;
4090 return false;
4091 }
4092
4093
4094 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4095
4096 static bool
4097 df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec,
4098 struct df_mw_hardreg *old_rec,
4099 bool abort_if_fail)
4100 {
4101 unsigned int ix;
4102 struct df_mw_hardreg *new_reg;
4103
4104 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4105 {
4106 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4107 {
4108 if (abort_if_fail)
4109 gcc_assert (0);
4110 else
4111 return false;
4112 }
4113 old_rec = DF_MWS_NEXT (old_rec);
4114 }
4115
4116 if (abort_if_fail)
4117 gcc_assert (old_rec == NULL);
4118 else
4119 return old_rec == NULL;
4120 return false;
4121 }
4122
4123
4124 /* Return true if the existing insn refs information is complete and
4125 correct. Otherwise (i.e. if there's any missing or extra refs),
4126 return the correct df_ref chain in REFS_RETURN.
4127
4128 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4129 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4130 verification mode instead of the whole function, so unmark
4131 everything.
4132
4133 If ABORT_IF_FAIL is set, this function never returns false. */
4134
4135 static bool
4136 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4137 basic_block bb,
4138 rtx insn,
4139 bool abort_if_fail)
4140 {
4141 bool ret1, ret2, ret3, ret4;
4142 unsigned int uid = INSN_UID (insn);
4143 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4144
4145 df_insn_refs_collect (collection_rec, bb, insn_info);
4146
4147 /* Unfortunately we cannot opt out early if one of these is not
4148 right because the marks will not get cleared. */
4149 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4150 abort_if_fail);
4151 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4152 abort_if_fail);
4153 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4154 abort_if_fail);
4155 ret4 = df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4156 abort_if_fail);
4157 return (ret1 && ret2 && ret3 && ret4);
4158 }
4159
4160
4161 /* Return true if all refs in the basic block are correct and complete.
4162 Due to df_ref_chain_verify, it will cause all refs
4163 that are verified to have DF_REF_MARK bit set. */
4164
4165 static bool
4166 df_bb_verify (basic_block bb)
4167 {
4168 rtx insn;
4169 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4170 struct df_collection_rec collection_rec;
4171
4172 gcc_assert (bb_info);
4173
4174 /* Scan the block, one insn at a time, from beginning to end. */
4175 FOR_BB_INSNS_REVERSE (bb, insn)
4176 {
4177 if (!INSN_P (insn))
4178 continue;
4179 df_insn_refs_verify (&collection_rec, bb, insn, true);
4180 df_free_collection_rec (&collection_rec);
4181 }
4182
4183 /* Do the artificial defs and uses. */
4184 df_bb_refs_collect (&collection_rec, bb);
4185 df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4186 df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4187 df_free_collection_rec (&collection_rec);
4188
4189 return true;
4190 }
4191
4192
4193 /* Returns true if the entry block has correct and complete df_ref set.
4194 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4195
4196 static bool
4197 df_entry_block_bitmap_verify (bool abort_if_fail)
4198 {
4199 bitmap_head entry_block_defs;
4200 bool is_eq;
4201
4202 bitmap_initialize (&entry_block_defs, &df_bitmap_obstack);
4203 df_get_entry_block_def_set (&entry_block_defs);
4204
4205 is_eq = bitmap_equal_p (&entry_block_defs, df->entry_block_defs);
4206
4207 if (!is_eq && abort_if_fail)
4208 {
4209 fprintf (stderr, "entry_block_defs = ");
4210 df_print_regset (stderr, &entry_block_defs);
4211 fprintf (stderr, "df->entry_block_defs = ");
4212 df_print_regset (stderr, df->entry_block_defs);
4213 gcc_assert (0);
4214 }
4215
4216 bitmap_clear (&entry_block_defs);
4217
4218 return is_eq;
4219 }
4220
4221
4222 /* Returns true if the exit block has correct and complete df_ref set.
4223 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4224
4225 static bool
4226 df_exit_block_bitmap_verify (bool abort_if_fail)
4227 {
4228 bitmap_head exit_block_uses;
4229 bool is_eq;
4230
4231 bitmap_initialize (&exit_block_uses, &df_bitmap_obstack);
4232 df_get_exit_block_use_set (&exit_block_uses);
4233
4234 is_eq = bitmap_equal_p (&exit_block_uses, df->exit_block_uses);
4235
4236 if (!is_eq && abort_if_fail)
4237 {
4238 fprintf (stderr, "exit_block_uses = ");
4239 df_print_regset (stderr, &exit_block_uses);
4240 fprintf (stderr, "df->exit_block_uses = ");
4241 df_print_regset (stderr, df->exit_block_uses);
4242 gcc_assert (0);
4243 }
4244
4245 bitmap_clear (&exit_block_uses);
4246
4247 return is_eq;
4248 }
4249
4250
4251 /* Return true if df_ref information for all insns in all blocks are
4252 correct and complete. */
4253
4254 void
4255 df_scan_verify (void)
4256 {
4257 unsigned int i;
4258 basic_block bb;
4259 bitmap_head regular_block_artificial_uses;
4260 bitmap_head eh_block_artificial_uses;
4261
4262 if (!df)
4263 return;
4264
4265 /* Verification is a 4 step process. */
4266
4267 /* (1) All of the refs are marked by going through the reg chains. */
4268 for (i = 0; i < DF_REG_SIZE (df); i++)
4269 {
4270 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4271 == DF_REG_DEF_COUNT (i));
4272 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4273 == DF_REG_USE_COUNT (i));
4274 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4275 == DF_REG_EQ_USE_COUNT (i));
4276 }
4277
4278 /* (2) There are various bitmaps whose value may change over the
4279 course of the compilation. This step recomputes them to make
4280 sure that they have not slipped out of date. */
4281 bitmap_initialize (&regular_block_artificial_uses, &df_bitmap_obstack);
4282 bitmap_initialize (&eh_block_artificial_uses, &df_bitmap_obstack);
4283
4284 df_get_regular_block_artificial_uses (&regular_block_artificial_uses);
4285 df_get_eh_block_artificial_uses (&eh_block_artificial_uses);
4286
4287 bitmap_ior_into (&eh_block_artificial_uses,
4288 &regular_block_artificial_uses);
4289
4290 /* Check artificial_uses bitmaps didn't change. */
4291 gcc_assert (bitmap_equal_p (&regular_block_artificial_uses,
4292 &df->regular_block_artificial_uses));
4293 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses,
4294 &df->eh_block_artificial_uses));
4295
4296 bitmap_clear (&regular_block_artificial_uses);
4297 bitmap_clear (&eh_block_artificial_uses);
4298
4299 /* Verify entry block and exit block. These only verify the bitmaps,
4300 the refs are verified in df_bb_verify. */
4301 df_entry_block_bitmap_verify (true);
4302 df_exit_block_bitmap_verify (true);
4303
4304 /* (3) All of the insns in all of the blocks are traversed and the
4305 marks are cleared both in the artificial refs attached to the
4306 blocks and the real refs inside the insns. It is a failure to
4307 clear a mark that has not been set as this means that the ref in
4308 the block or insn was not in the reg chain. */
4309
4310 FOR_ALL_BB_FN (bb, cfun)
4311 df_bb_verify (bb);
4312
4313 /* (4) See if all reg chains are traversed a second time. This time
4314 a check is made that the marks are clear. A set mark would be a
4315 from a reg that is not in any insn or basic block. */
4316
4317 for (i = 0; i < DF_REG_SIZE (df); i++)
4318 {
4319 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4320 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4321 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));
4322 }
4323 }